CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

1. Junior Member
Join Date
Jul 2011
Posts
6

## Recursive program

why does this program go so slow?

Code:
```#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;
}```

2. Elite Member Power Poster
Join Date
Oct 2007
Location
Seattle, WA
Posts
10,895

## Re: Recursive program

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.

3. Junior Member
Join Date
Jul 2011
Posts
6

## Re: Recursive program

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?

4. ## Re: Recursive program

Originally Posted by 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?
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.

5. Elite Member Power Poster
Join Date
Oct 2007
Location
Seattle, WA
Posts
10,895

## Re: Recursive program

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

Code:
```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:
Code:
```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]```

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•