재귀함수

재귀함수란 ? 

함수 내부에서 자기자신을 호출하는 것.

 

재귀함수 조건

1. Stop condition(base case)
2. Recursive case

모든 재귀함수는 스택오버플로우를 방지하기위해 실행을 종료할 base case를 정의해야한다.

 

재귀단계의 연산을 제대로 설정하지않으면 maximum call stack size exceeded 에러 발생

function drink(x) {
  //1. base case
  if(x < 1) {
    console.log('배불러')
    return;
  }
  //2. recursive case
  drink(--x);
}

drink(5);

 

예제1) 문자열을 뒤집는 함수

function reverse(str){
  //base case
  if(str == ''){
    return ""
  } else {
  //recursive case
    return reverse(str.substr(1)) + str.charAt(0)
  }
}

resverse(hello);

 

예제2) 피보나치 수열

function fib(n){
  //base case: n이 0또는 1일때 n을 반환
  if(n <= 1){
    return n
  } else {
  // recursive case(이전 두 수의 합 반환)
    return fib(n-1) + fib(n-2)
  }
}

fib(5);