재귀야? 네! 재귀야? 네!

앞서 재귀함수란 특정 조건이 만족할 때까지 자기 자신을 호출하는 함수를 뜻한다는 것을 알았다.
즉 자기가 호출하고 자기가 응답하는 셈이다.

이번 시간엔 재귀함수의 조건과 재귀함수를 왜 그리고 언제 사용해야 하는지, 재귀함수의 주의점, 그리고 대표적인 재귀함수 예제에 대해 알아보자.

이 글은 JavaScript 알고리즘 & 자료구조 마스터클래스를 참고하여 작성되었습니다.

01. 재귀함수의 조건

1. 탈출 조건(Base Case)

재귀 함수는 특정 조건을 만족할 때까지 스스로를 계속 호출하기 때문에 반드시 탈출 조건이 필요하다.

2. 재귀 함수의 매개변수 값(Different Input Value)

매 재귀함수를 호출할 때마다 다른 매개변수를 전달해야 한다. 매번 같은 매개변수 값을 전달하는 것은 같은 작업을 무한 번 반복하는 셈이기 때문이다.

02. 재귀함수은 왜 그리고 언제 사용할까?

Why 왜?

모든 재귀 함수는 동일한 작은 단위의 처리를 반복해서 처리하기 때문에 for문이나 while문으로도 충분히 표현 가능하다. 그런데도 왜 재귀함수를 써야 할까?
→ 재귀함수를 사용하면 보다 간결하고 가독성 좋은 코드 작성이 가능하다는 장점이 있다.

재귀함수로 작성할 때

function arrSum(arr) {  
  if(arr.length === 0) {
  	return 0
  }
  return arr.shift() + arrSum(arr);
}

for문으로 작성할 때

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++) {
                    for (let n = 0; n < n; n++) {
                        for (let o = 0; o < n; o++) {
                            for (let p = 0; p < n; p++) {
                                // do something
                                someFunc(i, j, k, l, m, n, o, p);
                           }
                        }
                    }
                }
            }
        }
    }
 }

When 언제?

1. 주어진 문제의 로직이 비슷하고, 더 작은 단위로 나눌 수 있는 경우
2. 중첩된 반복문이 많거나 반복 횟수를 예측하기 어려운 경우

03. 재귀 함수의 주의점

Stack Overflow Error

• 재귀함수는 값이 리턴되어 제거되기 전까지 Call Stack에 쌓여 메모리를 차지하기 때문에 메모리를 비효율적으로 사용할 수 있다.
• 특히 재귀 함수를 너무 많이 호출하게 되면 스택 오버플로우가 발생하여 프로그램이 중지되거나 오류가 발생할 수 있어 적절한 적절한 탈출 조건을 작성하는 등 사용에 주의가 필요하다.

가독성 저하

• 반복되는 로직이나 리턴되는 값을 예측하기 어렵다면 오히려 가독성을 떨어뜨릴 수 있다.
• 따라서 문제에 따라 재귀함수 또는 반복문을 적절히 선택하는 것이 좋다.

04. 대표적인 재귀 문제

1. Power

Math.pow()을 모방하여 두 개의 수를 변수로 받아 첫 번째 수는 밑, 두 번째 수는 지수가 되어 밑의 거듭제곱을 지수로 반환하는 함수

function power(base, exponent) {
  if (exponent === 0) return 1;
  return base * power(base, exponent - 1);
}

console.log(power(2, 2)); // 4
console.log(power(2, 0)); // 1
console.log(power(2, 4)); // 16

1. power 함수는 밑 * power 함수를 한 값을 리턴한다.
2. 재귀 함수인 power의 인자로는 base와 exponent-1한 값이 연속적으로 주어지며, 탈출 조건은 exponent가 0이 될 때로, 이때 1을 리턴한다.

2. Factorial

숫자를 받아 해당 숫자의 계승(팩토리얼)을 반환하는 팩토리얼 함수

function factorial(n) {
  if (n === 1 || n === 0) return 1;
  return n * factorial(n - 1);
}

console.log(factorial(2)); // 2
console.log(factorial(4)); // 24
console.log(factorial(7)); // 5040

1. factorial 함수는 n * factorial 함수를 한 값을 리턴한다.
2. 재귀 함수인 factorial의 인자로는 n-1한 값이 연속적으로 주어지며, 탈출조건은 n이 1 또는 0일 때이다.

3.ProductOfArray

숫자 배열을 받아 모든 숫자의 곱을 반환하는 함수

function productOfArray(arr) {
  if (arr.length === 0) return 1;
  return arr[0] * productOfArray(arr.slice(1));
}

console.log(productOfArray([1, 2, 3])); // 6
console.log(productOfArray([1, 2, 3, 10])); // 60

1. productOfArray는 arr의 첫번째 요소 * productOfArray 함수 값을 리턴한다.
2. 재귀 함수인 productOfArray의 인자로는 arr의 0번째 요소를 제외한 값이 연속적으로 주어지며, 탈출 조건은 해당 배열의 길이가 0이 될 때이다.

4. RecursiveRange

0부터 전달된 숫자까지의 모든 합을 더하는 함수

function recursiveRange(n) {
  if (n === 0) return 0;
  return n + recursiveRange(n - 1);
}

console.log(recursiveRange(6)); // 21
console.log(recursiveRange(10)); // 55

1. recursiveRange는 n + recursiveRange값을 리턴한다.
2. 재귀함수인 recursiveRange의 인자로는 n-1한 값이 연속적으로 주어지며, 탈출조건은 n이 0이 될 때이다.

5. Fib

숫자를 받아 피보나치 수열의 n번째 숫자를 반환하는 함수

function fib(n) {
  if (n <= 2) return 1;
  return fib(n - 1) + fib(n - 2);
}

console.log(fib(4)); // 3
console.log(fib(10)); // 55
console.log(fib(28)); // 317811
console.log(fib(35)); // 9227465

fib는 fib(n - 1) + fib(n - 2)값을 리턴하며 탈출 조건은 n이 2와 같거나 작을 때이다.

💡 3줄 정리

1. 재귀 함수는 재귀를 멈추는 탈출 조건을 필수로 갖추어야 하며, 매 호출 때마다 다른 매개변수를 전달한다.
2. 재귀 함수는 중첩된 반복문이 많거나 반복을 예측하기 어려울 때 유용하다.
3. 적절한 탈출 조건을 작성하지 않으면 스택 오버플로우가 발생할 수 있고, 리턴되는 값을 예측하기 어려울 수 있으니 사용에 주의해야 한다.