尾递归,C语言实现
程序员文章站
2022-03-24 15:29:30
...
普通递归在执行时需要在保存当前数据,并在内存中重新开辟栈。所以普通递归的空间复杂度比较高,效率比较低。所以,我们一般倾向于把递归方式转化成迭代的方式进行计算。但是如果递归语句是整个函数的最后一个语句,则无需保存当前数据,并重新开辟栈。可以直接在当前的栈中继续读取/写入数据。这种递归方式的效率就比较高。递归语句是整个函数的最后一个语句,这种方式称之为尾递归。我们还是用计算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)。但这不是本文的研究重点。