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 |

Hi

You could have reduce the call of the fibonacci function call further by replacing fibonacci(count-2) by results[count - 2]

#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) + results[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;

}

Hi,

for the first quiz question I wrote this and it seemed to work fine:

is there any reason this version would be dangerous to use, or is it okay?

`findFactorial` causes undefined behavior, because it doesn't return unless `fact == 1`.

Thank you!

Hi, I've got a question.

How do you know when do you have use cache?

I made a typo

How do you know when do you have use *to* cache?

Hi here is my version of Fibonacci without recursion you challenged us!!:

however using "unsigned long long" is preferred for larger n

There is a typo. it should be "int i{2}" in line 13!

In the answer to quiz 1,

you didnt use the memoization technique for better performance. Is it because it doesnt work for this requirement or is it unnecessary?

1. Question on 1205 and 35 function calls

In our compiler, how do you check the number of times a function is called?

2. Question on cache

"We'll use a static std::vector to cache calculated results"

Does cache mean cache memory?

The L1, L2 very fast type of memory or does it mean just the stack?

3. This is for Quiz 1

I hope that this is acceptable.

Thank you very much for the tutorial.

1. The compiler doesn't run your functions, it can't count how often they're called. You can add a global variable and print and increment it every time the function is called to see how often it got called. This is for debugging only, avoid global variables.

2. Cache doesn't refer to any hardware. It's a place where you store something that you think you might need later.

3. Your solution isn't recursive, but correct for an iterative solution. Rather than adding `value` and 1 every iteration, you can use `i <= value`.

1. Ah, like

Note to self: It would be nice if IDE/compilers had a function call counter.

2. Got it. Thank. Like a temp memory somewhere?

3. Got it. I'll redo it in a recursive version. May I ask for a specific example where recursion is obviously better than iteration?

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

Thank you for all the clarification.

It makes learning C++ much smoother.

2. This is for Question 2. Based on quotients and remainders.

For part 3b, I did not know it was so simple to just static_cast<unsigned int>(getInt());. I thought we had to use *=-1.

1. Logic is correct. You don't need the `factorial` variable, you can return right away.

2. Causes undefined behavior, your compiler warns about this.

1. Changed to remove the "int factorial{}". I think this is quite useful. Like avoiding premature optimization.

Is there a way for the compiler to tell you that you can optimize your code further?

2. I don't have any compiler errors from Microsoft Visual Studio 2019.

May I ask which line of code is it?

1. You can use clang-tidy. Start by enabling all checks, then disable the ones you don't agree with.

2. If I tell you were the issue is, you won't try to fix your compiler/IDE. You're using a weird version or you broke something. If you don't fix it you'll make mistakes that your compiler would have warned you about.

1. How do I use Clang Tidy? There are no check boxes.

2. I'm pretty certain I've been following the instructions you gave out.

a. Raise Warning to W4

b. Report all Warnings as Errors

c. Turn off Language Extensions to /Za

d. C++2017

It's not covered on learncpp and I don't use Visual Studio, you'll have to figure this out yourself

https://docs.microsoft.com/en-us/cpp/code-quality/clang-tidy?view=msvc-160

I run the Fibonacci program and it resulted in '0 1 41484624 0 41491168 0 2082450736 0 2123935360 -130065824 -88581200 -130065824 1993869536'

I think the issue was caused by the sizeof operator, which i changed from std::size since mine is C++14. Is there any fix to this?

`sizeof()` returns the size of the type you're giving it. You're giving it a `std::vector`, so it returns the size of the type `std::vector`, not the length of its contents. `std::vector` has a `.size()` member function that you can use.

There's no reason not to be using C++17 for desktop applications.

Ah i finally figured out how to choose a C++17 compiler, thank you

Thought I should share my hilariously unnecessary (and requiring-external-research) answer to Q2:

Hi, may i ask what (y - 48) does? I'm going in the same direction as you but with C style string and i'm stuck

Hiya. I can't pretend my approach made any kind of good sense. In essence, instead of taking a simple mathematical approach to the question, as in the given solution, I was operating on the following rationale:

(1) To treat the digits of '93427' individually, I 'needed' to convert the integer '93427' to an std::string (on the understanding that an std::string is basically a container-array of individual CHARS);

(2) I was then static_casting to int each final char in the string and assigning them to y before then removing them from the string, converting the remaining string BACK to an integer, and returning it for recursion PLUS the VALUE of the character that had been removed;

(4) this is the thing that took me forever to realise, though: when you static_cast a char to int it does NOT give you the value of the number (as you might expect), but instead the ASCII code FOR that value: so for final char '7', this would produce '55', which of course was giving me all kinds of screwy final results. So what I needed to do was subtract off everything that precedes the ASCII code for '0' (i.e., 48) from my 'y' value: e.g., y-48, where y is the CHAR '7' static_cast to the ASCII-code FOR '7' (i.e. '55'), gives us the actual integer value (55 - 48 =)'7'.

Madness! But I hope my explanation clarifies... somewhat. :-P

Thanks a lot it really hepled! And no it wasn't madness at all, since i was going in the same direction but i couldn't transform numbers to an array. I think it's a good job done. Have a great day!

I can't understand how the solution to 3b works. And it turns out that the conversion to unsigned int from int is the part where I lose it. I tried to understand the conversion but I can't. How does normal int convert to unsigned int. I was thinking that the sign just goes off but it doesn't

This is my third time trying to finish this course over the past 2 years. I switched over to java over a year and a half ago and have made many strides on that, but with some spare time on my hands, I decided to finish the basic of C++ at least or else I'll be mad at myself.

Anyway I decided to try a small for fun program of a basic polish notation parser using recursion. Anything I could take back and reflect on to improving? I know there isn't much to consider though.

Example:

&+2*83 is the same as "the sum up to (2 + (8*3))

+23 is the same as 2 + 3

- If you don't modify something, make it `const`. Especially references.

- Initialize variables with list initialization for higher type-safety and uniformity.

- `isdigit` is `std::isdigit` and is declared in <cctype>

- Don't ignore your compiler's warnings. Your code is broken. It's unspecified which side of an operator gets evaluated first. Because you're using `++index`, which has a side effect (Incrementing `index`), this changes the behavior of your program.

- Line 23+: Don't repeat yourself. This goes along with the previous point. To fix the previous point, you have to update 4 different places, rather than 1. Handle the & case first. Then run your `calculateExp` calls in separate lines and store their results in variables. Then run a `switch` and use the variables.

Ok, I have level 4 compiler warning on VStudio but I am getting no warnings. I also don't know what you mean by the last point, do you mean to create four different variables for each case +,-,*,/

With default settings, you get

I didn't see this before, but it causes undefined behavior.

With /W4, you also get

With /Wall, you also get

And astonishingly, msvc really doesn't warn about the side effects. In either case, something is wrong with your settings if you're getting no warnings at all.

You need 1 variables for

and another variable for

Then you can use the variables in your switch-statement, rather than repeating the calls to `calculateExp`.

In case you want to check if you've resolved the warnings, I've configured a compiler that shows them properly https://godbolt.org/z/7MqWPo

Just paste your code there and read the output in the top right window.

Oooh, I did define two variables but I defined it in the wrong scope by mistake hence why it wouldn't work for cases such as '+2*82'. Those warnings are because the original code I uploaded wasn't fully assessed so there's a random variable secondDigitIndex. I fixed the warnings. Thanks so much for the help. Just shows I still got alot to learn.

Your solution to Q2 just returns negative numbers back to the caller. Here's a version that returns the sum of the digits with a negative sign in front (e.g. sumDigits(-93427) returns -25), which I think is pretty cool.

The underlying logic is the same, but the code exploits the fact that newer specifications of C++ (17, I think?) preserves the negative sign when applying operator%. Of course, this code is going to give you garbage if your version of C++ doesn't do that.

Using integer==0 will print 0 (0%2 == r0), and using integer==1 will print 1 (1%2 == r1).

What I thought is that using if (integer==0) is useless, because the recursion will terminate once the integer is less than 1.

(Sorry for multiple comments in this chapter, I've read it all again to make sure I understood everything)

and what about integer==2? It will enter the recursion, but then still reach the `std::cout` with integer==2

What do you mean?

Thanks for the reply!

If I understood you right, you want to change

to

But that doesn't work, try it out.

If that's not what you suggested, please elaborate

No no, I just meant that this:

Can just be changed to

So no return statement is needed (and the rest will be the same):

- When x is 1 or less the function will stop the recursion

- 1%2 is always 1, 0%2 is always 0

Yes you can do that. It boils down to personal preference which one you use.

Hi,

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.

I don't understand what is the side effect of -- operator than -1 from your statement.

What I understand is --sumto is completely different with sumto-- hence using sumto-- will cause some issue.

Hope you can explain with some example for the possible side effect.

Thank you always

On my PC with Code::Blocks 20.03 a solution to the last question gives an error:"conversion to unsigned int from int may change the sign of the result"in line 17.

I added a cast to the solution, thanks for pointing out the warning!

The hint for quiz 3b confused me quite a bit: "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)."

The second sentence implies a special relationship between the two numbers, e.g. +15 == -15 in binary, which is of course wrong. I suggest rephrasing the hint, e.g. like this: "Any negative integer value stored in memory can be interpreted as a positive integer by type conversion. Extract the user input as int and then convert it to unsigned int."

Apparently, Andreas Krug hasn't been here yet: Shouldn't the line "Rule: Generally favor iteration over recursion, except when recursion really makes sense." be placed in a beautiful green rule box? :-D

My solution to question 3.

It's hilarious how in every quiz I make containing ifs/elses, I always miss the fact that my if/else statements are completely useless (since in this case the remainder is always either 1 or 0).

r.i.p

Is the following solution OK in case we don't want to avoid having 'unsigned int' type as our function parameter?

Is it a good way to write factorial like this? after the termination condition is met, the function is done and

it doesn't have to go back all the way to the first function call.

"There are techniques that can be used to reduce the number of calls necessary."

Necessary or Unnecessary?

"The iterative version of the algorithm requires managing a stack of data."

What does this mean?

>>We do this to this because operator-- has a side effect

Isn't 'to this' extra?