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

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

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变换，可以把非尾递归转换为尾递归。其核心思想就是把
可以参考这篇博客

终身学习！