欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

尾递归,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)。但这不是本文的研究重点。

相关标签: 算法