递归算法

Question

当我写递归程序时，即使是一个小程序，我总是感到困惑。

#include <iostream>
using namespace std;

int recursion(int x)
{
    if(x == 0)
        return 0;

    return (x + recursion(x-1));  //recursive function call should always be in the                                        return statement?
}

int main()
{
    cout<<"SUM:"<<recursion(9);
}

有没有其他的方法可以避免递归函数调用出现在return语句中？

- cppcoder

Answer 1

没有语言规定递归调用必须作为return语句的一部分出现。它可以出现在方法的任何位置（甚至可能出现在多个位置）。

例如：

int recursion(int x)
{
    if (x == 0) return 0;
    int rec = recursion(x-1);
    return x + rec;
}

话虽如此，在函数的最后进行递归调用具有其优点：这被称为“尾递归”，一个好的编译器可能能够优化尾递归。

最后，值得一提的是，在您的特定示例中（将数字从 0 加到 n ），递归是完全不必要的。

- NPE

Answer 2

在进行递归时，不要想着递归。思考："啊，在这个点上调用那个recursion()函数很实用"或者"哦，我可以在这里重复使用它"。它们和所有其他调用一样是普通的函数调用。

递归这个术语会让许多初学者感到不必要的困惑。如果你了解函数和函数调用，那么你已经理解了递归，只是你还不知道而已。

- Sebastian Mach

---

我认为对于新手程序员来说，常见的一种情况是没有意识到有两个理由可以调用正在编写的函数："1. 函数没有完成，因此无法使用"和 "2. 如果调用此函数，将会形成无限循环"。要解决第一种情况，请确保了解自上而下的编程方法。要解决第二种情况，请从基本情况开始。 - Viktor Mellgren

是的，仅调用函数并使用其返回值（而不是实现函数）比一次性进入函数并发现它未完成更有意义。（这不仅适用于递归，而且适用于编程的一般情况（也许在面向对象编程中表现得最好，因为您还需要考虑构造函数和对象）。 - Viktor Mellgren

@vixen：我们程序员有时很难向非程序员解释我们的工作。他们不理解我们（“你通过聊天与他交流，但他就坐在你旁边？”），而我们也不理解他们（“它不起作用”，“什么不起作用？”，“哦，那个软件”）:D - Sebastian Mach

Answer 3

当然，您可以以任何希望的方式进行递归。例如，要以天真的方式计算斐波那契数列，您需要进行一种必然会极快地分支的递归：

inf fib(int n)
{
  //... base case
  int a = fib(n - 1);
  int b = fib(n - 2);
  return a + b;
}

你还可以写成return fib(n-2) + fib(n-1);，但关键是在这种情况下你无法消除递归分支。

另一方面，你真正想尝试和实现的是尾部递归，即最终语句只是递归调用。例如，你的求和可以写成：

void sum(int n, int & result)
{
  if (n = 0) return;
  result += n;
  sum(n - 1, result);
}

这个特殊情况的关键特点是递归可以完全原地进行。通常，栈的增长速度为（B - 1）ⁿ，其中n是递归深度，B是并行评估的数量。这是指数级的（可以理解为很糟糕），除非你有B = 1，在这种情况下，可以尝试将函数设计为尾递归形式。

- Kerrek SB

Answer 4

您不需要将递归函数调用放入返回语句中；您可以这样做：

int recursion(int x)
{

    if(x == 0)
        return 0;
    int val = recursion(x-1);
    return (x + rec);  
 }

- mort