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 parameter sumto = 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 (both inclusive).

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

Note that in the above code, we recurse with value sumto - 1 rather than --sumto. We do this to this because operator-- has a side effect, and using a variable that has a side effect applied more than once in a given expression will result in undefined behavior. Using sumto - 1 avoids side effects, making sumto safe to use more than once in the expression.

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 (not very efficient) 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.

Memoization algorithms

The above recursive Fibonacci algorithm isn't very efficient, in part because each call to a Fibonacci non-base case results in two more Fibonacci calls. This produces an exponential number of function calls (in fact, the above example calls fibonacci() 1205 times!). There are techniques that can be used to reduce the number of calls necessary. One technique, called memoization, caches the results of expensive function calls so the result can be returned when the same input occurs again.

Here's a memoized version of the recursive Fibonacci algorithm:

This memoized version makes 35 function calls, which is much better than the 1205 of the original algorithm.

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 each individual digit in the integer (e.g. 357 = 3 + 5 + 7 = 15). Print the answer for input 93427 (which is 25). Assume the input values are positive.

Show Solution

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

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 converting it to an unsigned integer. These have identical bit representations (the type is used to determine how to interpret the number into decimal).

Show Solution

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

268 comments to 7.11 — Recursion

  • Jack Overby

    Not sure if anyone has already come up with a similar solution, but here's a better way to handle negative numbers, that avoids unsigned int overflow:

    Works as you'd hope for both negative #s and 0!

  • teddye

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

    For the sake of being pedantic I'll point you towards the Ackermann Function, not particularly useful for anything, but truly can only be solved with recursion. Technically you can code it without calling the function within itself, but it involves dynamically allocating a stack and treating it like a call stack, so it's recursion by any other name.

  • Parsa

    Can you make a lesson on returning functions? Does return have a temporary variable?

    I am super confused right now

  • potterman28wxcv

    Hello,

    I was surprised at the Fibonacci example, especially since the implementation you give is the most naive one, of exponential complexity. This could induce a beginner into thinking their iterative version is much faster than the recursive one - when in fact, the recursive implementation you gave is algorithmically awful in terms of complexity (exponential complexity).

    It would be much better (and not much more complicated) to use memoization such as this code:

    (the .push_back part could be done a bit better, but it's just an example)

    And indeed, if I try to run your example on fibonacci(10000) it runs on and on without finishing because of the exponential ; while my code seems to be much faster, below a second of execution.

    (it is a bit silly i know to run fibonacci(10000) when a 64 bits integer isn't enough to contain it, but it's just to show the runtime complexity)

    Cheers

    • Alex

      The lesson is primarily focused on C++ mechanics, not so much on algorithm design. Regardless, since you provided some code, I added a subsection to the lesson. Thanks for bringing this up!

      • potterman28wxcv

        Hey, sorry for the delay in the reply - i thought i would have been notified of replies by mail but that's apparently not the case, so actually i didn't check the comments much for further replies.

        Thanks a lot for adding this subsection, it is very well explained and smooth, as usual! :)

  • Jonathan

    My solution is slightly different from the sample solution for the binary question, seems like it works for negative and positive integers and zero.

  • Nirbhay

    Typo:

    Question 3 a) This one is slightly trickier. Write a program that asks the user to enter "an"(should be "a") positive integer.

  • sasan.sn

    hello!
    unfortunately i can't use 8 bytes (64bit) even by long long int variable! why?
    thank you for your answers.

    • - Limit your lines to 80 characters in length for better readability on small displays.
      - Don't use `system`, it won't work on other platforms.
      - Use ++prefix unless you need postfix++.
      - Initialize your variables with brace initializers.

      The size of built-in numeric types is implementation-defined (with some restrictions). If you need a guaranteed size, use `std::int_least64_t` or `std::int_fast64_t`. See lesson 4.6 for more information.
      You can flip bits using the `~` operator.

  • I want to solve marital and individual numbers using self-recall

  • masterOfNothing

    I just couldn't solve the second quiz question.

    Here's the 3A quiz question. Had to do it the hard way:

    • * Don't use C-style casts.
      * Use float literals for floats.
      * Use your editor's auto-formatting feature.
      * Missing printed trailing line feed (Print a line feed when you program is done).

      Line 3 can be simplified by math

      • masterOfNothing

        Yes, the c-style casts... They seem so less complicated and so conveniently similar to how it's done in python. I did it due to laziness, I guess.

        The f suffix?

        I did use it, but for some reason the code I copied in kept copying with wrong indentations. So I fixed what I could in the comment section.

        Good catch! (3rd line)

  • X

    How important is it to learn or know Recursion? Is it used often in the workplace?

    Asking because I understand the concept, I can follow the code of one (using hand-written diagrams) but creating one, as of right now, is something I can't do and I was wondering if I should spend more time on it now and learn it (if it is important) or if I can safely "skip" it and come back at some other point in time.

  • NXPY

    Hey there guys !

    How important is the concept of dynamic programming here ? Can it help reduce time complexity for the Fibonacci sequence to that of an iterative Fibonacci ?

    (Note: I'm using Fibonacci as it's the only example I know correctly . If there are other examples I'll be grateful to know them)

    • > How important is the concept of dynamic programming here
      Dynamic programming is nice, but we have iterative code, which is nicer. Dynamic programming is important in functional languages, where everything is done with functions, not variables.

      > Can it help reduce time complexity for the Fibonacci sequence to that of an iterative Fibonacci ?
      No. Dynamic programming speeds up recursion, but it can't be as fast as an iterative solution.
      The slow part about recursion is that all local variables have to be stored while the recursive sub-call is running. For every recursive call, all local variables (and some extra information) have to be stored. With an iterative solution, every variable exists once.

  • NXPY

    What happens if we make a recursive function inline ?

    • Hi!

      The "inline" keyword is merely a suggestion to the compiler that you'd like this function to be inlined during compilation. The compiler is allowed to ignore your request and it's allowed to inline function which you didn't declare inline.
      If you try to force the compiler to inline a function by using compiler-specific techniques, it might repeat the code over and over, or it aborts compilation.
      clang++'s output:

  • Arthur

    interesting. I have heard of the Fibonacci sequence but never seen it drawn as the Fibonacci sequence I have only seen that drawn as 'The Golden Mean' which is used in art. in photographic composition it is the 'rule of thirds'.

  • Demetrius

    Best explanation of recursive functions I have ever seen. Many thanks to the authors

  • Yiu Chung WONG

    For 3b, so the code is essentially turning the negative integer into a really big positive integer, and then start dividing this big integer by 2 recursively? Is this where all the ones come from ?

    I'm also confused by the ones in front. In chapter 3.7, an example is the number -76. In binary it is 1011 0100, but the code in 3b gives me 11111111111111111111111110110100. The last eight digits are the same, but how does the compiler/CPU/what ever tell the difference?

    • Hi!

      > turning the negative integer into a really big positive integer [...]
      Yep

      > I'm also confused by the ones in front
      The two binary numbers are the same, they're just using a different amount of bits. Since two's complement (Lesson 3.7) will swap all bits, all 1s will turn into 0s.

  • ryder

    Just want to share with anyone who interested in recursion:

    I found a video very intuitive to show what's recursion: https://www.youtube.com/watch?v=2SUvWfNJSsM&feature=youtu.be

  • kapsch

    Hi there, just like you guys pointed out in one of the comments, the presented solution for 3a) won't print anything for input 0.

  • I tried it and really as u said the recursive solution is easier to design , understand and makes sense more, but
    the speed decreased a lot when i increased the count to 40 in the recursive solution vs the iterative one,
    A question is there a way stop the recursion from making stack overflow just before stack runs out, by signaling that the function
    could not found a solution to the problem ?

    • Alex

      I'm not aware of any good way to determine when the stack is about to overflow.

      The best thing to do here would be to specify a max recursion depth parameter, and either throw an exception or return some sentinel value if the answer can't be determined within that amount of depth.

  • #3a I suppose would be a bit like this:

    and to accept a negative integer (3b) I would just change the call in the function declaration from

    to

    .  I suppose this is correct?

Leave a Comment

Put all code inside code tags: [code]your code here[/code]