자바스크립트 알고리즘 : 재귀함수란?

*Udemy의 "Master the Coding Interview : Data Structures + Algorithms" 강의에서 학습한 내용을 정리한 포스팅입니다.

*자바스크립트를 배우는 단계라 오류가 있을 수 있습니다. 틀린 내용은 댓글로 말씀해주시면 수정하겠습니다. 감사합니다. :)

---

1. 재귀 함수란?

재귀 함수는 알고리즘이라기 보다는 문제를 해결하기 위한 컨셉, 코딩 패턴에 더 가깝다. 앞으로 배울 sorting, searching의 경우에 재귀를 많이 사용하게 될 예정이다.

쉽게 말해 재귀 함수란, 특정 함수가 함수 안에서 자기 자신을 다시 호출하는 것을 의미한다. 반복적인 sub task가 있을 때 사용하면 좋다.

2. 재귀 함수의 3가지 원칙

1. Base Case를 명확히 작성한다.
2. Base Case의 조건에 부합하지 않을 경우, Recursive Case를 명확히 작성한다.
3. 원하는 결과물까지 최대한 접근하고, 필요한 경우에 return한다. 일반적으로 2개의 return 문이 존재한다.
(Base Case의 return문 하나, Recursive Case의 return문 하나)

 

let counter = 0;
function inception() {
  if (counter > 3) {
    return 'done!';
  }
  counter++;
  inception();
}
inception();

위 inception 함수의 실행 결과는 무엇일까? 일반적 예상과는 달리 'done!' 대신 undefined가 출력된다. 왜일까?

let counter = 0;
function inception() {
  console.log(counter); // console.log()를 추가해보자.
  if (counter > 3) {
    return 'done!';
  }
  counter++;
  inception();
}
inception();
/*
0
1
2
3
4
=> undefined
*/

console.log()를 추가해보면, 분명히 counter는 0부터 4까지 정상적으로 추가되면서 출력이 되었다. 그럼에도 undefined를 출력한 이유는?

 

크롬 디버거모드를 실행해보면, 콜스택에 inception 실행 컨텍스트가 계속 쌓이는 것을 볼 수 있다. 그리고 마지막, 즉 counter가 4가 되어서 return 'done!' 를 출력하는 조건문에 들어갔을 때, 콜스택 최상단의 실행 컨텍스트에서 return value는 분명 'done!'임을 확인할 수 있다.

 

그러나 최상단의 콜스택이 제거되면서 리턴된 done!은 사라지고 return value가 undefined가 된 것을 확인할 수 있다. 그 이유는 무엇일까? 

 

최초 작성한 코드는 아래 코드와 실질적으로 동일한 코드이다.

inception(inception(inception(inception(inception()))))

가장 안쪽의 inception()이 return 되면서 'done!'으로 치환된다.

inception(inception(inception(inception('done!'))))

그런데 이 상황을 보면, 현재 가장 안쪽의 inception('done!')함수를 실행하면 이 경우 if 문에 들어가지 않기 때문에 done!을 return하는 if 문 안에 들어가지 않게 된다. 그런데 if 문 밖에서 inception 함수는 어떤 것도 return 시키지 않고 있다. 따라서 return value가 없으므로 undefined가 리턴되는 것이다.

 

따라서 아래와 같이 코드를 수정하면 최종적으로 done!이 리턴된다.

let counter = 0;
function inception() {
  if (counter > 3) {
    return 'done!';
  }
  counter++;
  return inception(); // 이 부분에 return이 들어간다!
}
inception();

 

3. 재귀 함수를 활용한 알고리즘 풀이 1 : Factorial

function factorial1(number) { // O(n)
  //code here
  if (number <= 2) return number;
  
  return factorial1(number-1) * number;
}

function factorial2(number) { // O(n)
  //code here
  let i = 1;
  let answer = 1;
  while (i <= number) {
    answer = answer * i;
    i++;
  }
  return answer;
}

첫번째 풀이는 재귀함수를 이용했고, 두번째 함수는 반복문을 이용했다. 이 경우에 시간 복잡도는 둘 다 O(n)이다.

 

4. 재귀 함수를 활용한 알고리즘 풀이 2 : Fibonacci

function fibonacci1(n){ // O(2^n)
  //code here;
  if (n < 2) return n;
  return fibonacci1(n-1) + fibonacci1(n-2);
}

function fibonacci2(n) { // O(n)
  //code here;
  const arr = [0,1];
  for (let i = 2; i <= n; i++) {
    arr.push(arr[arr.length-1] + arr[arr.length-2]);
  }
  return arr[n];
}

첫번째는 재귀 함수를 이용해서, 두번째는 반복문으로 풀었는데, 첫번째 풀이의 시간 복잡도는 O(2^n)이 된다. input이 하나가 커질 때마다 처리할 작업량이 기하급수적으로 늘어나는 거의 최악의 시간복잡도가 된다. O(2^n)은 영어로 Exponential Time이라고도 부른다.

 

5. 왜, 언제 재귀 함수를 사용해야 할까?

재귀 함수로 풀 수 있는 모든 문제는 iterative한 해결책으로 풀 수 있다. 그런데 왜 recursive를 배우고 활용하도록 노력해야 하는 것일까? 

 

재귀 함수를 이용하면 1) 코드가 DRY(Do not Repeat Yourself)해지고, 2) Readability(가독성)가 올라가는 반면, 콜 스택을 많이 차지하는 단점도 존재한다. 그럼에도 재귀 함수는 얼마나 많은 반복이 필요할지 모를 경우, 또는 tree 자료 구조나 노드 사이를 traversing하는 작업이 필요할 경우에는 일반적인 반복문보다 훨씬 효율적인 해결책이 된다.

 

1. tree 자료구조를 이용하거나, 또는 tree로 converting이 필요한 경우에는 재귀를 사용해라.
  1) Divided into a number of subproblems that are smaller instances of the same problem.
  2) Each instance of the subproblem is identical in nature.
  3) The solutions of each subproblem can be combined to solve the problem at hand.

2. Divide and Conquer using Recursion

 

# Tail Call Optimization

최근에는 콜 스택을 많이 잡아먹지 않고도 재귀를 활용할 수 있는 방법도 있다고 한다. 소개 링크만 남겨놓는다.

https://2ality.com/2015/06/tail-call-optimization.html