-
July 27th, 2011, 08:44 AM
#1
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;
}
-
July 27th, 2011, 08:52 AM
#2
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.
-
July 27th, 2011, 09:02 AM
#3
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?
-
July 27th, 2011, 09:18 AM
#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.
Cheers, D Drmmr
Please put [code][/code] tags around your code to preserve indentation and make it more readable.
As long as man ascribes to himself what is merely a posibility, he will not work for the attainment of it. - P. D. Ouspensky
-
July 27th, 2011, 10:42 AM
#5
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
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|