Search

7.10 — Recursion

A recursive function in C++ is a function that calls itself. Here is an example of a poorly-written recursive function:

When CountDown(10) is called, the number 10 is printed, and CountDown(9) is called. CountDown(9) prints 9 and calls CountDown(8). CountDown(8) prints 8 and calls CountDown(7). The sequence of CountDown(n) calling CountDown(n-1) is continually repeated, effectively forming the recursive equivalent of an infinite loop.

In the lesson on the stack and the heap, you learned that every function call causes data to be placed on the call stack. Because the CountDown() function never returns (it just calls CountDown() again), this information is never being popped off the stack! Consequently, at some point, the computer will run out of stack memory, stack overflow will result, and the program will crash or terminate. On the authors machine, this program counted down to -11732 before terminating!

This program illustrates the most important point about recursive functions: you must include a termination condition, or they will run “forever” (or until the call stack runs out of memory).

Stopping a recursive function generally involves using an if statement. Here is our function redesigned with a termination condition:

Now when we run our program, CountDown() will count down to 0 and then stop!

Let’s take a look at another recursive function that is slightly more useful:

Recursive programs can often be hard to figure out just by looking at them. It’s often instructive to see what happens when we call a recursive function with a particular value. So let’s see what happens when we call this function with nValue = 5.

SumTo(5) called, 5 <= 1 is false, so we return SumTo(4) + 5. SumTo(4) called, 4 <= 1 is false, so we return SumTo(3) + 4. SumTo(3) called, 3 <= 1 is false, so we return SumTo(2) + 3. SumTo(2) called, 2 <= 1 is false, so we return SumTo(1) + 2. SumTo(1) called, 1 <= 1 is true, so we return 1. This is the termination condition. Now we unwind the call stack (popping each function off the call stack as it returns): SumTo(1) returns 1. SumTo(2) returns SumTo(1) + 2, which is 1 + 2 = 3. SumTo(3) returns SumTo(2) + 3, which is 3 + 3 = 6. SumTo(4) returns SumTo(3) + 4, which is 6 + 4 = 10. SumTo(5) returns SumTo(4) + 5, which is 10 + 5 = 15. Consequently, SumTo(5) returns 15. One question that is often asked about recursive functions is, "Why use a recursive function if you can do many of the same tasks iteratively (using a for loop or while loop)?”. It turns out that you can always solve a recursive problem iteratively -- however, for non-trivial problems, the recursive version is often much simpler to write (and read).

Fibonacci numbers

One of the most famous mathematical recursive algorithms is the Fibonacci sequence, as Fibonacci sequences appear in many places in nature, such as branching of trees, the spiral of shells, the fruitlets of a pineapple, an uncurling fern frond, and the arrangement of a pine cone.

Here is a picture of a Fibonacci spiral:

Each of the Fibonacci numbers is the length of the side of the square that the number appears in.

Fibonacci numbers are defined mathematically as:

F(n) = 0 if n = 0
1 if n = 1
f(n-1) + f(n-2) if n > 1

Consequently, it’s rather simple to write a recursive function to calculate the nth Fibonacci number:

Running the program produces the following result:

0 1 1 2 3 5 8 13 21 34 55 89 144

Which you will note are exactly the numbers that appear in the Fibonacci spiral diagram.

While it’s possible to write the Fibonacci function iteratively, it’s much more difficult!

7.12 -- Handling errors (assert, cerr, exit, and exceptions)
Index
7.9 -- The stack and the heap

41 comments to 7.10 — Recursion

  • Tom

    I try to include Fibonacci in my diet every morning.

  • sherrellbc

    Although the Fibonacci recursive implementation tends to be how the idea of recursion is introduced, the recursive implementation has extremely poor run-time efficiency compared to the iterative approach - think big-O. Many of the necessary calculations are computed repeatedly and it is therefore redundant. Formulate a recursion tree for the algorithm and prove it to yourself.

  • ahrramin

    Here is my iterative Fibonacci program =) :


    #include <iostream>

    using namespace std;

    int Fibonacci(int x)
    {
    int fibBack2 = 0;
    int fibBack1 = 1;
    int fibNow = 0;
    for(int iii=0; iii < x; iii++)
    {
    if(iii == 0)
    fibNow = 0;
    else if(iii == 1)
    fibNow = 1;
    else
    fibNow = ((fibBack1) + (fibBack2));
    cout << fibNow << " ";
    fibBack2 = fibBack1;
    fibBack1 = fibNow;
    }

    }

    int main()
    {
    int x;
    cin >> x;
    cout << Fibonacci(x) << endl;

    return 0;
    }

  • panqnik

    Hey there,
    Very useful post! I would like to invite you to visit my blog as well, and read my latest post about sequence points in C and C++.

    http://blog.panqnik.pl/dev/sequence-points-in-c-cpp/

    Best regards,
    panqnik

  • DrSuse

    Check out my Fibonacci algorithm. I can barely figure out how I did this!
    #include <iostream>

    using namespace std;
    int nFibarray[3];
    int nLimit;
    int main()
    {
    cout << "Display Fibonacci numbers up to what number? ";
    cin >> nLimit;

    for (*(nFibarray+2) = 1; *(nFibarray + 1) <= nLimit; *(nFibarray+2) = *nFibarray + *(nFibarray + 1) )
    {

    cout << *(nFibarray + 1) << " " ;

    *nFibarray = *(nFibarray + 1);
    *(nFibarray + 1) = *(nFibarray + 2);

    }

    return 0;
    }

  • abdelones

    hi every one i hope you can help me with this i found this countdown code in C
    ******************************
    void countdown(int n)
    {
    if (n<10)
    {
    countdown()(n+1);
    printf("%d\n", n);
    }

    }

    void main()
    {
    countdown()(1);
    getch();

    }
    *********************************
    when it's done we can saw countdown printed like that
    9
    8
    7
    .
    .
    .
    the problem is that i just can't understand how it works and why it print last numbers in the first place ? seek_help ;)

  • mael

    #include

    using std::cout;
    using std::cin;
    int main()
    {
    double nOld(0), nNew(1), nSum(0), nThfibo;
    cout << "Numbers above the 30th, loose precision so \n";
    cout << "the 29th and the 30th numbers are 514,229 and 832,040 maybe you should go manual from there \n \n";
    cout <> nThfibo;

    int iii = 1;
    while (iii < nThfibo)
    {
    nSum = nOld + nNew;
    nOld = nNew;
    nNew = nSum;
    iii++;
    }
    cout << nSum << " is the " << nThfibo << "th Fibonacci number.\n";

    cin.clear();
    cin.ignore(255, '\n');
    cin.get();
    return 0;
    }
    Faster way to get the Fibbo you want?
    but above 30th number you loose precision anyway to fix it??
    Greate site :)

  • clementl

    My pc stopped at -130146. Facinating!

  • Dr. HaXX

    "On the authors machine, this program counted down to -11732 before terminating!"
    Then you must have quite some stack memory, my computer stopped counting at -4607 xD

    "Hahaha… apparently Linux doesn’t believe in stack overflows.
    I ran your stack overflowing program and it just kept going all the way past -4,000,000, when I stopped it."

    Lmao, apparently you have infinite stack memory on your pc :P

    • Nelson Jenkins

      Probably related to the compiler and your RAM, or maybe even the byte size of your operating system (I hit -130,146 before crashing, just like clementl below me, and I've got 12 GB of RAM using Dev-C++ on Windows 7 64-bit). Perhaps the compiler Quinn used had some kind of fancy dynamic/large stack, unless he has a few TB of RAM.

      Fun to test, though. Someone should make a program using this principle that pops up error messages instead of cout's to simulate the Windows experience for Mac/Linux users!

Leave a Reply

You can use these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">