피보나치 수열 C++

재귀 함수?

Re(int n)

{

if(n==0)

return 0;

return n + Re(n-1);

}

피보나치 점화식 : 

$$F_0=0, \ F_1=1, \ F_{n+2}=F_{n+1}+F_{n}

피보나치 방법 2개있지 않나 ? 순환? 재귀 ?

피보나치는 F(0) = 0, F(1) = 1일 때, 2 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 점화식

• f(1) = f(2) = 1

• f(n) = f(n-1) + f(n-2)

if (n==0)=> 0

if (n==1)=>  1

if (n==2)=>  1

int fibo( int n)

{

if(n == 0)

return 0;

if( n==1)

return 1;

else

return fibo(n-1) + fibo(n-2);

}

function fibonacci(n) {
    if (n < 2)
        return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

재귀 니까 -> 좀 메모리 과부화 

좋은 글 : 

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