[Achievement Goal]

base case 와 recursive case 차이를 알 수 있다.
언제 재귀 함수를 써야 하는지 알 수 있다.
자료 구조 중 Tree 구조에 재귀 함수를 사용하는 이유를 이해할 수 있다.
실생활에 사용 되는 유용한 Tree 구조를 알고 있다.
재귀 함수를 활용하여 모두 순회(traverse)할 수 있다.

1. 재귀함수

재귀함수란 ?

인자가 빈배열이 아닐 경우, 함수 내부에서 자기 자신을 호출하는 것.
재귀함수는 for 과 while 문 같은 반복문의 역할을 한다고 볼 수 있다.
반복할 부분을 함수 단위로 분리하여 특정 조건에 도달할 때까지 반복한다.

재귀함수의 규칙.

재귀함수는 반복문과 같이 쓰이고 자기 자신을 불러일으키는 함수이므로
반드시 특정 조건이 필요하다. 이 조건을 써주지 않으면 무한루프가 돌게 된다.

Base Case

재귀함수를 사용 할 때 재귀의 탈출조건(?) 이라고 생각하면 된다.
재귀함수가 해당 조건을 만족할때까지 계속적으로 돌게 되는데, 이 조건이 없으면 앞서 말했듯이 callstack 에 빠졌다는 오류를 볼 수 있다.

Recursive Case

본격 재귀함수를 쓰는 부분이라고 보면 된다.
recursive case 는 계속 쪼개질 수 있는 경우이며 함수 자기 자신을 조건을 만족할때까지 계속적으로 불러 일으킨다.

ex)

function recursive(n){
  // 조건을 써준다. 
  if(n === 0){
     return 1;
  }
  //재귀함수 
  return n * recursive(n-1)
}

재귀함수는 어떤문제에서 적합할까?

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

예시 1. factorial

factorial 은 주어진 어떤 숫자가 1이되기 전까지 곱해준 값을 의미한다.
!factorial(num) = 5 가 주어졌다면
5 x 4 x 3 x 2 x 1 => 120 이 결과값이 된다.
이것을 재귀함수로 풀어본다면

function factorial(num){
  if(num === 1 ){
    return 1;
  }
  return num * factorial(num-1) 
  //주어진 숫자 num 에서 num 을 1씩 계속적으로 빼준값을 연속해서 곱해준다.
}

예시 1. fibonacchi

피보나치 수열 규칙은 다음과 같다.
0,1 을 제외한 나머지 수는
fib(n) = fib(n-1) + fib(n-2);
이것을 재귀함수로 풀어본다면

function fib(num){
  if(num === 0){
    return 0;
  }else if(num === 1){
    return 1;
  }
  return fib(num-1) + fib(num-2)
  //fib의 num이 0 또는 1이 될때까지 빼는것을 계속적으로 반복한다.
}