알고리즘에서 재귀 함수를 사용하는 이유는?

재귀함수란?

• 자기 자신을 호출하는 함수이다.
• 반복문으로도 구현될 수 있다.

재귀 함수 예제 코드 (자바스크립트)

function recursive(num) {
  // base case, stopping condition, 종료 조건
  if (num > 3) {
    return;
  }

  console.log(`before call itself, num: ${num}`);
  recursive(num + 1);
  console.log(`after call itself, num: ${num}`);
  return;
}

• 위는 아주 간단한 재귀 함수의 예이다.
• 위의 주석에서 base case 라고 표기된 부분은 재귀 함수를 그만 생성하며 재귀 종료가 일어나는 시나리오를 말한다.
  • stopping condition, 종료 조건 이라고 말하기도 한다.

실행 결과로 재귀 동작 살펴보기

before call itself, num: 1
before call itself, num: 2
before call itself, num: 3
after call itself, num: 3
after call itself, num: 2
after call itself, num: 1

• 첫번째 출력문까지는 일반 함수와 별다른 차이가 없으므로 before call itself, num: 1 이 먼저 출력된다.
• console.log() 를 통해 출력을 마친 뒤에는 재귀로 자기 자신을 호출해나간다.
• base case 를 만나기 전까지는 before call itself, num: x 만 계속 출력된다.
  • 이 때 callstack 이라는 곳에 종료되지 못한 함수가 계속 쌓여 있다.
• 추후 base case 를 만나게 되면서 마침내 callstack 에 쌓인 함수들에서 재귀 호출 뒷부분을 마저 수행하고 함수를 callstack 에서 걷어낸다.
  • 이 때, callstack 의 가장 안쪽 함수부터 처리되므로 마지막 숫자는 3, 2, 1 의 순서로 출력된다.

base case 를 어마무시하게 큰 숫자로 지정하면, callstack 에 종료되지 않은 함수가 아주 많이 쌓여서, 자바스크립트 엔진이 정한 사이즈의 한계를 넘어서며 "too much recursion" or "Maximum call stack size exceeded" 에러가 뜨고 작업이 비정상적으로 종료된다.

보통은 프로그래머가 의도치 않게 재귀 호출을 만들어내는 경우 이러한 에러 메세지를 보게 된다.

재귀 함수의 목적

사실 이전의 소스코드는 for 문으로 구성하는 게 callstack 걱정도 없으며, 훨씬 이해도 쉽고, 간단하다. 그렇다면 알고리즘에서 재귀 함수를 사용하는 목적은 뭘까?

어떤 큰 문제(Main problem)를 작은 문제(Sub problems)로 분할해야 하는 경우, 유리하다는 이유 때문에 사용한다.

이를테면, n 번째 피보나치 수열을 구하는 문제가 있을 때, 우리는 F(n) = F(n-2) + F(n-1) 이라는 공식을 쉽게 도출해낼 수 있다.

이는 아래의 코드처럼 직관적으로 표현될 수 있다. n 번째 피보나치 수열 숫자를 구하는 것은 n-1 번째 피보나치 수열과 n-2 번째 피보나치 수열을 구하라는 두개의 문제로 나눌 수 있고, n-1 번째 피보나치 수열도 마찬가지로 계속 하위 문제로 나눌 수 있다.

Fn = Fn-2 + Fn-1 수식을 재귀 관계라고 표현할 수 있다.

알고리즘에서 재귀 함수를 사용하는 이유는 큰 문제를 작은 문제로 분할하여 쉽게 풀 수 있다는 재귀 관계를 파악했을 때, 이를 쉽게 코드로 옮길 수 있기 때문이다.

function getFibo(n) {
  if (n < 1) {
    return 0;
  }

  if (n === 1) {
    return 1;
  }

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

for 문으로 쉽게 풀 수 있는 문제는 굳이 재귀를 사용할 이유가 없다. 일단 속도도 느리며, 이해도 어렵다.