[Recursion] Febonacci - Why recursion is not always good

 

Fibonacci Sequence – recursion and “Gotcha”

 

if n>1

→ F(n) = F(n-1) + F(n-2)

if n=0, 1

→ F(n) = n

 

 

 

 

예제1)

#include<iostream>

using namespace std;

int Fib(int n) {

            if(n<=1) {

                        return n;

            }

            int F1, F2, F;

            F1 = 0;

            F2 = 1;

           

            for(int i=2; i<=n; i++) {

                        F = F1+F2;

                        F1 = F2;

                        F2 = F;

}

return F;

}

 

int main() {

            int n;

            cout<<”Give me an n: ”;

            cin>>n;

            int result = Fib(n);

            cout<<result;

}

 

실행 결과1)

Give me an n: 6
8

 

실행 결과2)

Give me an n: 40
102334155

 

 

예제2)

#include<iostream>

using namespace std;

int Fib(int n) {

            if(n<=1) {

                        return n;

            }

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

}

 

int main() {

            int n;

            cout<<”Give me an n: ”;

            cin>>n;

            int result = Fib(n);

            cout<<result;

}

 

실행 결과1)

Give me an n: 6
8

 

실행 결과2)

Give me an n: 40
102334155

 

 

예제 1보다 예제2가 더 오래 걸림

왜 그럴까?

 

Albert의 경우 Iterative로, 딱 한 번씩만 작업하는 반면

Pinto의 경우 Recursive하게 처리하는데, 같은 작업이 중복되어 처리 속도가 느려지는 것이다.

 

 

 

 

↓ 참고 사이트

https://www.youtube.com/watch?v=GM9sA5PtznY&list=PL2_aWCzGMAwLz3g66WrxFGSXvSsvyfzCO&index=2