递归算法

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语句中

Answer 1

没有语言规则规定递归调用必须作为return语句的一部分出现。它可以出现在方法中的任何地方(甚至可能出现在几个地方)。

例如：

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

也就是说，在函数的最后进行递归调用有它的好处:这就是所谓的“尾递归”，一个好的编译器也许能够优化尾递归。

最后，值得一提的是，在您的特定示例(从0到n的数字求和)中，递归是完全不必要的。

Answer 2

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

递归这个术语不必要地把许多新手搞糊涂了。如果你理解函数和函数调用，你就已经理解了递归，只是你还不知道而已。

Answer 3

您不需要将递归函数调用放入return语句中；您只需这样做：

int recursion(int x)
{

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