[Algorithm] Recursion - 재귀

Loops may achieve a performance gain for your program. Recursion may achieve a performance gain for your programmer. Choose which is more important in your situation!

 

: 루프는 프로그램의 성능을 향상시킵니다. 재귀는 프로그래머의 실력을 향상시킵니다. 상황에 따라 더 적합한 걸 선택하세요!

 

 

Recursion ( 재귀 )

재귀는 반복문과 그 역할을 서로 바꿀 수 있다. 재귀를 쓰면 복잡한 코드가 조금 더 간결해보이는 효과를 나타낸다.

 

피보나치를 구현해보자.

반복문:

const fib1 = (n) => {
  if ( n < 3 ) {
    return n === 0 ? 0 : 1;
  }
  const arr = [0, 1, 1];
  let tmp = 0;

  for ( let i = 2; i < n; i++ ) {
    [ arr[0], arr[1], arr[2] ] = [ arr[1], arr[2], tmp ];
    arr[2] = arr[1] + arr[0];
  }

  return arr[2];
}

 

재귀함수:

const fib2 = (n) => {
  if ( n < 3 ) {
    return n === 0 ? 0 : 1;
  }

  return fib2(n-1) + fib2(n-2);
}

 

재귀함수로 문제를 해결하는 코드는 아주 간결하고 직관적이다.

재귀 함수를 가장 잘 나타내는 말은 functional program 이다.

 

functional programming은 함수의 형태로 코드를 구현하는 걸 말하는 데,

피보나치의 일반항은 F(n) = F(n-1) + F(n-2) 이다.

 

이 일반항을 그대로 코드로 구현하는 것이 functional programming 이며, 직관적으로 어떤 기능을 수행하는 지 알 수 있다.

그리고 이런 functional programming에 가장 많이 사용되는 프로그래밍 방식이 Recursion이다.

 

Call Stack ( 콜스택 )

반복문 대신재귀함수를 사용할 때 가장 많이, 자주, 쉽게 발견할 수 있는 에러가 "Uncaught RangeError: Maximum call stack size exceeded" 이다.

스택은 앞선 포스팅에서 확인할 수 있다.

 

컴파일러 혹은 시스템은 프로그램을 실행할 때 코드를 순서대로 읽으며 함수를 호출하는 순서대로 실행할 코드를 스택의 형태로 쌓는다. 그리고 스택의 사이즈는 정해져 있는데, 재귀함수가 스스로를 호출하면서 함수호출이 콜스택에 쌓이다가 스택의 사이즈를 넘어서면서 발생하는 에러가 위에서 보이는 에러이다. ( 일반적으로 스택에 다 담지 못하는 에러를 스택오버플로우라고 한다 / stack overflow )

 

 

따라서 재귀함수를 선언하고 사용함에 있어 그 구조를 짜는 것이 매우 중요하다.

재귀함수의 구조는 Base Case 와 Recursive Case로 나뉘어진다.

 

혹시 귀납법 ( Inductive reasoning ) 에 대해 알고 있다면 재귀함수의 구조를 이해하는 것에 유리하다.

귀납법은 Base Case 와 Inductive Case로 나뉘어 지는데, 재귀함수의 구조와 매우 유사하다.

 

---

n! ( 팩토리얼 ) 을 증명해보자

n이 1일 때는 결과가 1이고,

n이 2일 때는 결과가 2이다.

n이 n일 때는 결과가 n * (n-1) * ... * 2 * 1 이다.

 

그렇다면 n이 n+1일 때는 어떨까?

결과는 (n+1) * n * (n-1) * ... * 2 * 1 이 된다.

 

따라서, n이 0보다 큰 양의 정수라면 1부터 n까지의 모든 정수의 곱이 n! 이다.

---

그리고 이걸 코드로 옮기면, 재귀함수가 된다.

const factorial = (n) => {
  return n === 1 ? 1 : n * factorial(n-1);
}

 

간-단

편-안

 

복잡한 내용을 풀려고 시도할 수록 재귀함수는 더더 어려워질 수 있다. 그렇지만 기억하자. 재귀함수의 적절한 사용으로 코드는 더 간결해질 수 있다.