尾调用、尾递归 与 非尾递归

it2023-01-06  71

尾调用、尾递归、非尾递归的几个概念及非尾递归是否可以转换为尾递归。

1、 尾调用:

tail call指的是一个函数的最后一条语句也是一个返回调用函数的语句,即return的是一个函数,这个函数可以是另一个函数,也可以是自身函数。

def fun_b(x): x = x -1 return x def function_a(x): x = x + 1 return fun_b(x) # 最返回的是函数

2、尾递归:

函数在return的时候调用自身,这种情况称为尾递归,除了调用自身不能有其他额外的。尾递归是递归的一种特殊形式,也是是尾调用的一种特殊形式(尾调用最后调用函数自身,就是一个尾递归)。尾调用不一定是尾递归。

尾递归特点:

在回归过程中不用做任何操作,编译器会利用这种特点自动生成优化的代码。(编译器发现在回归调用时通过覆盖当前的栈,而不是创建新的栈,使用来减少栈空间的使用和减少栈的分配释放开销)尾递归是把变化的参数传递给递归函数的变量了。递归发生时,外层函数把计算结果当成参数传给内存函数。尾递归的优化从函数调用的汇编实现很容易理解,只要不涉及多余的参数(也就是不用额外的栈容量存,栈顶不用往下扩展再调用回函数),直接就可以改变%edi,%esi的值,重新调用函数,也就是说不用任何额外的赞变量。 def fun_b(x): if x == 1: return x else: return fun_b(x) # 最后返回调用的是自身函数,是尾递归,如果写成`return fun_b(x)+1`则不是尾递归

3、非尾递归:

把尾递归之外的其他递归调用归结为非尾递归

4、栈调用的区别

普通递归函数自身调用次数很多,递归层级很深,栈空间为0(n),尾递归优化后栈空间可为O(1)。下面有例子可以观察其栈占用的不同:

# 这个是一个非尾递归 def normal_sum(x): if x == 1: return x else: return x + normal_sum(x - 1)

调用fun_sum(5)非尾递归的栈变化:

normal_sum(5) 5 + normal_sum(4) 5 + (4 + normal_sum(3)) 5 + (4 + (3 + normal_sum(2))) 5 + (4 + (3 + (2 + normal_sum(1)))) 5 + (4 + (3 + (2 + 1))) 5 + (4 + (3 + 3)) 5 + (4 + 6) 5 + 10 15

把上面的函数修改为尾递归的方式(尾递归是把变化的参数传递给递归函数的变量了):

def tail_sum(x, total=0): if x == 0: return total else: return tail_sum(x - 1, total + x)

调用尾递归tailrecsum(5, 0)的栈变化:

tail_sum(5, 0) tail_sum(4, 5) tail_sum(3, 9) tail_sum(2, 12) tail_sum(1, 14) tail_sum(0, 15) 15

4、非尾递归是否已可以转回为尾递归

通过CPS变换,可以把非尾递归转换为尾递归。其核心思想就是把 可以参考这篇博客

终身学习!

最新回复(0)