c++ - 在 C++ 中使用递归函数

Question

// Ex5_15.cpp (based on Ex5_01.cpp)
// A recursive version of x to the power n
#include <iostream>
using std::cout;
using std::endl;
double power(double x, int n); // Function prototype
int main(void)
{
    double x(2.0); // Different x from that in function power
    double result(0.0);
    // Calculate x raised to powers -3 to +3 inclusive
    for(int index = -3; index <= 3; index++)
    cout << x << “ to the power “ << index << “ is “ << power(x, index)  <<  endl;
    return 0;
}
// Recursive function to compute integral powers of a double value
// First argument is value, second argument is power index
double power(double x, int n)
{
    if(n < 0)
    {
        x = 1.0/x;
        n = -n;
    }
    if(n > 0)
        return x*power(x, n-1);
    else
        return 1.0;
    }

我在学校上编程课。这是书中给出的递归函数的示例。我不太明白他们在做什么以及涉及的技术。我只是想知道是否有人可以向我解释这一点，或者至少为我指明正确的方向，以便我更好地理解这项技术。

Answer 1

让我们看看调用 power(2,3) 时会发生什么:

double power(double x, int n) { // x = 2, n=3; 
   if (n<0) {...}  // false, so skip the brackets  
   if (n>0)        // true
      return x*power (x; n-1);  // call power() again, with different paraleters
   ...             // the rest is skipped
}

所以它返回 2 * power(something)。在能够计算返回值之前，power() 必须再次调用自身。这是一个递归调用。您可以将其视为将要执行的函数的另一个拷贝，具有自己的变量(即不触及调用实例的局部变量)。

• 现在调用 power() 时参数为 x=2 和 n=2。执行流程类似，它将返回 2 * power(x, n-1) 但 n-1 现在是 1。所以这里又是一个递归。

  • 现在用 x=2 和 n=1 调用 power()。这将返回 2 * power(x, n-1)，但 n-1 现在为 0。再次递归；

    • 最后，将在 x=2 和 n=0 的情况下调用幂。这里的执行流程将跳过两个 if 并最终执行 elese 分支，因为 n 为 0。它将返回 1。

      现在我们有了所有的元素，可以通过结束这些连续的调用来计算值(value)

所有这些都可以用图形显示:

power(2,3) 
   |
   +--> 2 * power(2,2)
              |
              +--> 2* power(2,1) 
                        |
                        +--> 2* power(2,0) 
                                  |
                                  1

所以最后它返回 2*2*2*1，即 2^3，即预期结果。

通过进一步推广这个推理，您可以使用 mathematical induction证明对于任何 n>=0，power (x, n) 将返回 x^n。我让你自己看看当 n 为负时会发生什么来完成练习。

还有一些 furhter reading这可能有助于从不同的角度进行一些图形解释。