재귀함수와 반복문

오늘은 

알고리즘 문제 예상 대진표를 풀며 알게된 재귀 함수와 반복문의 차이점에 대해 작성해보겠습니다. 

 

문제를 풀며 제가 사용한 재귀 함수입니다.

function solution(n, a, b) {
  let round = 0;

  const recursion = (a, b, round) => {
    if (a !== b) {
      return recursion(Math.ceil(a / 2), Math.ceil(b / 2), round + 1);
    }
    return round;
  };
  
  const answer = recursion(a, b, round);
  return answer;
}

 

a와 b가 동일한 값을 가질때까지 나눠진 뒤 올림 처리 되는 것을 볼 수 있습니다. 

이를 반복문으로 표현한다면

function solution(n, a, b) {
  let round = 0;

  while (a !== b) {
    a = Math.ceil(a / 2);
    b = Math.ceil(b / 2);
    round++;
  }
  return round;
}

 

이런 코드로 표현할 수 있습니다.

 

재귀함수와 반복문은 코드의 가독성 뿐만 아니라 시간복잡도에서도 차이가 있습니다. 

좌: 재귀 함수, 우: 반복문

해당 문제의 테스트 케이스를 통과하는 것은 문제없지만, 우측에 반복문을 사용했을 때 더 빠르게 통과되는 걸 볼 수 있습니다. 

왜 이런 차이가 생기는걸까요 ? 

 

	재귀함수	반복문
정의	함수를 다시 호출하여 반복작업 수행	명령을 반복적으로 실행
스택 메모리	함수 호출 시 함수의 매개변수, 지역변수, 리턴값, 함수 종료 후 돌아가는 위치가 스택메모리에 저장	스택 메모리를 사용하지 않음
무한 반복 시	무한 재귀는 스택 오버플로우 발생	무한 루프는 CPU 사이클을 반복적으로 사용
속도	느린 실행	빠른 실행

 

 

재귀함수는 스택메모리에 함수 실행을 저장하고 있습니다. 

 

[출처] : boostCourse - 재귀 학습 자료

 

 

반복문은 동일한 변수를 지속적으로 사용하기 때문에 새로운 함수를 호출할 때 비용이 발생하지 않습니다. 

반면, 재귀 함수는 함수를 호출하며 context switching 비용이 발생하게 됩니다. 

즉 메모리를 많이 사용하고 (스택을 사용하므로) 속도가 느려지게 됩니다. 

 

그렇다면 어떤 때에 재귀 함수를 사용해야 할까요 ? 

 

1. 변수 사용을 줄여야 할 때 

변수 사용이 줄어든다는 뜻은 프로그램에 오류가 생길 가능성이 줄어들고, 프로그램이 정상적으로 돌아가는지에 대한 증명이 쉬워진다는 뜻입니다.

let sum = 0;
for(let i = 0; i <= 100; i++) {
  sum += i;
}

일반 반복문

 

function sum(x) {
  if(x === 100) return x;
  else return x + sum(x + 1);
}

sum(0)

재귀함수

 

2. 알고리즘 자체가 재귀적일 때 

피보나치 수열에 관한 코드입니다. 재귀함수를 사용함으로써 코드가 간결해지고 가독성이 좋아졌습니다.

function fibonacci(n) {
  let pre = 0;
  let cur = 1;
  let last = 0;
  for(let i = 1; i < n; i++){
    last = pre + cur;
    pre = cur;
    cur = last;
  }
  return last;
}

일반 반복문

 

function fibonacci(num) {
  if(num < 2) return num;
  return fibonacci(num - 1) + fibonacci(num - 2);
}

재귀함수

 

마무리

재귀 함수를 사용하여 반복을 구현한다면 좀 더 직관적이고 가독성 좋은 코드를 작성할 수 있습니다.

하지만 콜 스택이 쌓여 Stack OverFlow가 발생하거나 성능적인 이슈가 생길 수 있고 따라서 코드의 목적에 따라 

예측 가능한 범위에서 사용할 수 있도록 주의해야겠습니다.