윤성우의 열혈 자료구조를 읽고 복습한 내용입니다.

함수의 재귀적 호출의 이해

재귀는 자료구조와 알고리즘에 있어서 매우 중요한 요소이다.

재귀함수의 기본적인 이해

function Recursive(){
  console.log("Recursive call!");
  Recursive(); // 자신을 재호출한다.
}

완료되지 않은 함수를 다시 호출하는 것이 가능할까?

위 질문의 대답은 Yes이다. 그 이유에 대해서는 아래 그림을 보자.

Recursive 함수를 실행하는 중간에 다시 Recursive 함수가 호출되면, Recursive 함수의 복사본을 하나 더 만들어서 복사본을 실행하게 되기 때문에 가능한 것이다.

지금 정의한 Recursive 함수는 한번 호출되면 계속해서 호출되는 문제가 있다. 이러한 문제는 Recursive 함수에 '재귀의 탈출조건'이 없기 때문에 발생한다. 탈출조건을 추가해보자.

function Recursive(num){
  if(num <= 0) return;
  console.log("Recursive call!", num);
  Recursive(num-1);
}

Recursive(3);

/*
expected output:
Recursive call! 3
Recursive call! 2
Recursive call! 1
*/

위 그림에서 볼 수 있듯이, 재귀적으로 호출이 이뤄지고 있는 Recursive 함수에 0이 전달되면서 '재귀의 탈출조건'이 성립되어 함수가 반환하기 시작한다. 이처럼 재귀함수를 정의하는데 있어서 탈출조건을 구성하는 것은 매우 중요한 일이다.

재귀함수의 디자인 사례

재귀함수는 자료구조나 알고리즘의 어려운 문제를 단순화하는데 사용되는 중요한 도구이다. 재귀함수가 있기에 재귀적인 수학적 수식을 그대로 코드로 옮길 수 있다. 이러한 재귀함수의 특징을 보이기 위해 팩토리얼(factorial) 값을 반환하는 함수를 재귀적으로 구현해보자. 정수 $n$의 팩토리얼은 $n!$로 표시하고, 수식적 의미는 다음과 같다.

정수 $n$팩토리얼은 정수 $n$과 $n-1$팩토리얼의 곱으로 표현할 수 있으므로, $n$팩토리얼 $f(n)$은 수식적으로 다음과 같이 표현할 수 있다.

위의 식을 보면 $f(0)$에 해당하는 $0!$이 1이므로 이것이 재귀함수의 탈출조건이 된다. 따라서 위의 식을 재귀함수를 이용해서 코드로 옮길 수 있다.

const Factorial = (n) => {
  if(n === 0) return 1;
  else return n * Factorial(n-1);
}

console.log("1! =",Factorial(1));
console.log("2! =",Factorial(2));
console.log("3! =",Factorial(3));
console.log("4! =",Factorial(4));
console.log("9! =",Factorial(9));

/*
expected output:
1! = 1
2! = 2
3! = 6
4! = 24
9! = 362880
*/