递归函数导致堆栈溢出

Question

我有以下任务:

编写一个程序,询问数字和权力.编写一个递归函数,将数字作为幂.例如,如果数字为2且功率为4,则该函数将返回16.

我编写了一个程序,编译时没有错误,但是当我启动程序并输入一个值时会出现错误,说"Stack Overflow".我想我的递归函数变得无限,但我不知道如何以其他方式编写它.

这是我的代码:

#include <iostream>
using namespace std;
int powpow(int number);

int main(){
    cout<<"Enter number:";
    int x;
    cin>>x;
    cout<<"The result of ("<<x<<" * "<<x<<") * "<<x*x<<" is: "<<powpow(x);
    system("pause");
    return 0;
}
int powpow(int number){
    int result = number*number;
    return powpow(result);
}

Answer 1

您的递归没有终止条件,因此它会永远运行.

听起来好像你可能没有很好地掌握递归,所以我想从一些更简单的东西开始,斐波那契序列.

每当我们根据递归定义函数时,我们首先需要定义一个基本案例.在Fibonacci的案例中,我们有2个基本案例:

F(0) = 0
F(1) = 1

也就是说,用英语说,"0的0是0,F的1是1".或者更简单地说,如果我们将0传递给函数F,我们将得到0.如果我们通过1,我们将获得1回.

一旦我们定义了基本案例,我们就需要寻找一个递归关系.在Fibonacci的情况下,我们有以下重复:

F(n)= F(n-1)+ F(n-2)

因此n >= 2,我们可以使用上述重复.为什么？好吧,让我们尝试n = 2.

F(2) = F(n-1) + F(n-2)
     = F(1) + F(0)
     = 1    + 0
     = 1

所以现在我们知道F(2)的答案是1.而且,我们现在可以计算F(3)的答案.为什么？那么,我们需要计算F(3)？我们需要F(2)和F(1).我们现在有了这两个答案,因为F(1)是一个基本情况,我们刚刚解决了上面的F(2).

那么,现在让我们尝试编写一段伪代码来解决F.

function F(int n) {
  // handle base cases
  if (n equals 0)
    return 0
  if (n equals 1)
    return 1

  // recurrence
  return F(n-1) + F(n-2);
}

请注意,在递归函数中,我们总是在函数开头处理基本情况.如果我们没有基本情况,我们就无法定义这种复发,否则,我们将没有终止复发的终止条件.这就是为什么你总是将基本案例放在函数的开头.

现在,鉴于上述解释,另一个好的练习是为阶乘函数编写递归函数.因此,请按照下列步骤操作

1. Define the base case (use wikipedia article for hints).
2. Define recurrence in terms of base case
3. Write pseudo code to solve the recurrence, and be sure to put base case(s) at beginning of function, and recurrence at end.

一旦掌握了这些步骤,那么继续进行电源重复应该对你更有意义.