向量双重递归

问题描述 投票：0回答：1

我试图弄清楚在以下示例中双重递归是如何工作的：

#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]<<" ";
}

输出：

21 33 46 60 75

我明白 21 是如何被推入向量的。但在那之后，我不明白调用哪个递归（左或右），以及如何遵循它直到正确的输出。

您能一步一步向我解释一下这个特定程序是如何执行的吗？

c++ function recursion
1个回答
0
投票

来自您的OP：

if (a <= 0 || b <= 2) return a;

以上是有助于防止递归永远递归的基本情况。

a = F(v, a - 1, b) + F(v, a, b);
v.push_back(a);

假设先执行左递归

第一项是调用（根据假设）。最初b=7，a=15。然后，由于 a 在调用中立即递减，而 b 在 F 内部递减，因此 a 和 b 一起减少。由于 a-b > 2，基本情况将在 a 之前达到 b == 2 <=0.
在递归中，第一项被一遍又一遍地调用，直到 b == 2。然后才调用第二项，并且现在 a 在调用中不会递减。在第二个 F 内，再次调用第一个 F（根据您的假设）。这次，b 仍然是 2，因为直到基本情况之后它才会递减。在调试器中，请务必观察调用堆栈并观察递归展开。

一个棘手的项目。调用第一个 F 时的 arg a 比调用第二个 F 时的 arg a 小 1。请记住一点。

我很好奇结果可能会有多大不同。这些变化由添加的 

a-1
标志 
flag_am1
控制。
flag_am1
= 1：确定性，首先评估 a-1 项。
flag_am1
= 0：确定性，其次评估 a-1 项。
flag_am1
= -1：与 OP 相同
flag_am1
= -2：与OP类似，只是交换了两个函数的顺序。
请注意，对于 
flag_am1
= -2 的情况，

#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;
}

查看四组输出时要记住的重要一点是，对于 

flag_am1
= -1 或 = -2 的情况，您的结果可能会有所不同。

输出：

         *** 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
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.