1

我有以下任务：

编写一个程序，要求输入一个数字和一个幂。编写一个递归函数，将数字发挥到极致。例如，如果数字为 2，幂为 4，则函数将返回 16。

我写了一个程序，编译时没有错误，但是当我启动程序并输入一个值时，会出现“堆栈溢出”错误。我想我的递归函数变得无限，但我不知道如何以其他方式编写它。

这是我的代码：

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

3 回答 3

9

您的递归没有终止条件，因此它永远运行。

听起来你可能没有很好地掌握递归，所以我想从更简单的东西开始，斐波那契数列。

每当我们根据递归定义一个函数时，我们首先需要定义一个基本情况。在斐波那契的情况下，我们有 2 个基本情况：

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

也就是说，用英语来说，“F of 0 is 0, F of 1 is 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);
}

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

现在，根据上面的解释，另一个很好的练习是为阶乘函数编写一个递归函数。因此，请按照以下步骤操作：

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.

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

于 2012-05-28T22:34:37.333 回答
3

你的功能

  • 不应该做什么
  • 没有终止条件

试着想一想：当你的函数x^y只接受一个数字作为参数时，它怎么能返回。然后，考虑如何将数字提高到幂，并且实施应该是显而易见的。

于 2012-05-28T22:36:05.023 回答
2

递归例程总是需要一个“平凡”或“基本”的案例。想想你写了什么，为 x 传入 1，什么会停止递归？

powpow(1)
  result = 1*1
  call powpow(1)
    result = 1*1
    call powpow(1)
      result = 1*1
      call powpow(1)

adinfinitum （或直到你执行堆栈）

于 2012-05-28T22:39:05.160 回答