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

7.12 -- Handling errors, cerr and exit |

Index |

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

Hi,

#2 is also quite straightforward:

Hi,

No.1 first I tried thus:

but that just ran a string of 1's and crashed. Then I tried thus:

and it worked as expected. can a while statement not be used with recursives?

Hi Nigel!

Yes it can, but line 20 is not inside the body of the while-loop. It won't be executed until the while-loop has exited, which it doesn't, because @count never changes.

hi, how can I call one function each 5 seconds, without affect the call of others functions

Hi jp!

You're looking for threads:

Note that asynchronous code can cause unexpected behavior when not used carefully.

Hello sir,

I am getting an output : Binary representation: 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 1

my code:

[bold] Not sure why I'm getting the leading '0', in the output [/bold]

Hello sir,

Please ignore my last question. I figured it out.

Also, the given solution can be modified as -

//To avoid the leading zero

So, your output will be: 11111111111111111111111111110001

instead of 011111111111111111111111111110001.

Please correct me if I'm wrong.

I have just one question, and it is not related to code itself in the quiz, but the math.

How should I approach figuring out the math to writing the code for the factorial and the sum of digits. Do I just write code and work by trial and error, or am I expected to have level of math knowledge to go about the quiz questions?

Hi Nicholas!

All the math you need in explained in the quiz, the rest is coding.

Hi Alex,

Long time no see, been busy with way too many other things,

Quick question about the fibonacci program, it seems very slow, am I doing something wrong, I am sure I wrote a PHP script that calculated n fibonacci sequences much more quickly using a formula from wikipedia of all places, any advice on this would be greatly appreciated.

Great to be back

Jon

Hi Jonathan!

Recursion is slow and should be avoided. You probably used an iterative approach in PHP.

Thanks for your reply nascardriver

it must be, whilst I know that PHP is based on C and C++, the speed differential was massive, I remember calculating the first million prime numbers on the same day and that completed in about 15 seconds(hmm that does seem too fast I'll try it again, just to be sure) but the fibonacci calculation here looks broadly the same as the one I found on the wiki except everything was in a master function and then returned the result per number ... weird

Hmm it seems that I got to iteration 47 and that gave me a minus result so I have obviously overshot the int limit (will have to try it with a double), I forget PHP tends to sort this stuff out in the background as it is not so type dependent.

> first million prime numbers [...] in about 15 seconds

I just tested, it took about 50 seconds. 15 seconds seems realistic.

> will have to try it with a double

You don't need floating point numbers, use an @std::uint64_t.

Ok so I re-visited this php version and it was written recursively so I came up with a php version of the recursive function and compared it to the C++ version, added some timing functions to both and it worked as it should do here are the 2 versions

php version

This took 93.6 seconds to calculate the first 40 numbers starting from 0 (0-39)

and the C++ version

completed in 23.3 seconds for the same calculation

I left the timing code in both to show how I did it

Jon

Hi! First, thanks for writing and updating this web site and for still actively answering questions!

For 3b, I came up with a slightly different solution and just wanted to verify it. Instead of making the passed variable unsigned, I'm checking the input here:

Aside from it being a bit more verbose and crude, is there anything syntactically wrong with this answer?

I don't see anything syntactically wrong at a glance.

A few minor things:

1) intUser = intUser * -1; can be simplified as intUser *= -1 or intUser = -intUser.

2) I don't see how this handles the case where the user inputs 0.

I have a function which I am using to parse an xml file with a single node named m_labelNodeName

The question I have is how on earth does line 14 "curNode = curNode->next;" ever get called; it does because if it is not there it will create an infinite loop, but I just don't see how it works.

Hi tim!

Example with one child in the root element.

First call:

curNode is not a nullptr, the while loop is entered, does it's stuff and calls parse_xml with curNode->children.

Second call:

curNode is not a nullptr, the while loop is entered, does it's stuff and calls parse_xml with curNode->children.

Third call:

curNode is a nullptr, parse_xml returns, the second call continues execution at line 14.

You can try this yourself using a debugger, most IDEs have a debugging feature.

References:

* Lesson 1.11 - Debugging your program (stepping and breakpoints)

* Lesson 1.11a - Debugging your program (watching variables and the call stack)

Ahh, now I get it; it would have been far more readable if it was written thus though:

Thanks for your explanation.

That doesn't work, because that way you're passing a different node the parse_xml.

Ok, now I am really confused: As far as I can see parse_xml(curNode->children); doesn't exit the loop until it has called curNode = curNode->next; Because curNode is a pointer it must therefore change before it is called because it is scoped.

i.e. it will not call the function until it has exited the loop and by that time it has changed the address that curNode points to.

I have tried this and it does appear to work, but my test example is very simplistic so it could be more good luck than good management.

UPDATE- I have just tried this on a more complex example and your are of course right, but I just don't understand why. What stops parse_xml() form calling itself but just passing itself a nullptr? Shouldn't it just jump over line 14?

On line 10 in the function sumTo, shouldn't the variable value be sumto instead?

No, function sumTo() is calling itself in this case, with variable sumto as a parameter.

Ok, but I still don't understand where the variable named "value" comes from.

Oh, sorry! My mistake. I changed the name of the variable and missed that instance. It's been changed to "sumto" now.

Regarding the given solution for 3b.

1. You don't need two function calls to get the result.

2. You don't need the static cast, although there is nothing wrong with using it.

Or as Donlod showed us in his example, we can do the conversion by making the parameter of the function definition unsigned.

Hi Peter!

2. It is a problem when using uniform initialization.

Hi nascardriver,

Is this related to the binaryOut() code or something else? Please elaborate... thanks.

Very instructive nascardriver... my mind is still reeling from this new information. We need to add one more possibility:

Updated the quiz answer, as this is definitely more elegant than what I came up with. Thanks for re-pointing me at Donlod's solution.

The solution given for 3a does not work for the number 0. Something like the following is needed:

The question tells the user to assume a positive integer. We address the 0 case in 3b.

Quiz item 2 doesn't consider negative integers, so the solution needs to be something like

For simplicity, I added a constraint to the program to assume positive inputs.

Quiz item 1: "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). "

It is the sum of all the digits used to express the integer, not "all the numbers in the integer."

Clarified. Thanks!

Regarding the factorial function: since the text gives 0!==1, the definition becomes:

0! = 1

n! = n*(n-1)! for n > 0

and the code to include 0 looks like

However, this and the example given also needs to error check for negative numbers.

Updated per your suggestion. Thanks for pointing out the error!

In the section “A more useful example” the initial comment could be made clearer. As it stands:

1. It was not made clear in the comment that only integers are involved. (If the value is greater than 1, then there are an infinite number of numbers in the interval and the sum is infinite.) We have to read the function definition to find out that this is only for integers.

2. It is not clear until the function definition is read what type “value” is.

3. Although value is inclusive, there is no mention of whether or not 1 is also inclusive.

4. It isn’t clear from the comment what happens when the value is outside the range. To find out, we would have to look at the code itself. In fact, the way the function is written, it is the sum of all the integers from 0 (inclusive) to value (inclusive). Thus the function can be simplified:

If would also be instructive to explain why we should not write

More Issues:

• there really isn’t any reason to exclude negative numbers, so we could re-write the function to allow value to be negative and produce the sum from 0 (inclusive) to value (inclusive) as

• The given function really should not be written as a recursive function, because the sum of the first n integers (starting at 1) is n*(n+1)/2.

Thanks for the feedback! It was my assumption that users _would_ read the code sample, because it's short and right at the top of the article. From that:

1) It's pretty clear that this is only for integers, as the sumto parameter is an integer. I also updated the comment to make it clear this function is intended to sum integers.

2) I don't think this is an issue, as you're supposed to read the code.

3) Added a note that 1 is inclusive in the comment

4) Added a note about how this function handles negative numbers. I agree the function could be simplified by removing the middle use case, but my 2c is that this makes the function harder to understand for learning (why may be slightly clearer with the comments I added). This also makes the function recurse one additional time for normal input, which makes the examples more complex.

5) Good call on --sumto vs sumto - 1. Added a note about that.

6) Agreed both that we could make this function handle negative numbers and that we should use iteration over recursion here -- but in both cases we haven't done so, since the point here is to show how recursion works with a simple example. The former suggestion adds complexity and the latter makes the example unsuitable for its intended purpose. :)

You might want to use an alternative to the sum of the first n integers, say a function that returns the value of pi using formulas such as

π = 4*(1 - 1/3 + 1/5 - 1/7 + 1/9 - 1/11 + ... .

or

π = SQRT( 6 * (1/1^2 + 1/2^2 + 1/3^2 + 1/4^2 + 1/5^2+…)

(where ^ is used to represent exponentiation)

(see http://www.geom.uiuc.edu/~huberty/math5337/groupe/expresspi.html)

So this is the solution i came up with for 3b:

As far as i understand the logic behind printBinary, it checks in every recursion step if the rightmost bit of the current number is either 1 or 0 by calculating n % 2. If the number is higher than 1 the number is divided by 2 first which leftshifts the binary representation resulting in having the next bit as the rightmost one. And because this is done recursively it actually starts at the leftmost bit of the original number n first.

Hi Donlod!

You understood correctly. (n % 2) returns the remainder of a division by 2, which is essentially the least significant bit.

Suggestions:

* Line 17: Initialize your variables with uniform initialization

* Line 22: Inconsistent use of '\n' and @std::endl. If you don't have a reason to mix them pick one and stick to it.

* Line 24: Don't use @system unless you have to. "pause" is a Windows-only command, it won't work on other platforms. Use @std::cin.ignore instead. If you do need @system use @std::system.

> * Line 22: Inconsistent use of '\n' and @std::endl. If you don't have a reason to mix them pick one and stick to it.

Used those \n\n in order to have an empty line between the binary output and the "press any key to continue ... " at the end of the program just for readability. The problem here is that printBinary() does not std::endl or \n because it uses a loop to print the numbers in one line. Is it better to use cout << '\n' << endl? What do you suggest?

> * Line 24: Don't use @system unless you have to. "pause" is a Windows-only command, it won't work on other platforms. Use @std::cin.ignore instead. If you do need @system use @std::system.

Im using system("pause") because the cmd window closes when it reaches return in main making it impossible to read the output. Usually im using std::cin.get but it does not work when any input was done previously (i think this is because return key is still in the buffer after making the input for >> x). std::cin.ignore also does not seem to work.

Hi Donlod,

Really nice solution for printBinary! I had not thought of doing the conversion by typing the parameter to unsigned.

I had already solved 3a in a less efficient way than you had done, so I decided to try and keep up the tradition with 3b. As far as I can tell, this solution still works.

hmm.

Concerning the problem 3b, I tried to go by the hint but I think my mind was too focused on a different solution from the beginning.

Well, at least, at the end of my convertToBinary function I still have the binary representation of the integer [ha, ha, ha!].

Hi radu!

I won't check you conversion logic, because I don't like this quiz, but there are some things worth mentioning.

General:

* Use uniform initialization (Line 64, 74).

* I don't know how well regex is implemented in C++, but generally, you should avoid it, especially for easy tasks like this and even more, because @std::istringstream::operator>> is already performing a number verification for you. Check it's error flag and @std::istringstream::peek to see if everything was successfully extracted. Anyway, your expression considers \123 to be a valid number.

@main:

* Why do you use a short for this array? You're only storing 0 or 1. Use a bool or char.

* You don't need to type out all those zeroes.

* Prefer ++prefix over postfix++

* Why did you name the iterator "j"? "i" is the first choice.

@convertToBinary:

* There's no need for a switch, use

* @binary_representation::add_one_bit is only used in this function, don't declare it globally if you don't need it.

@getIntegerInput:

* Why do you initialize @input to "0"? Leading zeroes are ignored.

Thanks, nascardriver!

As always, useful feedback.

I first used regex for a problem where I had to validate the input consisting in one of the characters +,-,*,/.

The function looks like that:

I liked it and thought to use this scheme even further [I really dislike considering input like "124f" a valid one when I expect integers, or "aas+f" a valid one when I expect "+" only].

@ "your expression considers \123 to be a valid number" - can it be because of a different compiler? On mine it works just fine, but I see your point about avoiding regex in this case.

@ "Check it's error flag and @std::istringstream::peek to see if everything was successfully extracted" - I'm not familiar yet with this kind of things [well, it's a beginning for everything in life...]

@ "Why do you use a short for this array? [...] Use a bool or char." - bool was my first choice but I didn't know if, in terms of performance, "true+true" or "true+1" isn't bad comparatively to "1+1".

I didn't take in consideration char type [because of the arithmetics involved] so I just shortened the array.

@ "Why did you name the iterator "j"? "i" is the first choice." - like declaring wrong globally 'add_one_bit', these are scraps from a different version of the program, which I forgot to adapt accordingly.

@ "Why do you initialize @input to "0"? Leading zeroes are ignored." - I just put a value for initialization. Don't know if it matter or not? I guess in this particular case, initialization could be omitted anyway, because it's a string and the user cannot input bad values.

@ "convertToBinary: There's no need for a switch [...]" - yeah, I rewrited the code a bit now [the 'sign' variable value can be used in the array to keep the info about the sign of the integer, if - potentially - I want to convert the array back into an integer; of course, with an increase in length of array]. But, I think the program is a bit off-topic already.

> "your expression considers \123 to be a valid number"

I take that back, I was confusing the literal backslash and the escaping backslash. C++ features raw strings which you can use to treat every character as that exact character, without escaping. I like those for paths and regex.

Output

Hello" Wor\l'd

> I'm not familiar yet with this kind of thing

It's only partially covered on learncpp in lesson 5.10. Here's an example:

std::ios::fail http://www.cplusplus.com/reference/ios/ios/fail/

std::istream::peek http://www.cplusplus.com/reference/istream/istream/peek/

> initialization could be omitted anyway

Don't you omit initialization! Initialize strings with an empty string

Is there anything wrong with not using the whole unsigned int thing? I feel like it's just simpler

Well, for one, your solution doesn't work. :) When I plug in -15, it gives me 1111 instead of 11111111111111111111111111110001

Oversight of the century. Tried testing values and mistook the actual results for the correct results.

Just racked my brain for an hour trying to make it work without unsigned int for sheer fun using two's compliment and loops on loops, but I surrender... too much.

Thanks Alex

Hi Alex,

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

can you please explain this in more detail and why casting to unsigned int as in the following code gives the output : 4294967281

The binary number 1111 1111 1111 0001 can be interpreted in two ways. If interpreted as an unsigned number, it means 4294967281. If interpreted as a signed number, it means -15 (assuming a two's complement representation for signed numbers). The only difference between the two is the type information.

Hi! In this lesson you wrote "It turns out that you can always solve a recursive problem iteratively --". Though it's rare, this is not actually quite true in all cases e.g. Ackermann function. Was this omitted on purpose or by accident?

Hi Vili!

The Ackermann function can be calculated without recursion, eg. by using a stack.

It's just cannot be calculated by using for-loops alone.

I didn't pay a lot of attention during that class so I don't know if there is a function that cannot be calculated without recursion, I guess there's always a way without recursion though.

Ackermann functions can be written iteratively. See this thread for examples.

It's actually pretty simple to see that any recursive function can be solved iteratively. When you call a recursive function, you're just leveraging the call stack to temporarily store the value of the current parameters while you do another iteration of the function. You can do this entirely iteratively if you maintain your own stack and do all the pushes and pops yourself.

Another helpful view: when converting from recursion to iteration you are just moving the iterative control operation from inside the function to outside the function.

Hi Alex,

Thank you so much for this guide, it's written just as I'd like.

The solution for 3b) from CrazyL seems to lack returns in the functions?

I was surprised to see two functions in the solution, I solved it in a different manner by simply casting the number to an unsigned integer before calling the function from 3a). It seems to work, outputting "11111111111111111110101001001101" for an input of "-5555".

How come you used two functions?

My solution:

Hi Dag!

> The solution for 3b) from CrazyL seems to lack returns in the functions?

It is indeed missing a return statement in @main. void functions don't need to return explicitly.

I don't know why Alex used two functions, I guess he wanted to build on top of the solution of the previous quiz, one function seems to be fine.

To your code

Line 11: Initialize your variables.

Line 1,8: Inconsistent curly braces.

Line 13-18: This code should be moved into @printBinary

Line 13-18 should only run once, not on every call to printBinary. As such, it was deliberately put there as per the general principle of minimizing execution time.

As for braces, initialization and indenting, I'm still not where I'm used to doing it just one way. I normally put the "{" on the same line as the function declaration, but my IDEs default for main() is on the next line.

> Line 13-18 should only run once, not on every call to printBinary

Now, that's the reason why Alex has two functions.

Yup. printBinary gets called once, printBinaryDigits can get called multiple times.

They definitely could have been combined -- if printBinaryDigits had a second parameter called "firstIteration" that defaulted to true, the logic in printBinary could have been rolled into printBinaryDigits. That's a little more concise, but I'm not sure it's as easy to follow, since you have two parameters that can change each iteration instead of one.

Hi Alex - I wrote it to return a string, as opposed to creating something that was discarded as it was created.

I think I've got it down to as little as I can, but wondering if it is OK creating the string that I am returning after all

of the characters are defined. Seems a bit backwards, but the other options I've thought of involve pointers and tracking position

of the bit I am currently working on, or passing the string down as is, or by reference in addition to the number being worked on.

Regards (and thank gawd pointers is over - my head is still ringing after doing ch 6 best part of 3 times)

Doh... Line 24/25 can be reduced to just

Hi Angus!

Don't break your head trying to optimize this too far, in a real scenario recursion wouldn't be used for this task.

Line 5: Interesting, I like it.

Line 23-25: In fact, this can be reduced even further

This constructor will create a string containing 1 repetition of @bit.

Cheers nascardriver.... I tried skipping the creation of the variable 'bit' and just creating it on the fly as part of line 13, but couldn't make creation of the char and the return work, and for that reason, didn't try to squeeze creation of the string and the return on one either...

I'm now wondering why I could have created a string on a return line, but not a char...

Although having a 4 line recursive function returning a string is still pretty cool methinks...

As for line 5, that partly came from playing with 8-bit machines almost 30 years ago - when you could add anything to anything you liked; and partly from remembering that chars are essentially 8-bit numbers, so surely I could add a number to another one...

> I’m now wondering why I could have created a string on a return line, but not a char

In the context of the line

I wanted to remove `bit` variable, but couldn’t work out how to do that. adding to a char wasn’t something it seemed happy with…

Sorted it! …. Had to use a static cast…

Here is what I came up with for 3b. Seems to work.

Instead of having my base case at 0, I put it at <2, and then printed the left most digit in a separate line. That way I was able to account for printing 0 without a explicitly treating that case.

Hi Alex,

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

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

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

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

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

Thank you and have a nice day in advance!.

Hi Stephane!

Your code formatting is terrible, I'll usually leave it up to the coder but this is a mess.

I'll use the following code to refer to line numbers. I'm not going to list all of the issues with your code, so please just read though this and compare it to your code to see what I changed. If you have any question about my modifications feel free to ask.

Why does binarySearch find 11 when the vector is unsorted?

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

Why does your program crash when you replace 11 with 0?

Line 21: (1 < 0) is false, line 27: mid is the first element of the vector, mid-1 does not exist.

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

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

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

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

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

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

Here is my code to distribute money into Rupee(Indian currency) notes.

how can I use recursion to make it short?

#include <iostream>

void count (int x)

{

int f = 0;

for(; x>=2000; f++ )

{

x-=2000;

}

std::cout << f << " 2000 note \t " ;

f =0;

for(; x>=500; f++)

{

x-=500;

}

std::cout << f << " 500 note \t " ;

f =0;

for(; x>=100; f++)

{

x-=100;

}

std::cout << f << " 100 note \t " ;

f =0;

for(; x>=50; f++)

{

x-=50;

}

std::cout << f << " 50 note \t " ;

f =0;

for(; x>=20; f++)

{

x-=20;

}

std::cout << f << " 20 note \t " ;

f =0;

for(; x>=10; f++)

{

x-=10;

}

std::cout << f << " 10 note \t " ;

f =0;

for(; x>=5; f++)

{

x-=5;

}

std::cout << f << " 5 note \t " ;

f =0;

for(; x>=2;f++ )

{

x-=2;

}

std::cout << f << " 2 note \t " ;

f =0;

for(; x>=1; f++)

{

x-=1;

}

std::cout << f << " 1 note \t " ;

f =0;

}

int main()

{

std::cout << " Enter amount of rupees " ;

int g;

std::cin>>g;

count(g);

return 0;

}

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

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

I agree with Alex that recursion doesn't seem to fit this problem, although we could be wrong. The iterative solution is pretty straightforward. Something like:

You have an interesting use of a for loop used as a while loop. Any special reason for this?

Here is my code for quiz 3

#include <iostream>

void dtob( int y)

{

if ( y ==1 )

{

std::cout << "1";

return;

}

dtob(y/2);

std::cout << y%2;

}

int main()

{

dtob(6);

return 0;

}

is the code efficient?

Here is my code for quiz 2

#include <iostream>

double sumnumbers( double y)

{

if (y <10)

return y;

int x = y/10;

double z = y - (x*10);

return sumnumbers( x) + z;

}

int main()

{

std::cout<< sumnumbers(93427);

return 0;

}

It is easy to understant

here is my program for factorial of number.

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

#include<iostream>

using namespace std;

long long factorial(int x)

{

if(x==0)

return 1;

else

{

return factorial(x-1)*(x);

}

}

int main()

{

int n;

cin>>n;

cout<<factorial(n);

}

You could return it as a double, or use a library/class that supports bigger integers (there are free ones available online).

okay, thank you