8월 25일 (수) 재귀의 흐름(피보나치)

남이섬·2021년 8월 25일

TIL

피보나치는

피보나치 나무위키

위와 같이 피보나치에 대한 정의를 보면 좀 복잡할 수 있다.

간단하게 피보나치 수열은 첫번째 수와 두번째 수를 더한 값이 세번째 수이다.

f(0) = 0, f(1) = 1, f(n + 2) = f(n + 1) + f(n)
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

f(n + 2 - 2) = f(n + 1 - 2) + f(n - 2)
f(n) = f(n - 1) + f(n - 2) // 재정의

피보나치 수열 반복문형태

function fibonacci(n) {

    if (n == 0) return 0; // 제 0항은 0을 반환한다.
    else if (n == 1) return 1; // 제 1항은 1을 반환한다.
    else {
    
        let result = 0;
        let iterA = 0, iterB = 1
        
        for (let i = 2; i <= n; i++) {
            result = A + B;
            A = B;
            B = result;
        } // n항의 값을 구한다.
        return result;
    }
}

반복문 흐름

fibonacci(5)

function fibonacci(5) {

    if (n == 0) return 0; 
    else if (n == 1) return 1; 
    else {
    
        let result = 0;
        let A = 0, B = 1
        
        for (let i = 2; i <= 5; i++) {
            result = A + B;
            A = B;
            B = result;
        return result;
    }
}

n(5)까지 반복

        let result = 0;
        let A = 0, B = 1
        
        for (let i = 2; i <= 5; i++) {
            result = A + B;
            A = B;
            B = result;
        return result;
    }

i = 2

result = 0 + 1 (1)
A = 1
B = 1

i = 3

result = 1 + 1 (2)
A = 1
B = 2

i = 4

result = 1 + 2 (3)
A = 2
B = 3

i = 5

result = 2 + 3 (5)
A = 3
B = 5

function fibonacci(5) {

    if (n == 0) return 0; 
    else if (n == 1) return 1; 
    else {
    
        let result = 0;
        let A = 0, B = 1
        
        for (let i = 2; i <= 5; i++) {
            result = 2 + 3;
            A = 3;
            B = 5;
        return 5;
    }
}

return value 5;

반복문으로 피보나치 배열 구하기

function fibonacci(n) {
  let arr = [0, 1];
  for (let i = 2; i <= n; i++) {
    arr.push((arr[i - 1] + arr[i - 2]));
  }
  return arr;
}

피보나치의 특성상 3번째 수를 구하기 위해선 첫번째, 두번째 수를 배열에 할당을 해준다.
arr 배열에 현재 수를 넣어 준다
f(n) = f(n - 1) + f(n - 2)
현재수 = 전의 수 + 전전의 수

피보나치 재귀함수 흐름

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

resursive case에서 재귀함수가 2개로 조금 복잡한 구조로 재귀 흐름이 진행 된다.

fibonacci(5)

  return fibonacci(num - 1) + fibonacci(num - 2)

return fibonacci(5 - 1)
       fibonacci(4)

fibonacci(4)

return fibonacci(4 - 1)
       figonacci(3)

fibonacci(3)

return fibonacci(3 - 1)
       fibonacci(2)

fibonacci(2)

return fibonacci(2 - 1)

fibonacci(1)

function fibonacci(1) {

  if(1 === 1) {
    return 1 //
  }

  return fibonacci(num - 1) + fibonacci(num - 2)

return value 1;
fibonacci(1) = 1

fibonacci(2) // 두번째 재귀

return fibonacci(2 - 2) // 두번째 재귀

  if (0 === 0) {
    return 0 //
  }

return value 0;
fibonacci(0) = 0

첫번째 값

return fibonacci(2 - 1) + fibonacci(2 - 2)
    // fibonacci(1) + fibonacci(0)
    //     1        +       0  =  1

return value 1;

fibonacci(1) = 1

여기서 부터 펼쳐 놓은 재귀함수를 다시 거꾸로 올라간다.

fibonacci(2) // return value = 1

return fibonacci(1) + fibonacci(2 - 2)
                      fibonacci(0)
    //       1      +       0  =  1

fibonacci(3) // return value = 2

return fibonacci(2) + fibonacci(3 - 2) // 두번째 재귀
    //      1       + fibonacci(1) // 두번째 재귀 return value 1
            1       +      1  =  2

fibonacci(4)

return fibonacci(3) + fibonacci(4 - 2) // 두번째 재귀

fibonacci(4)의 두번째 재귀
fibonacci(2)

return fibonacci(2 - 1) + fibonacci(n - 2) // 첫번째 재귀

fibonacci(2)의 첫번째 재귀

return fibonacci(1) + fibonacci(n - 2) // 첫번째 재귀
    //      1

fibonacci(1) // return value = 1

fibonacci(2)의 두번째 재귀

return fibonacci(1) + fibonacci(2 - 2) // 두번째 재귀
    //      1       +       0  =  1

return value = 2

fibonacci(4)

return fibonacci(3) + fibonacci(4 - 2)
                      fibonacci(2)
                      return fibonacci(2 -1) + fibonacci(n - 2)
                             fibonacci(1)
                                  1
    //      2      +         1  =  3

fibonacci(4) // return value = 3

fibonacci(5)

return fibonacci(4) + fibonacci(5 - 2) // 두번째 재귀

fibonacci(5)의 두번째 재귀
fibonacci(3)

fibonacci(3)의 첫번째 재귀

return fibonacci(3 - 1) + fibonacci(n - 2) // 첫번째 재귀

fibonacci(2)의 첫번째 재귀

return fibonacci(2 - 1) + fibonacci(n - 2) // 첫번째 재귀

fibonacci(1) // return value 1;

fibonacci(2)의 두번째 재귀

return fibonacci(1) + fibonacci(2 - 2) // 첫번째 재귀 + 두번째 재귀
    //      1       + fibonacci(0)
    //.     1       +      0  =  1

fibonacci(2) // return value 1;

fibonacci(3)의 두번째 재귀

return fibonacci(2) + fibonacci(3 - 2) // 첫번째 재귀 + 두번째 재귀
    //       1      + fibonacci(1)     
             1      +      1  =  2

fibonacci(3) // return value 2;

fibonacci(5)

return fibonacci(4) + fibonacci(5 - 2)
            3       +        2  
                      fibonacci(3)
                            2
                      return fibonacci(3 -1) + fibonacci(n - 2)
                                               return fibonacci(3 - 2)
                                                      fibonacci(1)
                                                            1
                             fibonacci(2)
                                  1
                                  1         +        1  =  2