c++ - 递归C++函数计算: Bn(a) = Bn−1(a) × Bn−2(a) where B1(a) = B2(a) = a

Question

我在计算这个特定程序的递归时遇到了一些麻烦。我尝试了几种不同的选择，但我对递归函数是全新的。我唯一可以修改的程序部分是在函数 B 的内部。此函数计算:Bn(a) = Bn−1(a) × Bn−2(a)，其中 B1(a) = B2(a) = a。所以 B1(a) = a | B2(a) = 一个 | B3(a) = a^2 | B4(a) = a^3 | B5(a) = a^5 |等等……

#include <iostream>
using namespace std;
float B(float a, int n)
{
   //Here is where I'm having an issue...
}
int main(void)
{ cout << "Input a float a, and an int n > 0: ";
   float a; int n;
   cin >> a >> n;
   cout << "B(" << a << ")_" << n << " = " << B(a,n) << endl;
   return 0;
}

Answer 1

首先处理n 为1 或2 的情况，它们被定义为返回a 而不递归。这些就是所谓的终止案例。

float B(float a, int n)
{
   if (n == 1 || n == 2) { return a; }

   // ...
}

然后你递归其他的，每次从n中减去:

float B(float a, int n)
{
   if (n == 1 || n == 2) { return a; }

   return B(a, n - 1) * B(a, n - 2);
}

如果您传入大于 2 的 n，递归调用最终将到达终止情况，执行将在该点停止，返回最终结果一直返回到第一次调用.

让我们以调用为例，B(2, 4)。这与终止情况不匹配，因此该函数将递归，如下所示:

• B(2, 4) 将返回 B(2, 3) * B(2, 2)。
• B(2, 3) 将返回 B(2, 1) * B(2, 2)。我们替换原来的这个，我们得到:(B(2, 1) * B(2, 2)) * B(2, 2)。
• 我们现在只剩下终止情况，所以我们可以用 a 的值替换它们:(2 * 2) * 2 = 2³ = 8.

就实际发生的情况(不仅仅是代数简化)而言，这将是调用树:

• B(2, 4) 不是终止情况，它会调用:
  • B(2, 3) 不是终止情况，它会调用:
    • B(2, 2) 是终止情况，返回 2。
    • B(2, 1) 是终止情况，返回 2。
    • 返回将为 2*2 = 4。
  • B(2, 2) 是终止情况，返回 2。
  • 返回将为 4*2 = 8。