尾递归，C语言实现-蒲公英云

尾递归，C语言实现

普通递归在执行时需要保存当前数据，并在内存中重新开辟栈。所以普通递归的空间复杂度比较高，效率比较低。所以，我们一般倾向于把递归方式转化成迭代的方式进行计算。但是如果递归语句是整个函数的最后一个语句，则无需保存当前数据，并重新开辟栈。可以直接在当前的栈中继续读取/写入数据。这种递归方式的效率就比较高。递归语句是整个函数的最后一个语句，这种方式称之为尾递归。我们还是用计算sum = 1 + 2 + 3 + … + n举例：

int add1(int n) //普通递归 
{
   if (n == 0) //递归出口
        return n;
   else
           return n + add1(n - 1); //递归
}

这是普通递归，最后一个语句不是单一的递归语句，而是与加法一起组成的一个复杂语句。

int add2(int n, int sum) //普通递归 
{
   if (n > 0) 
        return add2(n - 1, sum + n); //递归
   else
           return sum; //递归出口
}

这是普通递归，递归语句不是函数的最后一个语句。

int add3(int n, int sum) //尾递归 
{
    if (n == 0) 
        return sum; //递归出口
    else
           return add3(n - 1, sum + n); //尾递归 
}

这是尾递归，递归语句是单一的，且递归是这个函数的最后一个语句。这种方式的效率是比较高的。如果可以，尽可能把普通递归转化成尾递归。

总结

1、递归：把大问题分解成小问题后进行求解；递归会占用大量内存，且有可能超出最大递归次数。尾递归不需要保存数据、重新开辟栈，所以尾递归的效率是比较高的。尽可能把递归转化成迭代或尾递归的方式。
2、关于f(n) = 1 + 2 + 3 + … + n的计算，用累加公式 f(n) = n * (n + 1) / 2的效率最高，时间复杂度为O(1)。但这不是本文的研究重点。