Understanding recursion in C ++
I think I understand the principle of recursion, for example the stack behavior and the program behavior "yo-yo" back through the function calls, it seems to me that there are problems figuring out why some functions return values what they do, although the code below returns 160 it has to do with returning 5 playing a role, i think i am correct in saying it will go 4 * 2 + 8 * 2 + 12 * 2, etc. I really doubt that when my values change.
Can anyone offer a short explanation of what values are being multiplied?
cout << mysteryFunction(20);
int mysteryFunction (int n)
{
if(n > 2)
{
return mysteryFunction(n - 4)*2;
}
else return 5;
}
source to share
If you are interested in the 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
In general:, 20 = 4*5
therefore 5 * 2^5 = 5 * 32 = 160
.
source to share
Recursion is not yo-yo, it just nests deep.
In your case, the if statement results in: a) a function being called from within a function, or b) a return value ... let it work ...
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
String F is the first time it n > 2
is false, which means it returns 5.
Line F is called on line E and line of E values gets (5) multiplied by 2 and returns. So string E returns 10.
Line E is called on line D ... and the value it gets (10) is multiplied by 2 and returned, so line D returns 20.
... etc.
Swift version ... let's order them according to the order in which 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
source to share
I suggest you read this Wikipedia article on recursion: http://en.wikipedia.org/wiki/Recursion In a nutshell, a recursive function is one that calls itself until you reach the base case (that's the key) ... If you don't reach the base case, your function will run forever (infinite loop). In the case of your function, take a piece of paper following your path, typing in any number as an example, this is the best way to figure out how it works. Factorial is a good example: factorial of a number, let 5 be 5 = 5 * 4 * 3 * 2 * 1, which is 120. Try it, the principles of recursion are the same regardless of the problem. Here's an example of a factor function. Recursion in a C ++ factual program
source to share
Just go through the code and replace 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
source to share