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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
#include <iostream> void countDown(int count) { std::cout << "push " << count << '\n'; countDown(count-1); // countDown() calls itself recursively } int main() { countDown(5); return 0; } |

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):

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
#include <iostream> void countDown(int count) { std::cout << "push " << count << '\n'; if (count > 1) // termination condition countDown(count-1); std::cout << "pop " << count << '\n'; } int main() { countDown(5); return 0; } |

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:

1 2 3 4 5 6 7 8 9 10 11 |
// return the sum of all the integers between 1 (inclusive) and sumto (inclusive) // returns 0 for negative numbers int sumTo(int sumto) { if (sumto <= 0) return 0; // base case (termination condition) when user passed in an unexpected parameter (0 or negative) else if (sumto == 1) return 1; // normal base case (termination condition) else return sumTo(sumto - 1) + sumto; // recursive function call } |

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 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:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
#include <iostream> int fibonacci(int count) { if (count == 0) return 0; // base case (termination condition) if (count == 1) return 1; // base case (termination condition) return fibonacci(count-1) + fibonacci(count-2); } // And a main program to display the first 13 Fibonacci numbers int main() { for (int count=0; count < 13; ++count) std:: cout << fibonacci(count) << " "; return 0; } |

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:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
#include <iostream> #include <vector> // h/t to potterman28wxcv for a variant of this code int fibonacci(int count) { // We'll use a static std::vector to cache calculated results static std::vector<int> results{ 0, 1 }; // If we've already seen this count, then use the cache'd result if (count < static_cast<int>(std::size(results))) return results[count]; else { // Otherwise calculate the new result and add it results.push_back(fibonacci(count - 1) + fibonacci(count - 2)); return results[count]; } } // And a main program to display the first 13 Fibonacci numbers int main() { for (int count = 0; count < 13; ++count) std::cout << fibonacci(count) << " "; return 0; } |

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.

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.

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.

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).

10.13 -- Command line arguments |

Index |

10.11 -- std::vector capacity and stack behavior |

whats wrong with this code? it prints accumulated result.

See lesson 6.10

try my fibonacci in an iterative approach, which use less memory

You could tidy the beginning a bit like so:

This might not be preferred by many (for one it does extra work when passed 0 or 1) but I just have a thing for the ternary operator:

The use of modulus is a neat trick but pretty hard to decipher. I like this implementation since it easier to read and gets rid of the conditional statments althogether:

So in the Quiz 3)b), I still don't understand why we can pass a negative value to an unsigned int (which just holds positive value, right?) and we still get the right output?? How does it convert??

And also, how does the function work when we pass a negative, like, how the function can print out the right binary of a negative?? And what do you mean by "These have identical bit representations"?? Sorry, but I still don't understand and can't get through this Quiz

When you call a function, the parameters get initialized via copy initialization, ie.

Unlike list initialization, copy initialization allows narrowing conversions, so this initialization of `n` is legal. When a signed negative integer is converted to an unsigned integer, the value wraps around (-1 is the maximum, -2 is maximum-1, ...).

Suppose we have a 4 bit integer,

dec(-1) is bin(1111)

dec(-1) converted to unsigned is dec(15), and dec(15) is bin(1111).

As you can see, the two's complement representation is identical to the number we get from wrapping around.

Ah, now that I can understand the quiz quite thoroughly, and move on to learn next lessons. Thanks so so much.

Really useful, thank you!

Dear Alex and Nascardriver, thank you very much for these tutorials. I am enjoying them very much!

About the memoization covered in this lesson, I think it would be of benefit to showcase how it unfolds and what each recursive function call does, for example, when calling fibonacci(3), and comparing it to the non-memoized version of fibonacci().

Hi guys!

Thanks for these amazing lessons in C++!

I made solutoins of the quiz only using iteration:

- Don't use special integers unless you have a reason to. Stick with plain `int`.

- `std::string` is for strings. Trying to use it for per-digit operations is a common mistake. It works, but it's slow. Stick with math, ie. number % 10 to get the least significat decimal digit, then number /= 10 to remove that digit.

- Name variables descriptively. Your variable names make your code hard to read.

One of the harder lessons for me so far. But I had way more trouble with quiz 2 than quiz 3 tbh, only me?

Just wanted to share my last quiz answer using std::abs to function with negative numbers.

Hi,

I saw in quiz 3a a good opportunity to use vectors (which I got to know recently through this tutorial) and I tried to solve the exercise with the following code but it is not working (it does not print anything), and yet, I can't see where the mistake is. I'd appreciate any comment and even more so any adjustment as I really would like to get this working. Thanks in advance.

You're passing `binary` by value. Line 8 doesn't modify `main`'s `binary`.

I did something similar. The solution above is neater for sure, but I wanted to try out passing a reference to a vector and implementing a stack.

2)

Hi! I wanted to solve the factorial function without having to use any iteration. Is this a legit way to solve it?:

I made an iterative version for the fibonacci numbers too:

The solution used a loop to test the function. The function itself shouldn't print anything. Yours doesn't work, because you used a `static` variable. Try calling `factorial` again and it will produce wrong results.

Same problem in `fibonacci`. Use pure function if possible (A function called with the same arguments produces the same behavior every time). Add a parameter to `fibonacci` which is the index of the number in the fibonacci sequence. Remove `static` and move the loop into `fibonacci`.

Yes, my bad!So I suppose the fibonacci should look something like this:

You were right in the case of the factorials too. I still can not understand why does this work though:

Shouldn't "Fact::factVal = 1;" set the value of Fact::factVal back to 1 every time the function is called? And shouldnt the function just print the value of n then?

You don't need, and shouldn't use, any global or `static` variables.

Let's run your `factorial` manually. The letters indicate which call (depth) we're currently in.

Yes, I understand it now! Thanks! I know that the globals are not necessary here (and in general), I just couldnt wrapmy head around why it worked. But I get it now, thanks again!

Enter an integer: -15

11111111111111111111111111110001

My program works, but I have a question.

For example, here’s how we represent -5 in binary two’s complement:

First we figure out the binary representation for 5: 0000 0101

Then we invert all of the bits: 1111 1010

Then we add 1: 1111 1011

15 binary: 0000 1111

We invert it: 1111 0000

Then we add 1: 1111 0001

The ending is correct but there are plenty of extra 1's. It's because our number starts from (unsigned int maximum number - 15). So my question is do we actually need to discard all the 1's and only leave 8 at the end?

If you want to display only 8 bits, then you need to discard the first 24 (Assuming 32-bit integers).

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!

"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.

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

I am super confused right now

What do you mean by "returning functions"? Functions that return other functions? The quiz in lesson 7.8 shows an example of this.

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

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!

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! :)

You should get replies by email when someone responds to your comment, assuming you left a valid email address. Check your spam box.

You are right, it was all in the spam.

Thanks!

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

Check again, it does not work for negative numbers, nevertheless it's an interesting approach, but still, not very accurate for the task.

true, I thought that for negative binary just add a negative sign in front of the binary...

Typo:

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

Typo fixed. Thanks!

thank you.

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

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

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)

> The f suffix?

Indeed.

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.

Skip it, recursion should be avoided.

Alright, thanks!

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.

Thanks for the reply !

Good thing I checked that doubt here .

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:

Now I understand . Thanks for the reply !

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'.

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

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.

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

Thats great.

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.

3a said to assume the user entered a positive integer (which 0 is not). I've updated the question text to make this clearer.

My bad, sorry.

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 ?

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?

Hi Nigel!

* @main is missing a return value.

* @printBinary won't print anything for input 0.

> I suppose this is correct?

It is