CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 5 of 5
  1. #1
    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. #2
    Lindley is offline 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. #3
    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. #4
    Join Date
    Jul 2005
    Location
    Netherlands
    Posts
    2,042

    Re: Recursive program

    Quote Originally Posted by t1mu View Post
    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

  5. #5
    Lindley is offline 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
  •  





Click Here to Expand Forum to Full Width

Featured