尾递归---更高效的递归方式
认识尾递归
尾递归是指在一个函数的最后一个操作是调用自身的递归。这意味着在递归调用后没有其他操作需要执行,直接返回递归调用的结果。尾递归通常是指递归调用出现在函数的最后一行,或者是出现在一个单独的分支中,确保在递归调用之后没有其他代码需要执行。尾递归的特点是在递归调用之后不需要保存当前函数的状态,因为递归调用的结果会直接返回。这种特性使得编译器可以对尾递归进行优化,将其转化为循环形式,从而避免在调用栈中不断添加新的帧,节约了内存空间。
拿计算阶乘举例:
普通的递归
factorial(n):
if n == 0:
return 1
else:
return n * factorial(n-1)
尾递归形式
factorial_tail(n, acc=1):
if n == 0:
return acc
else:
return factorial_tail(n-1, acc*n)//返回结果直接是递归函数本身
// 如果上述为return factorial_tail(n-1, acc)+1或者 return factorial_tail(n-1, acc*n)*n
这类形式都不是尾递归,因为返回结果并不是单一递归函数本身,有额外项,(如+1,*n)它的存在会导致每次函数调用栈不会清除,一直累积,和递归一样。
尾递归的优点
直接上实例看看尾递归的效率(拿计算斐波那契数列举例子)
很容易写出递归;
//count用于计算调用fac函数时,计算机会计算fac(3)的次数
实际结果如下:
可以看到,计算fac(40)时,fac(3)在电脑中居然会计算如此多次!!!!效率很低!
稍微修改下使用尾递归的方法
实际结果如下:
经过同样的测试,fac(3)只计算了1次;由此可见尾递归的效率是多么高!
为什么尾递归效率高呢?
尾递归和普通递归都是通过函数调用自身来实现的,但它们在内存利用方面有所不同。
在普通递归中,每次递归调用都会将当前函数的局部变量、参数和返回地址压入调用栈中,这些信息会在递归返回时被弹出。因此,如果递归层级很深,调用栈可能会变得非常大,占用大量内存空间甚至导致栈溢出。
而在尾递归中,递归调用是当前函数的最后一个操作,也就是说在调用之后没有其他操作需要执行。这使得编译器可以对尾递归进行优化,将其转化为循环形式,在原来的栈区不断覆盖再覆盖,而不是在调用栈中不断添加新的帧。这种优化称为"尾调用优化"。由于尾调用优化消除了不必要的调用栈帧,因此尾递归通常比普通递归节约内存空间。
尾递归在调用栈上不会累积大量的帧,而且可以被优化成循环,从而减少了内存的占用。
#牛客解忧铺#