Recursive Function

Recursive Function

재귀: 함수가 자기자신을 다시 호출하는 방식으로, 함수 내 하위의 문제들을 초함하고 있는 경우 문제해결에 이용된다.

즉, 재귀함수는 함수 내에서 자기 자신을 다시 호출하는 함수다.

재귀함수의 형식

재귀함수를 세분화하면 크게 세 부분으로 나눌 수 있다ㅏ.

1. 종료 조건 (A Termination Condition)

원치 않는 입력 값이 들어왔을 때 재귀가 계속해서 동작하는 것을 방지하는 안전장치로,
if (원치 않는 입력 값이 들어온다면) {그만}과 같다고 이해할 수 있다.

2. 기본 조건 (A Base Case)

재귀함수가 멈춰야 할 때를 정의해준다는 점에서는 종료 조건과 비슷하지만, 기본 조건은 재귀함수의 목적과 같은 역할을 한다.
if (이것이 일어난다면) {재귀 종료}와 같다고 이해할 수 있다.

3. 재귀 (The Recursion)

함수가 자기자신을 다시 호출하는 부분으로 실제 반복적인 재귀활동이 일어나는 부분이다.

예제

배열 arr의 첫 n개의 요소들을 더한 값을 찾는 재귀함수 sum(arr, n)이 있다. 아래 예제를 위 형식에 따라 나눠보면 다음과 같다.

function sum(arr, n) {
  // 종료 조건
  if (n < 0) return 0;
  
  // 기본 조건
  if (n === 0) return 0;
  
  // 재귀
  return sum(arr, n-1) + arr[n - 1];
}

sum([2, 3, 4, 5], 3) // 9

재귀의 실행

재귀함수에서 가장 핵심이 되는 재귀 부분의 실행 흐름을 살펴보자.
먼저 함수가 동작하면 if문을 넘어 재귀 부분으로 가게 된다.
이때 sum(arr, 3-1)과 arr[3-1]이 더해진 결과를 반환한다.

return sum(arr, 2) + 4;
// 배열 [2, 3, 4, 5]의 첫 2개 요소 + 4;

sum(arr, 2)가 동작하며 if문을 다시 넘어 재귀가 일어난다.
이때 sum(arr, 2-1)을 호출한다.

sum(arr, 1);
// 배열 [2, 3, 4, 5]의 첫 1개 요소;

그리고 다시 한번 sum(arr, 1)이 실행되며 재귀가 일어나 sum(arr, 1-1)을 호출한다.

sum(arr, 0);
// 배열 [2, 3, 4, 5]의 첫 0개 요소;

sum(arr, 0)이 동작할 때, 기본 조건인 (n === 0)을 충족하게 되면서
함수는 0을 반환한다.

if (n === 0) return 0;

이와 같은 순서로 함수가 리턴을 마치게 되면,
가장 내부의 중첩된 함수부터 순차적으로 반환된다.

이처럼 sum([2, 3, 4, 5], 3)은 결국 2 + 3 + 4와 동일해
리턴 값으로 9를 반환하게 되는 것이다.

예제

팩토리얼, n!을 재귀함수로 구현해보자.

function factorial(num) {
  // 종료 조건
  if (num <= 0) return 1;
  // 재귀
  return factorial(num - 1) * num;
}
console.log(factorial(5)); // 120

factorial(5);의 반환값은 120으로,
5! = 1 * 2 * 3 * 4 * 5 = 120의 결과와 동일하다.

for문 ➡️ 재귀함수

아래와 같이 for문으로 작성된 코드는 재귀함수로도 표현 가능하다.
즉, 함수가 자기 자신을 다시 불러올 수 있다면 굳이 반복문을 사용하지 않아도 된다.

function sum(arr, n) {
  var addedValue = 0;
  for (var i=0; i<n; i++) {
    addedValue += arr[i];
  }
  return addedValue;
}

sum(arr, n)은 sum(arr, n-1) + arr[n-1]로 breakdown을 할 수 있다.

function sum(arr, n) {
  if (n <= 0) {
    return 0;
  } else {
    return sum(arr, n-1) + arr[n-1];
  }
}

중요한 것은 n <= 0과 같이 재귀함수는 항상 기본조건(Base Case)를 가져야 한다.
위 if-else문에서는 n <= 0인 경우 0을 반환한다.
n값이 더 큰 경우, n <= 0이 될 때까지 n-1로 다시 자기자신을 호출한다.
이때, 모든 함수의 값이 반환되면서 원래 함수에게 최종적으로 값을 반환해준다.