재귀 함수(recursion)

 

재귀: 함수를 스스로 호출하는 것

function foo(){
  foo();
  }

 

대표적인 예시는 !(팩토리얼)이다.

 

function factorial(n){
  if(n === 0){// ** 재귀는 무한 반복을 방지하기 위해 반드시 탈출 조건이 있어야 한다!!! **
    return 1;
  }
  return n * factirial(n - 1);
}

 

기본적으로 반복문이므로, 모든 재귀는 반복문으로 표현할 수도 있다.

 

function factorial(n){
  let result = 1;
  for(let i = n; i > 0; i--){
    result = result * i;
  }
  return result;
}

 

대표적인 두 번째 예시는 피보나치 수열 이 있다.

 

피보나치 수열이란?

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

앞의 두 숫자를 합쳐서 다음 숫자를 만들어주는 수열이다.

//fib의 n번째 엘리먼트를 구하기 위해서는?
function fib(n){
    if(n === 0){
        return 0;
    } else if(n === 1){
        return 1;
    } else {
 return fib(n-1) + fib(n-2)
}
}

fib(5); //--> 5
fib(6); //--> 8