乐趣区

关于tensorflow:尾调用尾递归-与-非尾递归

jiezi

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

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 的时候调用本身，这种状况称为尾递归，除了调用本身不能有其余额定的。尾递归是递归的一种非凡模式，也是是尾调用的一种非凡模式（尾调用最初调用函数本身，就是一个尾递归）。尾调用不肯定是尾递归。

尾递归特点：

  1. 在回归过程中不必做任何操作，编译器会利用这种特点主动生成优化的代码。（编译器发现在回归调用时通过笼罩以后的栈，而不是创立新的栈，应用来缩小栈空间的应用和缩小栈的调配开释开销）
  2. 尾递归是把变动的参数传递给递归函数的变量了。递归产生时，外层函数把计算结果当成参数传给内存函数。
  3. 尾递归的优化从函数调用的汇编实现很容易了解，只有不波及多余的参数（也就是不必额定的栈容量存，栈顶不必往下扩大再调用回函数），间接就能够扭转 %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 变换，能够把非尾递归转换为尾递归。其核心思想就是把
能够参考这篇博客

一生学习！

退出移动版