I'm trying to figure out how double recursions work in the following example:
#include <iostream>
#include <vector>
int F(std::vector<int> &v, int a, int &b) {
if (a <= 0 || b <= 2) return a;
b -= 1;
a = F(v, a - 1, b) + F(v, a, b);
v.push_back(a);
return a;
}
int main(){
std::vector<int> v;
int b = 7;
F(v, 15, b);
for(int i=0;i<v.size();i++)
std::cout<<v[i]<<" ";
}
OUTPUT:
21 33 46 60 75
I understand how 21 got pushed into the vector. But after that, I don't understand which recursion (left or right) is then called, and how to follow that until the correct output.
Could you please explain to me, step by step, how this particular program is executed?
C++17:
17 Except where noted, evaluations of operands of individual operators and of subexpressions of individual expressions are unsequenced.
The output that you have posted, will be generated only when compiler will perform evaluation of subexpression F(v, a - 1, b) before F(v, a, b) in every evaluation of expression F(v, a - 1, b) + F(v, a, b).
A quick check you can do by swapping the operands (subexpression) - F(v, a, b) + F(v, a - 1, b). With this, you may get a different output.
The recursive call trace for the given expression will be like a binary tree but there is catch here - the parameter b of function F() is a reference. Which means, any change in value b will reflect everywhere it's been referred.
For the given value of parameter a and b (a = 15 and b = 7), once the value of b will become 2, the condition b <= 2 will be satisfied and rest of the recursive calls to F() function will simply return value of a (whatever it is passed as argument in that call to function F()).
Assume, in every call to function F(), when evaluating expression F(v, a - 1, b) + F(v, a, b) expression, compiler evaluates subexpression F(v, a - 1, b) first, this is how the recursion tree will be:
(C1) [Initial value of args - a = 15, b = 7] F(v, a, b) ==> returned value discarded
|
+-------------------+
| |
(C2) F(v, 14, b) F(v, 15, b) ==> a = 60 + 15 => 75 (pushed and returned)
|
+-----------------+
| |
(C3) F(v, 13, b) F(v, 14, b) ==> a = 46 + 14 => 60 (pushed and returned)
|
+-----------------+
| |
(C4) F(v, 12, b) F(v, 13, b) ==> a = 33 + 13 => 46 (pushed and returned)
|
+-----------------+
| |
(C5) F(v, 11, b) F(v, 12, b) ==> a = 21 + 12 => 33 (pushed and returned)
|
value of b calcul- |
ated to 2 +-----------------+ +-val returned-+
| | | v
(C6) F(v, 10, 2) F(v, 11, 2) ==> a = 10 + 11 => 21 (pushed and returned)
\ | / ^
\ +------------/-val returned--+
\_______________/
|
v
Both these calls will return the value of
parameter a received (i.e. 10 and 11) because
value of parameter b is 2 now.
Stack will windup from here.
All the pending calls to function F() (right subtree's), in the
stack, will just return the value of parameter a.
Hence, the output you are getting:
21 33 46 60 75