Understanding recursion in c++

Question

I think I'm understanding the principle behind recursion, for example the stack like behaviour and the way the program "yo-yo's" back through the function calls, I seem to be having trouble figuring out why certain functions return the values that they do though, the code below returns 160, is this due to the return 5 playing a part, I think I'm right in saying it will go 4*2 + 8*2 + 12*2 etc.. I'm really doubting that when changing my values though.

Would anybody be able to offer a brief explanation as to which values are being multiplied?

cout << mysteryFunction(20);

int mysteryFunction (int n)
{
 if(n > 2)
  {
   return mysteryFunction(n - 4)*2;
  }

   else return 5;
}

the formula is: `5*2^x` when x in the formula given by: `20/4 = 5`. therefore: `5*2^5 = 160` — SHR, Apr 24 '15 at 15:22

score 4 · Answer 1 · answered Apr 24 '15 at 15:24

If you are interested in actual call stack:

mysteryFunction(20):
[n > 2] -> mysteryFunction(16) * 2
           [n > 2] -> mysteryFunction(12) * 2
                      [n > 2] -> mysteryFunction(8) * 2
                                 [n > 2] -> mysteryFunction(4) * 2
                                            [n > 2] -> mysteryFunction(0) * 2
                                                       [n <= 2] -> 5
                                            5 * 2 = 10
                                 10 * 2 = 20
                      20 * 2 = 40
           40 * 2 = 80
80 * 2 = 160

More generally: 20 = 4*5, so 5 * 2^5 = 5 * 32 = 160.

score 3 · Answer 2 · answered Apr 24 '15 at 15:23

3

mysteryFunction(20) => 80 * 2 = 160
mysteryFunction(16) => 40 * 2 = 80
mysteryFunction(12) => 20 * 2 = 40
mysteryFunction(8) => 10 * 2 = 20
mysteryFunction(4) => 5 * 2 = 10
mysteryFunction(0) => 5

answered Apr 24 '15 at 15:23

αƞjiβ

3,056
14
58
95

Thank you, this suddenly makes alot of sense. – beardedranga Apr 24 '15 at 15:26

score 1 · Answer 3 · answered Apr 24 '15 at 15:28

Recursion doesn't yo-yo, it just nests deeply.

In you case, the if statement results in either a) the function being called from within the function, or b) a return value... let's look at it running...

 A- mysteryFunction(20)
 B-- mysteryFunction(16)
 C--- mysteryFunction(12)
 D---- mysteryFunction(8)
 E----- mysteryFunction(4)
 F------ mysteryFunction(0) <-- this is the first time (n > 2) is false

Line F is the first time n > 2 is false, which means it returns a 5.

Line F was called by line E, and the value line E gets (5) is multiplied by 2 and returned. So line E returns 10.

Line E was called by line D... and the value it gets (10) is multiplied by 2 and returned, so line D return 20.

... and so on.

Quick version... let's order these to match the order they act on the value...

 F: 5
 E: F * 2 = 10
 D: E * 2 = 20
 C: D * 2 = 40
 B: C * 2 = 80
 A: B * 2 = 160

I know this post is 4 years old but holy shit thank you!! I was having trouble understanding what happened to the return values when using recursion and this is exactly what I needed. THANKS!! — wiregh0st, Dec 06 '19 at 18:43

score 0 · Answer 4 · edited May 23 '17 at 11:58

I will suggest you to read this article on Wikipedia about recursion: http://en.wikipedia.org/wiki/Recursion In a nutshell a recursive function is one that calls itself until you reach a base case(this is the key). If you don't reach the base case your function will run forever(infinite loop). In the case of your function, get a piece of paper a follow its path picking any number as example, it is the best way to figure out how it works. The factorial is a good example: the factorial of a number, let's say 5 is !5 = 5 * 4 * 3 * 2 * 1 which is 120. Try it, the principles for recursion is the same regardless the problem. Here's an example for a factorial function. Recursion in c++ Factorial Program

score 0 · Answer 5 · answered Apr 24 '15 at 15:27

Just go through the code and substitute the values.

mysteryFunction(20)                     -> mysteryFunction(16) * 2
mysteryFunction(16) * 2                 -> mysteryFunction(12) * 2 * 2
mysteryFunction(12) * 2 * 2             -> mysteryFunction(8)  * 2 * 2 * 2
mysteryFunction(8) * 2 * 2 * 2          -> mysteryFunction(4)  * 2 * 2 * 2 * 2
mysteryFunction(4)  * 2 * 2 * 2 * 2     -> mysteryFunction(0)  * 2 * 2 * 2 * 2 * 2
mysteryFunction(0)  * 2 * 2 * 2 * 2 * 2 -> 5 * 2 * 2 * 2 * 2 * 2 -> 160

Understanding recursion in c++

5 Answers5