c++ - 递归函数导致栈溢出

Question

我有以下任务:

Write a program that asks for a number and a power. Write a recursive function that takes the number to the power. For example, if the number is 2 and the power is 4, the function will return 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 sequence .

任何时候我们根据递归定义一个函数，我们都需要首先定义一个基本情况。对于斐波那契数列，我们有 2 个基本情况:

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

也就是说，用英语来说，“0 的 F 是 0，1 的 F 是 1”。或者更简单地说，如果我们将 0 传递给函数 F，我们将返回 0。如果我们传递 1，我们将得到 1。

一旦我们定义了基本情况，我们就需要寻找递归关系。在斐波那契的情况下，我们有以下重现:

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

请注意，在递归函数中，我们总是在函数开头处理基本情况。如果我们没有适当的基本案例，我们就不能定义这种循环，否则，我们的循环将没有终止条件。所以这就是为什么您总是将基本情况放在函数的开头。

现在，鉴于上述解释，另一个很好的练习是为 factorial function 编写一个递归函数.因此，请按照以下步骤操作:

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.

一旦您掌握了这些步骤，那么继续进行幂循环对您来说应该更有意义。