재귀함수

 

재귀란

원래의 자리로 되돌아가거나 되돌아옴.

 

재귀함수는 자기 자신을 호출하는 함수

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

 

재귀는 언제 사용

 

• 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우
• 중첩된 반복문이 많거나 반복문의 중첩 횟수(number of loops)를 예측하기 어려운 경우

예시)

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);
                           }
                        }
                    }
                }
            }
        }
    }
 }

 

재귀로 문제 해결

1. 문제를 좀 더 작게 .

2. 문제가 더는 작아지지 않을 때까지, 가장 작은 단위.

3. 가장 작은 단위의 문제를 풂으로써 전체 문제를 해결.

 

단,

재귀 함수는 자신을 무한히 연쇄 호출하므로 호출을 멈출 수 있는 탈출 조건을 반드시 만들어야 한다. 탈출 조건이 없는 경우, 함수가 무한 호출되어 stackoverflow 에러가 발생

 

-> base case와 recusive case를 생각해 만든다.

base case : 문제를 더 이상 쪼갤 수 없을 때.

recusive case : 그렇지 않은 경우

 

ex)

// 피보나치 수열
// 피보나치 수는 0과 1로 시작하며, 다음 피보나치 수는 바로 앞의 두 피보나치 수의 합이 된다.
// 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, ...
function fibonacci(n) {
  if (n < 2) return n; // base case
  return fibonacci(n - 1) + fibonacci(n - 2); // recusive case
}

 

// 팩토리얼
// 팩토리얼(계승)은 1부터 자신까지의 모든 양의 정수의 곱이다.
// n! = 1 * 2 * ... * (n-1) * n
function factorial(n) {
  if (n < 2) return 1; // base case
  return factorial(n - 1) * n; // recusive case
}