자기 자신을 부르는 함수를 재귀함수라고 한다.
많은 연산을 필요로 하는 프로세스를 짤 때
시간복잡도에서 중요하게 보는 n의 단위를 작게 만들어,
프로세스의 실행 시간과 횟수를 효율적으로 만들 수 있다.

이는 곧 stackOverflow에 도달하지 않는 것을 목표로 한다고 볼수 있다.

---

콜 스택

함수는 호출시 콜 스택 이라는 곳에 stack으로 쌓이기 시작한다.
처음 호출시 쌓이기 시작해, 함수가 끝날 때 까지 쌓여,
실행되기 시작하는 함수부터 처음 쌓인 함수까지 실행된다.
실행이 될때마다 함수는 콜 스택에서 빠져나가는 것이다.
알고리즘 작성시, 재귀적으로 표현하여 호출 하는것이 자연스러울때
재귀함수를 쓰게 된다.

그러나, 재귀함수는 콜 스택의 메모리를 많이 잡아먹으므로,
stackOverflow가 발생하지 않는 한계선까지 사용을 해야한다.

---

재귀함수

함수 안에서 함수를 호출

function yoon(n) {
  if (n <= 1) {
    console.log('마지막 스택 n은 ' +n)
    return 1 // 조건 만족시 반환할 return값
  } else {
    let answer = yoon(n - 1)
    console.log('n은 ' + n)
    console.log(n + answer)
    return n + answer // yoon(n) 함수 안에서 yoon(n-1) 함수를 호출
  }
}
console.log(yoon(5));

함수 yoon에 파라미터(5)를 넣을시,
최초 n = 5 부터 if문을 시작하게 된다.

if (n <= 1) // false

false 실행 문구에서

return n + yoon(n-1)

파라미터(5)에 함수 yoon(n-1)의 반환값을 더해줘서
return하고 함수yoon(n)을 마쳐야 한다....

return 5 + yoon(5-1)

그러나

return n + yoon(n-1)

함수 yoon(n-1)의 반환값이 연산되지 않았으므로
컴퓨터는 함수 yoon(n)을 연산하기 위해 본인의 함수 yoon(n-1)을 연산하게 된다.

동시에

return이 예약(?) 되었으므로 콜 스택의 첫번째 블럭을채우게 된다.

return 5 + yoon(5-1)

이제 function yoon(4) {를 연산하기 시작한다.

n이 4이므로 false가 나오고

return 4 + yoon(4-1)

마찬가지로 콜 스택의 두번째 블럭을 채우고,

yoon(4-1)을 반환하기 위한 function yoon(3)을 연산하기 시작.

그리고 반복

return 3 + yoon(3-1)

return 2 + yoon(2-1)

콜 스택은 꾸준히 쌓여

밑에서 부터

return 2 + yoon(2-1)
return 3 + yoon(3-1)
return 4 + yoon(4-1)
return 5 + yoon(5-1)

4번째 블럭까지 채우게 된다.

function yoon(1)

이제 if조건문 n <= 1을 만족(true)하였고,

return 1 1을 반환한다.

function yoon(2-1)의 return값이 1이 반환되었다.

이제 컴퓨터는

return 2 + yoon(2-1)을 연산할 수 있다.

첫번째 블럭 return 2 + 1을 연산하여 3을 반환했다.

이는 곧

두번째 블럭 yoon(3-1)의 반환값 이므로

return 3 + yoon(3-1)도 연산이 가능해진다.

이제 최초로 추가된 블럭까지 pop한다.

return 3 + yoon(3-1) // 3+3 = 6
return 4 + yoon(4-1) // 4+6 = 10
return 5 + yoon(5-1) // 10+5 = 15

첫번째 블럭 함수의 리턴값은

function yoon(5) // 파라미터로 받은 값 n=5

15였으니, 반환되며 pop된다.

console.log(yoon(5)) // 15

15가 출력값으로 콘솔에 찍히게 된다.

메모이제이션

다이나믹 프로그래밍으로 대표되는 피보나치 수열 프로세스는
시간복잡도 n*n으로 작성시 콜 스택을 굉장히 많이 차지하게되는 문제가 생긴다.
이는 콜 스택이 무거워 짐을 뜻하고, 연산이 느려짐을 말한다.

다음 시간에는 피보나치 수열 프로세스를 작성하면서
콜 스택 공간을 절약하는 방법을 알아보자.

return fibo2(n) {
  if(n == i || n==2) {
    return 1
  }
  return fibo2(n-1) + fibo2(n-2)
}

let number = [1,1]
return fibo3(n) {
  if(number[n-1] > 0) {
    return 1
  } else if (number[n-1] > 0) {
    return number[n-1]
  } else {
    return fubo3(n-1) + fibo3(n-2)
  }
}