[JS] 재귀함수

재귀함수

함수가 자신을 다시 호출하는 구조로 만들어진 함수이다. 재귀함수는 종료조건이 있어야 하며, 종료조건을 설정해주지 않으면 무한 반복을 하게된다. 재귀함수로 작성이 되는 코드는 반복문으로도 작성할 수 있다.

---

예시1)

<1부터 100의 합 구하기>

반복문

let result = 0;
for (let i = 1; i < 101; i++) {
  result += i
};

console.log(result); // 5050

재귀함수

function result(n) {
  if (n <= 1) {  //base case
    return 1
  }
  return n + result(n - 1);  //recursive case
}

console.log(result(100)); // 5050

// 순번   f(n)       return       최종
// 1   f(100)    100 + f(99)  100+99+98+97+96+95+94..+2+1   
// 2   f(99)     99 + f(98)   99+98+97+96+95+94..+2+1 
// 3   f(98)     98 + f(97)   98+97+96+95+94..+2+1 
// 4   f(97)     97 + f(96)   97+96+95+94..+2+1 
// ...
// ... f(2)      2 + f(1)     2+1
// ... f(1)         1    return값이 자기 자신을 호출하지 않는 상황

---

예시2)

<피보나치 수열>

반복문

function fibonacci(n) {
  if (n <= 2) {
    return 1;  //2번째까지의 값은 1이므로 1을 리턴
  }
  
  let i = 1
  let num1 = 0;
  let num2 = 1;
  let result;
  
  while(i < n) {  //숫자 n이 될때까지 반복
    result = num1 + num2;
    num1 = num2;
    num2 = result;
    i++;
  }
  return result;
}

재귀함수

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