admin管理员组文章数量:1434900
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?
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?
Share Improve this question edited Nov 17, 2024 at 1:34 Remy Lebeau 602k36 gold badges508 silver badges853 bronze badges asked Nov 16, 2024 at 22:03 codproecodproe 12111 bronze badges 13 | Show 8 more comments2 Answers
Reset to default 2C++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
In short
The precedence rules of C++ do not define if the left or the right term of your double recursion is called first. In fact, depending on the order chosen by the compiler, you may obtain different results with the same code.
In depth demonstration
From your OP:
if (a <= 0 || b <= 2) return a;
Above is the base case that helps keep the recursion from recursing forever.
a = F(v, a - 1, b) + F(v, a, b);
v.push_back(a);
assuming that left recursion is first executed
The first term is call (per assumption). Initially b=7, a=15. Then since a is immediately decremented in the call and b is decremented inside F, both a and b decrease together. Since a-b > 2, the base case will hit b == 2 before a <=0.
In the recursion, the first term is called again and again until b == 2. Only then is the 2nd term called and now a is not decremented in the call. Inside the 2nd F, the first F is called again (per your assumption). This time, b is still 2 as it is not decremented until after the base case. In your debugger, be sure to observe the Call Stack and watch the recursions unwind.
One tricky item. The arg a when calling the first F is one less than the arg a when calling the second F. Just keep point in mind.
I was curious how different the results might be. The variations are controlled by an added a-1 flag, flag_am1.
flag_am1 = 1: Deterministic with the a-1 term evaluated first.
flag_am1 = 0: Deterministic with the a-1 term evaluated second.
flag_am1 = -1: Identical to the OP
flag_am1 = -2: Similar to the OP except that the order of the two functions are swapped.
Note that for the flag_am1 = -2 case,
#include <iostream>
#include <vector>
int F(std::vector<int>& v, int a, int& b, int flag_am1) {
// std::cout << flag_am1 << ": ENTER: a=" << a << " b=" << b << std::endl;
if (a <= 0 || b <= 2)
{
std::cout << flag_am1 << ": EXIT: a=" << a << " b=" << b << std::endl;
return a;
}
b -= 1;
if (flag_am1 == 1)
{
// std::cout << "1.0: a=" << a << " b=" << b << std::endl;
a = F(v, a - 1, b, flag_am1);
std::cout << "1.1: a=" << a << " b=" << b << std::endl;
a += F(v, a, b, flag_am1);
std::cout << "1.2: a=" << a << " b=" << b << std::endl;
}
else if (flag_am1 == 0)
{
// std::cout << "0.0: a=" << a << " b=" << b << std::endl;
a = F(v, a, b, flag_am1);
std::cout << "0.1: a=" << a << " b=" << b << std::endl;
a += F(v, a - 1, b, flag_am1);
std::cout << "0.2: a=" << a << " b=" << b << std::endl;
}
else if (flag_am1 == -1) // like the OP
{
std::cout << "-1.0: a=" << a << " b=" << b << std::endl;
a = F(v, a - 1, b, flag_am1) + F(v, a, b, flag_am1);
std::cout << "-1.1: a=" << a << " b=" << b << std::endl;
}
else{ // flag_am1 == -2
std::cout << "-2.0: a=" << a << " b=" << b << std::endl;
a = F(v, a, b, flag_am1) + F(v, a - 1, b, flag_am1);
std::cout << "-2.1: a=" << a << " b=" << b << std::endl;
}
v.push_back(a);
std::cout << " ** v.push_back(" << a << ")" << std::endl;
return a;
}
int main() {
std::vector<int> v{};
int b = 7;
v.resize(0);
b = 7;
std::cout << "\t *** a-1 flag is 1" << std::endl;
F(v, 15, b, 1);
for (int i = 0;i < v.size();i++)
{
std::cout << v[i] << " ";
}
std::cout << "\n" << std::endl;
v.resize(0);
b = 7;
std::cout << "\t *** a-1 flag is 0" << std::endl;
F(v, 15, b, 0);
for (int i = 0;i < v.size();i++)
{
std::cout << v[i] << " ";
}
std::cout << "\n" << std::endl;
v.resize(0);
b = 7;
std::cout << "\t *** a-1 flag is -1 (effectively like the OP)" << std::endl;
F(v, 15, b, -1); // like original OP
for (int i = 0;i < v.size();i++)
{
std::cout << v[i] << " ";
}
std::cout << "\n" << std::endl;
v.resize(0);
b = 7;
std::cout << "\t *** a-1 flag is -2 (similar to OP but two F terms reversed)" << std::endl;
F(v, 15, b, -2); // like original OP except the a-1 term is 2nd
for (int i = 0;i < v.size();i++)
{
std::cout << v[i] << " ";
}
std::cout << "\n" << std::endl;
}
The important thing to remember when looking at the four sets of outputs, for cases flag_am1 = -1 or = -2, your results may vary.
Output:
*** a-1 flag is 1
1: EXIT: a=10 b=2
1.1: a=10 b=2
1: EXIT: a=10 b=2
1.2: a=20 b=2
** v.push_back(20)
1.1: a=20 b=2
1: EXIT: a=20 b=2
1.2: a=40 b=2
** v.push_back(40)
1.1: a=40 b=2
1: EXIT: a=40 b=2
1.2: a=80 b=2
** v.push_back(80)
1.1: a=80 b=2
1: EXIT: a=80 b=2
1.2: a=160 b=2
** v.push_back(160)
1.1: a=160 b=2
1: EXIT: a=160 b=2
1.2: a=320 b=2
** v.push_back(320)
20 40 80 160 320
*** a-1 flag is 0
0: EXIT: a=15 b=2
0.1: a=15 b=2
0: EXIT: a=14 b=2
0.2: a=29 b=2
** v.push_back(29)
0.1: a=29 b=2
0: EXIT: a=28 b=2
0.2: a=57 b=2
** v.push_back(57)
0.1: a=57 b=2
0: EXIT: a=56 b=2
0.2: a=113 b=2
** v.push_back(113)
0.1: a=113 b=2
0: EXIT: a=112 b=2
0.2: a=225 b=2
** v.push_back(225)
0.1: a=225 b=2
0: EXIT: a=224 b=2
0.2: a=449 b=2
** v.push_back(449)
29 57 113 225 449
*** a-1 flag is -1 (effectively like the OP)
-1.0: a=15 b=6
-1.0: a=14 b=5
-1.0: a=13 b=4
-1.0: a=12 b=3
-1.0: a=11 b=2
-1: EXIT: a=10 b=2
-1: EXIT: a=11 b=2
-1.1: a=21 b=2
** v.push_back(21)
-1: EXIT: a=12 b=2
-1.1: a=33 b=2
** v.push_back(33)
-1: EXIT: a=13 b=2
-1.1: a=46 b=2
** v.push_back(46)
-1: EXIT: a=14 b=2
-1.1: a=60 b=2
** v.push_back(60)
-1: EXIT: a=15 b=2
-1.1: a=75 b=2
** v.push_back(75)
21 33 46 60 75
*** a-1 flag is -2 (similar to OP but two F terms reversed)
-2.0: a=15 b=6
-2.0: a=15 b=5
-2.0: a=15 b=4
-2.0: a=15 b=3
-2.0: a=15 b=2
-2: EXIT: a=15 b=2
-2: EXIT: a=14 b=2
-2.1: a=29 b=2
** v.push_back(29)
-2: EXIT: a=14 b=2
-2.1: a=43 b=2
** v.push_back(43)
-2: EXIT: a=14 b=2
-2.1: a=57 b=2
** v.push_back(57)
-2: EXIT: a=14 b=2
-2.1: a=71 b=2
** v.push_back(71)
-2: EXIT: a=14 b=2
-2.1: a=85 b=2
** v.push_back(85)
29 43 57 71 85
本文标签： cDouble recursion with vectorsStack Overflow
版权声明：本文标题：c++ - Double recursion with vectors - Stack Overflow 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.betaflare.com/web/1745642056a2667916.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
F(v, a - 1, b) + F(v, a, b)contains two subexpressions (the two calls) that can be evaluated in any order. The order is unspecified. Therefore, it does not make much sense to reason about the order of the elements ofv. See: en.cppreference/w/cpp/language/eval_order. – Marco Bonelli Commented Nov 16, 2024 at 22:07auto left = F(v, a - 1, b); auto right = F(v, a, b); a = left + right;would be fine. – Marco Bonelli Commented Nov 16, 2024 at 22:28