Recursive program

[t1mu]

why does this program go so slow?

#include<iostream.h>
int fib(int n){
if(n==1 || n==2) return 1;
return fib(n-1)+fib(n-2);
};

void main(){
for(int i=1; i<70; i++)
cout<<" fib("<<i<<") = "<<fib(i)<<endl;
}

[Lindley]

For the same reason the Fibonacci sequence itself grows so fast. An increasingly large number of function calls are required to compute each n. While fib(2) may only require 1 call, fib(7) will require 18 (by my estimate), and so on.

Pretty soon you get to fib(70) requiring thousands of function calls.

[t1mu]

thank you. how can i change it so that it doesnt make the function call thousands of times and just does it extremely fast? do i have to make something static?

[D_Drmmr]

thank you. how can i change it so that it doesnt make the function call thousands of times and just does it extremely fast? do i have to make something static?

Don't recalculate all the Fibonacci numbers whenever you need to know a new one. You could just compute each Fibonacci number in a loop and print it in the same loop, or store them in a vector and print all of them afterwards.

[Lindley]

The solution is to solve bottom-up rather than top-down. For instance, with your current approach, fib(10) is solved as:

Compute fib(9).
    Compute fib(8).
        Compute fib(7).
            Compute fib(6).
                Compute fib(5).
                    Compute fib(4).
                        Compute fib(3).
                            Compute fib(2).
                            Compute fib(1).
                        Compute fib(2).
                    Compute fib(3).
                        Compute fib(2).
                        Compute fib(1).
                Compute fib(4).
                    Compute fib(3).
                        Compute fib(2).
                        Compute fib(1).
                    Compute fib(2).
            Compute fib(5).
                Compute fib(4).
                    Compute fib(3).
                        Compute fib(2).
                        Compute fib(1).
                    Compute fib(2).
                Compute fib(3).
                    Compute fib(2).
                    Compute fib(1).
        Compute fib(6).
            Compute fib(5).
                Compute fib(4).
                    Compute fib(3).
                        Compute fib(2).
                        Compute fib(1).
                    Compute fib(2).
                Compute fib(3).
                    Compute fib(2).
                    Compute fib(1).
            Compute fib(4).
                Compute fib(3).
                    Compute fib(2).
                    Compute fib(1).
                Compute fib(2).
    Compute fib(7).
        Compute fib(6).
            Compute fib(5).
                Compute fib(4).
                    Compute fib(3).
                        Compute fib(2).
                        Compute fib(1).
                    Compute fib(2).
                Compute fib(3).
                    Compute fib(2).
                    Compute fib(1).
            Compute fib(4).
                Compute fib(3).
                    Compute fib(2).
                    Compute fib(1).
                Compute fib(2).
        Compute fib(5).
            Compute fib(4).
                Compute fib(3).
                    Compute fib(2).
                    Compute fib(1).
                Compute fib(2).
            Compute fib(3).
                Compute fib(2).
                Compute fib(1).
Compute fib(8).
    Compute fib(7).
        Compute fib(6).
            Compute fib(5).
                Compute fib(4).
                    Compute fib(3).
                        Compute fib(2).
                        Compute fib(1).
                    Compute fib(2).
                Compute fib(3).
                    Compute fib(2).
                    Compute fib(1).
            Compute fib(4).
                Compute fib(3).
                    Compute fib(2).
                    Compute fib(1).
                Compute fib(2).
        Compute fib(5).
            Compute fib(4).
                Compute fib(3).
                    Compute fib(2).
                    Compute fib(1).
                Compute fib(2).
            Compute fib(3).
                Compute fib(2).
                Compute fib(1).
    Compute fib(6).
        Compute fib(5).
            Compute fib(4).
                Compute fib(3).
                    Compute fib(2).
                    Compute fib(1).
                Compute fib(2).
            Compute fib(3).
                Compute fib(2).
                Compute fib(1).
        Compute fib(4).
            Compute fib(3).
                Compute fib(2).
                Compute fib(1).
            Compute fib(2).

Whereas, you instead store each value as you compute it and then just look them up:

Compute fib(1) and store it to F[0]
Compute fib(2) and store it to F[1]
Compute fib(3) as F[1]+F[0] and store it to F[2]
Compute fib(4) as F[2]+F[1] and store it to F[3]
Compute fib(5) as F[3]+F[2] and store it to F[4]
Compute fib(6) as F[4]+F[3] and store it to F[5]
Compute fib(7) as F[5]+F[4] and store it to F[6]
Compute fib(8) as F[6]+F[5] and store it to F[7]
Compute fib(9) as F[7]+F[6] and store it to F[8]
Compute fib(10) as F[8]+F[7]