알고리즘 관련문제를 풀던 도중 피보나치 수열중 n번째 항의 수를 리턴해야 하는 문제가 나왔다.

피보나치수열

0번째 피보나치수는 0, 1번째 피보나치수를 1로주고 두번째 피보나치 수 부터는 바로 직전의 피보나치 수의 합을 더한것을 의미함

즉 n=2부터는 n= (n-1) + (n-2)를 의미힌다.

처음으로 문제를 접하였을때 재귀함수를 이용해 답을 하기와 같이 도출하였다.

재귀함수를 이용한 피보나치

//재귀함수를 이용한 풀이
function fibonacci (n) {

  //base case
  if(n===1){
   return 1
  }
  
  if(n ===0) {
   return 0
  }
  
  //recursive case
  return fibonacci(n-2)+fibonacci(n-1)
  

}

위 코드도 물론 틀린답은 아니지만..
100번째 피보나치 수가 무엇인지 물어보는 fibonacci (100)을 하는 순간 브라우저가 멈춰버렸다..
물론 이렇다 보니 테스트 또한 시간초과로 통과하지 못하였다..

왜 시간초과가 되는지 찾아보니.. 함수가 너무많이 호출되서 컴퓨터가 뻗어 버린것이라고 한다.
console창에 fibonacci(10)까지는 무난하게 작동하는 것을 확인하였다.

컴퓨터가 뻗어버리는 것을 방지하기 위해 꼬리 재귀를 사용해서 문제를 풀어야 한다.

꼬리 재귀 (Tail Recursion)

재귀 호출이 끝나면 아무 일도 하지 않고 결과만 바로 반환되도록 하는 방법
이 방식을 사용하게 되면 이전 함수의 상태를 유지하지 않고 추가 연산을 하지 않기 때문에 스택이 넘쳐나는 문제를 해결할 수 있다.
꼬리 재귀를 사용할 경우 return문에 함수이외의 연산자나 값을 사용하면 안됨. 사용하게 되면 꼬리 재귀가 아니고 일반 재귀가 되어 버림.

꼬리 재귀를 이용한 피보나치

function fibonacci(n ,  prevFibo = 1, twowPrevFibo = 0) {
  //base case
  if(n===0){
    return twowPrevFibo
  }

  if(n===1){
    return prevFibo
  }

  //피보나치에 값을 넣는방법
  let = currentFibo=prevFibo+ twowPrevFibo  
  twowPrevFibo = prevFibo    
  prevFibo = currentFibo  


 //recursive case
  return fibonacci(n - 1, prevFibo, twowPrevFibo);
                                   
}

//n==5라고 했을경우
// n=5 cur 1 pre 1 two 1
// n=4 cur 2 pre 2 two 1
// n=3 cur 3 pre 3 two 2
// n=2 cur 5 pre 5 two 3
//그이후 n이 1이 되면서 if(n==1){return prevFibo로 인해 5가 리턴}

for문을 이용한 피보나치 풀이

function fibonacciLoop(n) {
    let currentFibo
    let previousFibo = 1 
    let previousPreviousFibo = 0;
    if (n < 2){
    	return n;
    }
        
    for ( let i = 2 ; i <= n ; i++ ) {
        // 이번 반복의 피보나치 수를 구하고
        currentFibo = previousFibo + previousPreviousFibo;

        // 다음번 반복을 위해 앞의 피보나치 수를 앞의앞의 피보나치 수로 한 칸 미루고
        previousPreviousFibo = previousFibo;

        // 다음번 반복을 위해 현재의 피보나치 수를 앞의 피보나치 수로 한 칸 미룬다.
        previousFibo = currentFibo;
    }
    return currentFibo;
}

---

참조
https://homoefficio.github.io/2015/07/27/%EC%9E%AC%EA%B7%80-%EB%B0%98%EB%B3%B5-Tail-Recursion/