Search

7.11 — Recursion

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

When countDown(5) is called, “push 5” is printed, and countDown(4) is called. countDown(4) prints “push 4” and calls countDown(3). countDown(3) prints “push 3” and calls countDown(2). The sequence of countDown(n) calling countDown(n-1) is repeated indefinitely, effectively forming the recursive equivalent of an infinite loop.

In lesson 7.9 -- 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 author’s machine, this program counted down to -11732 before terminating!

Recursive termination conditions

Recursive function calls generally work just like normal function calls. However, the program above illustrates the most important difference with recursive functions: you must include a recursive termination condition, or they will run “forever” (actually, until the call stack runs out of memory). A recursive termination is a condition that, when met, will cause the recursive function to stop calling itself.

Recursive termination generally involves using an if statement. Here is our function redesigned with a termination condition (and some extra output):

Now when we run our program, countDown() will start by outputting the following:

push 5
push 4
push 3
push 2
push 1

If you were to look at the call stack at this point, you would see the following:

countDown(1)
countDown(2)
countDown(3)
countDown(4)
countDown(5)
main()

Because of the termination condition, countDown(1) does not call countDown(0) -- instead, the “if statement” does not execute, so it prints “pop 1” and then terminates. At this point, countDown(1) is popped off the stack, and control returns to countDown(2). countDown(2) resumes execution at the point after countDown(1) was called, so it prints “pop 2” and then terminates. The recursive function calls get subsequently popped off the stack until all instances of countDown have been removed.

Thus, this program in total outputs:

push 5
push 4
push 3
push 2
push 1
pop 1
pop 2
pop 3
pop 4
pop 5

It’s worth noting that the “push” outputs happen in forward order since they occur before the recursive function call. The “pop” outputs occur in reverse order because they occur after the recursive function call, as the functions are being popped off the stack (which happens in the reverse order that they were put on).

A more useful example

Now that we’ve discussed the basic mechanics of recursive function calls, let’s take a look at another recursive function that is slightly more typical:

Recursive programs are often 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 value = 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.

At this point, it's easier to see that we're adding numbers between 1 and the value passed in.

Because recursive functions can be hard to understand by looking at them, good comments are particularly important.

Recursive algorithms

Recursive functions typically solve a problem by first finding the solution to a subset of the problem (recursively), and then modifying that sub-solution to get to a solution. In the above algorithm, sumTo(value) first solves sumTo(value-1), and then adds the value of variable value to find the solution for sumTo(value).

In many recursive algorithms, some inputs produce trivial outputs. For example, sumTo(1) has the trivial output 1 (you can calculate this in your head), and does not benefit from further recursion. Inputs for which an algorithm trivially produces an output is called a base case. Base cases act as termination conditions for the algorithm. Base cases can often be identified by considering the output for an input of 0, 1, "", '', or null.

Fibonacci numbers

One of the most famous mathematical recursive algorithms is the Fibonacci sequence. 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.

Recursive vs iterative

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). For example, while it's possible to write the Fibonacci function iteratively, it's a little more difficult! (Try it!)

Iterative functions (those using a for-loop or while-loop) are almost always more efficient than their recursive counterparts. This is because every time you call a function there is some amount of overhead that takes place in pushing and popping stack frames. Iterative functions avoid this overhead.

That’s not to say iterative functions are always a better choice. Sometimes the recursive implementation of a function is so much cleaner and easier to follow that incurring a little extra overhead is more than worth it for the benefit in maintainability, particularly if the algorithm doesn't need to recurse too many times to find a solution.

In general, recursion is a good choice when most of the following are true:

  • The recursive code is much simpler to implement.
  • The recursion depth can be limited (e.g. there’s no way to provide an input that will cause it to recurse down 100,000 levels).
  • The iterative version of the algorithm requires managing a stack of data.
  • This isn’t a performance-critical section of code.

However, if the recursive algorithm is simpler to implement, it may make sense to start recursively and then optimize to an iterative algorithm later.

Rule: Generally favor iteration over recursion, except when recursion really makes sense.

Quiz time

1) A factorial of an integer N (written N!) is defined as the product (multiplication) of all the numbers between 1 and N (0! = 1). Write a recursive function called factorial that returns the factorial of the input. Test it with the first 7 factorials.

Hint: Remember that x * y = y * x, so the product of all the numbers between 1 and N is the same as the product of all the numbers between N and 1.

Show Solution

2) Write a recursive function that takes an integer as input and returns the sum of all the numbers in the integer (e.g. 357 = 15). Print the answer for input 93427 (which is 25).

Show Solution

3a) This one is slightly trickier. Write a program that asks the user to enter an integer, and then uses a recursive function to print out the binary representation for that number. Use method 1 from lesson 3.7 -- Converting between binary and decimal. Assume the number the user enters is positive.

Hint: Using method 1, we want to print the bits from the "bottom up", which means in reverse order. This means your print statement should be _after_ the recursive call.

Show Solution

3b) Update your code from 3a to handle the case where the user may enter 0 or a negative number.

Here's a sample output (assuming 32-bit integers):

Enter an integer: -15
11111111111111111111111111110001

Hint: You can turn a negative integer into a positive one by static casting it to an unsigned integer. These have identical bit representations (the type is used to determine how to interpret the number).

Show Solution

7.12 -- Handling errors, cerr and exit
Index
7.10 -- std::vector capacity and stack behavior

148 comments to 7.11 — Recursion

  • Stephane

    Hi Alex,
    here’s a recursive function binarySearch that takes a vector of ints and an integer x and return a bool depending on whether x was found or not;

    As far as I know, when using binary search algorithm, it search an element by half and for condition that the array should be sorted.

    In ivec in the main function above, the value 11 is placed at an unordered way.

    1) When i run the program it says that: "11 is in the array" (So why this result I expected that 11 would not be found due to the unsorted array).

    2)In place of 11 in the same ivec, I put the value 0 and the program crash saying: "terminate called after throwing an instance of ‘std::bad_alloc’ what():  std::bad_alloc". (Why this behavior?)

    Thank you and have a nice day in advance!.

    • nascardriver

      Hi Stephane!
      Your code formatting is terrible, I’ll usually leave it up to the coder but this is a mess.
      I’ll use the following code to refer to line numbers. I’m not going to list all of the issues with your code, so please just read though this and compare it to your code to see what I changed. If you have any question about my modifications feel free to ask.

      Why does binarySearch find 11 when the vector is unsorted?
      Line 12: You’re setting mid to the start of the vector when it’s supposed to be the middle of the vector. binarySearch runs once, removes the 1, now 11 is at index 0, then 11 is mid, your algorithm found 11.

      Why does your program crash when you replace 11 with 0?
      Line 21: (1 < 0) is false, line 27: mid is the first element of the vector, mid-1 does not exist.

      • Stephane

        Thank you a lot nascardriver, I didn’t remarked that I initialized mid to begin() cause of the problems and excuse me for bad formatting.

  • Matias

    Here’s how I solved the second quiz question, the one on the sum of the digits of a number:

    Some of the mathematical intuition I got from a notepad file but I’ll try to explain in either way, maybe someone finds it useful.

    1st - I wanted to see how I could get individual digits out of an integer. Since this was integer division, I set up a notepad file to verify that the number in question divided (integer division, remember) by a power of 10 to the number of digits of that number minus 1 was what gave me the individual digits. Now I had a new “minitask”.

    2nd - Find out a way of getting the number of digits from an integer: I figured that the powers of 10 are the numbers that “start off” every new “column” (that corresponds to 10^numberColumn - this is just how we see numbers in the decimal system -> we see the digit and we multiply it by the power of 10 corresponding to that location). I decided to try my luck with the natural log function, and see how it differed in between each power of 10. The difference was that of around 2.3, hence how I came to the realization that ln(n)/2.3 + 1 was the number of digits(remember that ln(n)/2.3 would return “1” digit short).

    Hopefully this was a good explanation or whatnot, but it was really fun to have a math + programming assignment!

  • Kushagra

    Here is my code to distribute money into Rupee(Indian currency) notes.
    how can I use recursion to make it short?
    #include <iostream>

    void count (int x)
    {
    int f = 0;

    for(; x>=2000; f++ )
    {
        x-=2000;
    }
    std::cout << f << " 2000 note \t " ;
    f =0;

    for(; x>=500; f++)
    {
        x-=500;
    }
    std::cout << f << " 500 note \t " ;
    f =0;
    for(; x>=100; f++)
    {
        x-=100;
    }
    std::cout << f << " 100 note \t " ;
    f =0;
    for(; x>=50; f++)
    {
        x-=50;
    }
    std::cout << f << " 50 note \t " ;
    f =0;
    for(; x>=20; f++)
    {
        x-=20;
    }
    std::cout << f << " 20 note \t " ;
    f =0;
    for(; x>=10; f++)
    {
        x-=10;
    }
    std::cout << f << " 10 note \t " ;
    f =0;
    for(; x>=5; f++)
    {
        x-=5;
    }
    std::cout << f << " 5 note \t " ;
    f =0;
    for(; x>=2;f++ )
    {
        x-=2;
    }
    std::cout << f << " 2 note \t " ;
    f =0;
    for(; x>=1; f++)
    {
        x-=1;
    }
    std::cout << f << " 1 note \t " ;
    f =0;
    }
    int main()
    {
        std::cout << " Enter amount of rupees " ;
    int g;
    std::cin>>g;
    count(g);
    return 0;
    }

    • Alex

      It’s no fun if we do your work for you. 🙂 See if you can come up with a solution on your own.

      Personally, I’d use an iterative algorithm for this (and maybe an array to hold the different note sizes).

  • Kushagra

    Here is my code for quiz 3
    #include <iostream>

    void dtob( int y)
    {

    if ( y ==1 )
    {
        std::cout << "1";
        return;
    }

    dtob(y/2);
    std::cout << y%2;

    }

    int main()
    {
            dtob(6);
        
        return 0;
    }

    is the code efficient?

  • Kushagra

    Here is my code for quiz 2
    #include <iostream>

    double sumnumbers( double y)
    {
        if (y <10)
        return y;
    int x = y/10;
    double z = y - (x*10);
    return  sumnumbers( x) + z;

    }

    int main()
    {
    std::cout<<     sumnumbers(93427);
        
        return 0;
    }

    It is easy to understant

  • here is my program for factorial of number.

    just one question, what if we want to get the factorial of ,say 24, it will be pretty big. So, how do we return that.

    #include<iostream>
    using namespace std;
    long long factorial(int x)
    {
        if(x==0)
            return 1;
        else
        {
            return factorial(x-1)*(x);
        }
    }
    int main()
    {
        int n;
        cin>>n;
        cout<<factorial(n);
    }

Leave a Comment

Put C++ code inside [code][/code] tags to use the syntax highlighter