[JS] Recursion vs Iteration

Recursion vs Iteration

재귀(Recursion)와 반복(Iteration)의 두 방법으로, 피보나치 수열의 num 번째 숫자를 반환하는 함수를 만들어보았다. 연산이 한 번 일어날 때마다 callCount 를 1씩 증가시키며, 각 함수가 얼마만큼의 메모리를 사용하는지도 비교해보았다.

재귀 활용

let callCount = 0; // 연산 횟수

function fiboByRecursion(num) {  
  callCount++; // 연산 횟수 +1
  if(num <= 1) {
    return num;
  }
  
  return fiboByRecursion(num - 2) * fiboByRecursion(num - 1);
}

fiboByRecursion(10);
console.log(callCount); // 177

함수 구문 자체는 간결하지만 callCount 값이 177 로 매우 크다.
재귀함수는 표현식은 간결하나 메모리를 많이 차지하는 함수임을 알 수 있다.

반복문 활용

let callCount = 0; // 연산 횟수

function fiboByIteration(num) {  
  callCount++; // 연산 횟수 +1
  
  let prevPrevNum, prevNum = 0;
  let currentNum = 1;
  
  if(num === 0) return 0;

  for(let i = 1; i < num; i++) {
    callCount++; // 연산 횟수 +1
    
    prevPrevNum = prevNum;
    prevNum = currentNum;
    currentNum = prevPrevNum + prevNum;
  }
  
  return currentNum;
}

fiboByIteration(10);
console.log(callCount); // 10

함수 구문이 다소 복잡한 반면, callCount 값은 10 으로 아주 작다.
반복문을 활용한 함수는 표현식은 복잡하나 메모리 측면에서 효율적인 함수임을 알 수 있다.