재귀 함수

: 자기 자신을 호출하는 함수

function recursion() {
  console.log('This is recursion!');	
  recursion();
}

재귀를 사용하는 경우

1. 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우
2. 중첩된 반복문이 많거나, 반복문의 중첩 횟수를 예측할 수 없는 경우

for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
        for (let k = 0; k < n; k++) {
            for (let l = 0; l < n; l++) {
                for (let m = 0; m < n; m++) {
                	// do something
                    someFunc(i, j, k, l, m);
                }
            }
        }
    }
 }

➡️ 모든 재귀 함수는 반복문으로 표현할 수 있지만, 재귀로 표현하는 경우 더 간결하고 이해하기 쉽다.

재귀 함수 만드는 법

• recursive case : 자신을 호출하는 함수(재귀 함수)를 포함하는 경우
• base case : 더 이상 나눌 수 없는 경우로, 재귀 함수의 탈출 조건을 작성한다.
  (재귀 호출이 멈추는 조건)

예시 1) sumTo

숫자를 입력 받아 1부터 숫자까지의 합을 리턴하는 함수

function sumTo(num) {
...
}

recursive case

num === 5이라고 가정했을 때, sumTo(5)을 풀어서 작성해보면...

sumTo(5) = 5 + 4 + 3 + 2 + 1 + 0

위의 코드를 아래처럼 재귀함수로 표현할 수 있다.

sumTo(5) = 5 + sumTo(4)
sumTo(4) = 4 + sumTo(3)
sumTo(3) = 3 + sumTo(2)
sumTo(2) = 2 + sumTo(1)
sumTo(1) = 1 + sumTo(0)

=> sumTo(num) = num + sumTo(num - 1)

base case

sumTo(0) 더 이상 나눌 수 없으므로, 따라서 num === 0이 되는 경우가 탈출 조건이 된다.

sumTo(5) = 5 + (4 + (3 + (2 + (1 + sumTo(0)))))

// num === 0이 될 때, 0을 리턴하여 탈출한다.
sumTo(5) = 5 + (4 + (3 + (2 + (1 + 0)))) // 15

이렇게 구한 recursive case와 base case를 조건문 안에 작성해보자.

function sumTo(num) {
  
  // base case : num이 0이 되면, 0을 리턴한다.
  if(num === 0) {
    return 0;
  }
  
  // recursive case : num이 0이 아닌 경우, sumTo(num - 1)을 호출한다.
  return num + sumTo(num - 1);
}

예시 2) Factorial

숫자를 입력 받아 1부터 숫자까지의 곱을 리턴하는 함수

function factorial(num) {
  
  // base case : factorial(0) = 1
  if(num === 1) {
    return 1;
  }
  
  // recursive case
  return num * factorial(num - 1);
}

예시 3) arrSum

숫자를 요소로 가지는 배열을 입력 받아 모든 요소의 합을 리턴하는 함수

function arrSum(arr) {
  
  // base case
  if(arr.length === 0) {
    return 0;
  }
  
  // recursive case
  return arr[0] + arrSum(arr.slice(1));
}

❔ 학습 후 궁금한 점

• 재귀 함수와 메모리 사용량 간의 관계 (javascript recursion memory leak)
• 꼬리 재귀 (tail recursion in js)
• 하노이의 탑 재귀 (js tower of hanoi in recursion)
• 조합 재귀 함수 (js combination in recursion)