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.

Hint: You can turn a negative integer into a positive one by static casting it to an unsigned integer.

Show Solution

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

120 comments to 7.11 — Recursion

  • SJ

    Hi Alex,

    With the factorial function, it is clear that the output grows quite rapidly as a function of its input. So I was wondering…

    1) If I wanted to return a long value, what would be the correct way to do this? I noticed that, at least with my compiler, doing

    works, but the original way I did it was replacing return 1 with

    my thought process being that the 1l would end up converting the last product to a long, and then the second-to-last product to a long, etc… , since long had a higher priority when it comes to coercion (please correct me if I’m wrong, I’m just trying to remember what you taught in the implicit conversion tutorial!).

    So which one is preferred? I’m actually a little bit surprised the first way works actually but I tested it with large enough values and it does.

    2) Let’s say I wanted to test the value of the argument factorial(n) to see whether I should return an int or a long. This would require specifying the return value beforehand however, such as

    verses
    int factorial(n) {…}
    [/code]
    The only workaround I can think of is passing n to another function which has the appropriate return type, such as

    Would this be the correct approach?

    Thanks!

    • Alex

      Good questions.
      1) Returning 1 and 1l should produce the same result, as 1 would be implicitly converted to a long before being returned. The real challenge here is that “n*factorial(n-1);” only contains integers, and will produce an integer result (which could overflow). This (possibly overflowed) result will then be converted to a long for returning to the caller. What we actually should do is convert one of the operands to a long, so that all of the other operands get implicitly converted to longs as well: static_cast<long>(n)*factorial(n-1);
      2) Functions can’t differ only by return type, so your functions would need different names. While you could do as you suggest, is there any reason not to just always return a long?

      • SJ

        Thanks for the quick response! I assume you mean static_cast<long>(n) right? I guess I could also just read in n as a long, such as

        and then avoid the static casting.

        And upon further inspection of my code for my second question, I actually don’t think it would work because the call from int factorial(n) would be on the bottom of the stack, and so it would end up being converted to an int anyways (I believe). I know for this example simply using a long return value would be fine, but I was thinking ahead to possible other scenerios where one may wish to return a different type than what the return type for the calling function is. I don’t know what these other scenerios may be, and perhaps a simple cast may resolve the issue 😛

        • Alex

          Yes, the commenting system interpreted my <long> as an HTML code. Oops.

          But upon reflection, I think my previous analysis was incorrect, as factorial() will be interpreted as a long (since that’s what it returns), which should force everything else to be implicitly converted to a long. So your recursive line should work as intended. And as noted above, the base case of 1 will get implicitly converted if it’s not a long, so no worries there.

  • SkinMan95

    Is there a way to extend the recursion depth of a function? (just involving code, without changing any configuration in the OS)

    I tried to extend it by using just pointers when calling a function, because I thought that in the stack would be the reference of the variable as the information itself, so I tried that the pointers would be the only thing in the stack and the information to be dynamically allocated, I don’t know if I explained myself well. (I don’t know if what I’m saying is also true).

    • Alex

      The only way I can think of to allow your function to recurse deeper in a code-only manner would be to do something that reduced the amount of stack memory each function call took (which would allow it to recurse more times before running out of memory). That could be using pointers and dynamically allocating anything larger than the size of your pointer on the heap, removing variables or parameters, etc…

      • SkinMan95

        Involving that, is it true that what an actual variable weights is the reference to the object and the information of that object in the stack all together, in that case, for example, i declare a integer variable, which has 4 bytes, but the implicit pointer is 8 bytes, then the real weight is 12 bytes? or how does that work?

        • Alex

          I’m not sure what you’re asking.

          All variables allocated on the stack take up an amount of stack memory equal to the size of that variable.

          Memory allocated on the heap does not take up stack memory, since that comes from a different pool.

          So if your pointer size is 8 bytes, and you want to minimize your stack footprint, you’d want to allocate all memory above 8 bytes on the heap. For anything 8 bytes or less, the size of the variable is equal to or less than the size of the pointer, so you might as well just instantiate it directly.

          I don’t know why you’d do any of this though.

          • SkinMan95

            That’s because some competitive problems of programming involves sometimes recursion, and is important to know the depth that a recursion can reach, in python there’s something similar, but the limit is with a finite number and not explicitly with the size of the heap, what I’m trying to do is to squeeze the recursion limit in C++.

  • Alexander Bieniek

    "It turns out that you can always solve a recursive problem iteratively…"

    Are you sure about this? To be honest, I’m not entirely sure why, but I think I’ve heard that recursive functions are sometimes impossible to use iteratively because of forward recursion and tail recursion.

    based on my notes for a proficiency exam:

    Tail Recursion: A form of recursion where the recursive call is the final thing that you do in the recursive case of your algorithm

    These sorts of algorithms can be changed into loops because, when the recursive call is to be made, there is no more information that is still needed from the previous recursive instance

    _____

    Forward Recursion: A form of recursion where there is still work to be done after you make another recursive call

    These sorts of algorithms cannot be changed into loops because there is still information to be used when the algorithm wants to make the recursive call

    Comments? This class was based around the Java language, so I don’t know if that has anything to do with it, but I doubt it.

    • Alex

      Yes, I’m sure. However, that says nothing about how pretty/effective doing so would be.

      Tail recursion functions are usually pretty easy to convert. Forward recursion functions are usually not easy to convert -- doing so would likely involve your function maintaining its own stack! And why do that yourself when the language provides that functionality for you as part of function calls? But you could.

  • Sandro

    What does "int main(void)" means?

    Why the "void" parameter?

    • Sean Kelly

      including "void" as a parameter type just tells the compiler that there are no parameters included in the function. It is recommended by Alex (In another chapter) that you do not use void when creating function prototypes or defining functions in general.

    • Alex

      It means that main is not taking any parameters. It’s old school usage, and deprecated in C++. In C++ we’re supposed to use empty parenthesis (e.g. int main()). I’ve fixed the examples.

  • Sean Kelly

    Question 2 took me about 15 minutes to figure out, it was quite hard for me.
    I felt really accomplished once I did figure it out though, thank you for the tough question!

  • Quiz 1 solution:
    Since we know that 1! == 1 , it seems logical to add it to a base case, changing n < 1 to n < 2 (in which case, 1 and lower, inc 0, will return 1). (Otherwise every call to factorial(x) will do an extra useless «iteration» over 0.)

    (Also, the solution is missing a return value in main().)

  • Mike

    Hi Alex.

    The very first code example in this article won’t compile because there should be << ‘\n’ instead of << \n’ at the end of line 5.

    The last code example (recursive Fibonacci) won’t compile either because the function is defined as int fibonacci(int number), and its return statement calls Fibonacci (capital F), which is undefined.

  • Naga Pushkal

    Sorry for my typo in the first line of my comment. Count will be greater than Zero.

  • Naga Pushkal

    Hi Alex,

    In your second example program, you have mentioned that countDown(1) does not call countDown(0). But countDown(1) calls countDown(0) because count will be greater than 1 and if statement executes. So your program is printing

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

    Thank You very much for your tutorials. I am learning a lot from this site. Love your tutorials. You are like my master (My Guru in Indian culture). Waiting eagerly for your updates in Object Oriented Programming section.

  • SideEffects

    Hey Alex,

    I was wondering if you could tell me how you would implement a fibonacci sequence function considering the limit of the stack. From what I understood from the previous tutorial, the stack has less memory than the heap and since we are calling the same function every time, the return values start to accumulate and are never popped until the stack overflows.

    My question is: when would you use recursion and when would you use an iterative function? Is there really any use in using recursive functions? Before reading this I always used recursive functions, but now that I see that they are less efficient I am starting to wonder if I should even use them.

    • Alex

      This is a great question.

      Personally, I only use recursion when:
      * 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.

      Personally, I’d write a Fibonacci sequence function iteratively because it’s relatively simple to do, and will be more performant. But that said, because of the way that Fibonacci numbers grow, you’d overflow your integers before hitting the stack limit with a recursive implementation.

      There are some algorithms that are much easier to write recursively than iteratively, such as quick-sort or merge-sort and some tree-walking algorithms. I’d start with a recursive version of those, and then optimize to an iterative version if performance demands required it.

      In short, I use recursion for the few things where it really makes sense, and iteration for everything else.

      Note: In C/C++, iteration is generally quite a bit faster than recursion. However, in other languages, this is not necessarily (as) true, so the above may not be generalizable.

      • SideEffects

        Thanks Alex! That’s really useful to know, thanks for the quick reply!

        I would also like to thank you for taking time to write these tutorials and even answer the questions. This is hands down the best C++ tutorial I have ever seen and I keep referring all my friends who are trying to get into coding. Keep up the great work 🙂

  • Mr D

    I found this chapter very hard to get my head around, but i think i managed it.
    This youtube video also helps: https://www.youtube.com/watch?v=Mv9NEXX1VHc

  • Alex, here is my iterative fibonacci generator:

    I want to remove the if statement inside the for loop because it looks ugly. But i can’t because y needs to be incremented once. How can I do that?

  • 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;
    }

  • 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 😛

    • 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!

  • lunchmeat

    Hey there.

    I’m just another guy who’s been reading through your tutorials (not always in a linear fashion) and I liked this one - especially coming from the previous article dealing with stack memory.

    I noticed something - when I write recursive statements, I don’t use a return statement until I break the recursion. I noticed that you use return statements as part of your recursion. For example:

    When I’ve written code like this, I wouldn’t have thought to put the function call after a return statement in the else block. (In practice, it yields the same results.) You may have stated this, but I may have missed it - does using a return statement in front of the recursive function prevent the stack from filling up? Based on how you stated stacks worked in the previous tutorial, this seems to make sense…by issuing a return statement, the function variables and whatnot are removed from the stack each time it recurses so it doesn’t build up. Am I right or am I missing something? It seems to make sense, but something isn’t quite right….

    As a side note, I made my own fibonacci sequence before reading this article (as practice for command-line arguments) but I used a recursive sequence that added the last and second-to-last numbers to get the next number. 1+1=2, 2+1=3, 3+2=5, 5+3=8, and so on. Seems like this method takes less overhead?

    Thank you for your tutorials!

    • Alex

      Putting the function call on the same line as the return statement in the example was done just to avoid having to store the return value from the recursive function call in a temporary variable before returning it.

  • Bob

    Is there actually a use of fibonacci numbers in C++? Apart from in a maths program!

  • Simon Harpham

    Here’s an extension of the fibonacci sequence to negative numbers. The results are a little counter-intuitive for negative numbers, cf. http://en.wikipedia.org/wiki/Negafibonacci for details.

  • khawla hussein

    thank you very much, i understand a recursion, it is easy and fine, thnks again. i feel happy.

  • Quinn

    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. It didn’t even need to allocate any additional memory, I’m disappointed!

    Never tried doing that before, now I’m gonna see if I can fork bomb this beast!

    • Sean Kelly

      Keep in mind, I am pretty sure stacks on Linux are defaulted to be much larger than on windows environments.

      • Kruthers

        Same thing happened to me.  It goes on for millions and I don’t think stacks are ever that big.  Seems more likely the compiler is doing tail recursion optimization, where it automatically converts to iteration for you.

        http://stackoverflow.com/questions/34125/which-if-any-c-compilers-do-tail-recursion-optimization

  • Kerrick

    Note that the recursive implementation of a Fibonacci number generator is very inefficient. For example, to calculate Fibonacci(5), it calculates Fibonacci(4) and Fibonacci(3). To calculate Fibonacci(4), it recalculates Fibonacci(3), and so forth. In general, it will take an exponential number of calls to calculate the number; that is, it is O(exp(n)) in both time and space. See this code for a demonstration.

    • That is very true. It’s much more efficient to write an iterative version. I often see this question come up on job applications. They’ll ask you to write a Fibonacci function, but the thing they are really interested in is whether you understand that the recursive version of Fibonacci is too inefficient to use for practical purposes.

    • Kevin

      Iterative function that does the same. It’s quite simple to do in a loop as you can just start adding the numbers up as you work up the sequence. It’s easy to figure out when you look at the sequences working from left to right.

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

  • khen

    hey,
    I wanted to ask about the efficiency of Recursion versus using for loop or while.

    btw: your articles are great! I enjoy very much to read.

    thanks,
    khen.

    • Iterative functions (those using a for or while loop) are almost always more efficient than their recursive counterparts. The reason for this is because every time you call a function there is some amount of overhead that takes place. 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.

  • ny

    void quiz(int i)
    {
    if (i > 1)
    {
    quiz(i / 2);
    quiz(i / 2);
    }
    cout << “*”;
    }

    if quiz (5) ??? then how many time start printed?

    get confused for this one..

    how is going to solve step by step.. like u solved example one. .. ?

  • ny

    hay alex.. thanks lot man.. i know recursive function.. but after read this article.its so easy to solve recursive. now i completely understand recursive function. thanks lot

    cheers

  • Karma

    hi nice post, i enjoyed it

Leave a Comment

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