Ruby 浅谈尾递归

lanzhiheng · 2018年06月05日 · 最后由 MiffyLiye 回复于 2018年06月10日 · 1229 次阅读
本帖已被设为精华帖!

初入豆厂的时候就经常听到一些有经验的老员工谈到尾递归,当时我也不怎么当回事。相信许多初入职场的同学也跟我一样对于一些与自己所做工作似乎没有直接关系的东西一般都持排斥的态度。现在回想起来真想扇自己两巴掌,如果当时能够好好的了解一下这些概念的话,或许我能更早地发现编程里面更深层次的乐趣。

Ruby Title

直到最近翻阅《SICP》这本书,书中再次提到尾递归这个概念,我知道自己逃不掉了,这次一定要把它弄清楚。

1. 递归

递归应该是我们耳熟能详的一个概念了,通常在一些涉及高级计算机的理论的书籍或者课程中都会涉及这个话题。但是,在工作中能够直接运用上的机会并不是很多,这也使得它在我们心目中的位置被神化了。递归其实就是一个函数在调用自身的过程。为了更直观地了解这个概念,我们从一道面试题开始

请你实现一个计算阶乘的函数(只能够接受整数输入)

相信很多朋友都能够信手拈来,下面是Ruby版本的实现

def factorial(n)
  return 1 if n <= 1
  n * factorial(n - 1)
end

运行起来也是比较符合预期的

> factorial(2)
 => 2
> factorial(10)
 => 3628800
> factorial(30)
 => 265252859812191058636308480000000

但是当我们用这个阶乘函数来换算一个较大的数的时候,就会导致栈溢出的错误了

> factorial(100000)
SystemStackError: stack level too deep
    from (irb):3:in `factorial'
    from (irb):3:in `factorial'
    from (irb):3:in `factorial'
  .....

Why?我们来简单地分析一下上面的过程。递归确实可以使我们的代码更优雅,但是优雅的背后是要付出代价的。使用递归需要记录函数的调用栈,当调用栈太深的话则将造成栈溢出问题。下面以factorial(6)为例来展示这个阶乘函数的计算过程

factorial(6)
6 * factorial(5)
6 * (5 * factorial(4))
6 * (5 * (4 * factorial(3)))
6 *(5 * (4 * (3 * factorial(2))))
6 *(5 * (4 * (3 * (2 * factorial(1)))))
##############################
6 * (5 * (4 * (3 * (2 * 1))))
6 * (5 * (4 * (3 * 2)))
6 * (5 * (4 * 6))
6 * (5 * 24)
6 * 120
720

当n等于6的时候,我们调用栈的深度就为6。分割线以上的部分是展开的过程,也可以理解成是调用栈堆积的过程,而分割线以下的过程是换算过程, 也可以理解为释放调用栈的过程。可以预测调用栈随着我们传入的参数n的增长而呈线性增长。回到栈溢出的那条程序,当我们n等于100000的时候,调用栈的深度超出了预设的阀值,就会导致了Ruby报栈溢出的错误。为了解决这种递归过程中调用栈过深而引发的内存问题,我们可以借助尾递归。

2. 尾递归

上面的计算过程被称为递归计算过程,计算过程中构造了一个推迟进行的操作所形成的链条(分割线以上),收缩阶段表现为运算实际的执行(分割线以下)。而尾递归则是一种迭代计算过程

1) 迭代计算

迭代的概念我们接触得比较多了,一般的编程语言都会有迭代的关键字,比如for,each,while等等。在介绍尾递归之前我先用迭代的方式来实现一个阶乘的计算过程,下面是Ruby的实现,为了更直观,我先用一个外部变量来缓存每一次乘积的结果

a = 1

(1..6).each do |i|
  a = a * i
end

puts a

计算结果是一样的,6的阶乘等于720。借鉴这种方式如果我们能够在递归的过程中用一个类似a的变量存储计算过程的中间结果,而不是在原有的栈基础上进行叠加,弄成了一个长长的调用栈来延迟执行,那样岂不是能够剩下许多栈的资源?

2) 尾递归版本

我们可以尝试在递归的过程中维护一个变量来存储计算过程的中间结果,每次递归的时候把这个结果传送到下一次计算过程,达到特定条件的时候终止程序。在具体分析这个过程之前我先贴出代码

# 用a来存储计算的中间结果,并将结果作为下一次递归的参数
def fact_iter(i, n, a)
  a = i * a

  return a if i >= n

  i += 1
  fact_iter(i, n, a)
end

def factorial(n)
  fact_iter(1, n, 1)
end

上面的代码并没有最初的递归版本那么优雅了,我另外定义了一个方法fact_iter(i, n, a),来分别接收索引, 最大值, 累乘值这三个参数。下面来看一下如今的调用栈又是如何呢?

factorial(6, 1)
fact_iter(1, 1, 6)
fact_iter(1, 2, 6)
fact_iter(2, 3, 6)
fact_iter(6, 4, 6)
fact_iter(24, 5, 6)
fact_iter(120, 6, 6)
fact_iter(720, 7, 6)

可见上面的过程并没有像递归计算过程那样还有一个长长的调用栈,它的调用过程更加平滑,《SICP》把这个过程的总结为

它总能在常量空间中执行迭代型的计算过程,即使这一计算过程是用一个递归过程描述的,具有这一特征的实现称之为尾递归。

OK,具有尾递归特性的代码已经实现了。现在测试一下,它相比于前面的递归版本是否能帮我们节省一些计算资源,避免掉栈溢出的情况。

> factorial(30)
=> 265252859812191058636308480000000

> factorial(100000)
SystemStackError: stack level too deep
    from (irb):18:in `fact_iter'
    from (irb):23:in `fact_iter'
    from (irb):23:in `fact_iter'
    from (irb):23:in `fact_iter'
    from (irb):23:in `fact_iter'
    from (irb):23:in `fact_iter'
    from (irb):23:in `fact_iter'
    from (irb):23:in `fact_iter'

What? 显然花了那么多时间实现的尾递归版本并没能带来什么实质性的效果,栈依然溢出了。不过这是Ruby的问题,它默认没有开启尾递归优化,毕竟每门语言都有它自己的特性,不然如果每门语言都一样的话岂不是少了许多乐趣?接下来我会简单讲讲如何在Ruby里面启动尾递归优化。

3. Ruby不支持尾递归优化吗?

有些人说Ruby不支持尾递归优化这个说法并不是十分准确,应该描述成Ruby默认没有开启尾递归优化这个选项。大家都知道在Ruby1.9之后就有了虚拟机这个概念了,在这个版本之后Ruby代码都会先编译成字节码,然后把字节码放到虚拟机上面运行。我们可以修改虚拟机的编译选项来启动尾递归优化,相关的配置选项,如下

> require 'pp'
> pp RubyVM::InstructionSequence.compile_option
{:inline_const_cache=>true,
 :peephole_optimization=>true,
 :tailcall_optimization=>false,
 :specialized_instruction=>true,
 :operands_unification=>true,
 :instructions_unification=>false,
 :stack_caching=>false,
 :trace_instruction=>true,
 :frozen_string_literal=>false,
 :debug_frozen_string_literal=>false,
 :debug_level=>0}

可见tailcall_optimization这个尾递归相关的优化选项默认是false的,另外还有一个跟踪指令的选项trace_instruction这个默认是true,我们只需要开启前者,关闭后者就可以启动尾递归优化了。我把配置代码与方法定义的代码分别写到两个Ruby的脚本文件中

## config.rb
RubyVM::InstructionSequence.compile_option = {tailcall_optimization: true, trace_instruction: false}
# factorial.rb
def fact_iter(i, n, a)
  a = i * a

  return a if i >= n

  i += 1
  fact_iter(i, n, a)
end

def factorial(n)
  fact_iter(1, n, 1)
end

在REPL环境中分别加载这两个脚本,注意一定要先加载配置文件,然后再定义方法,如果把两个东西都放在同一个脚本里面,Ruby解析器会同时编译,导致方法定义的时候无法应用到最新的配置。

> require "./config.rb"
=> true
> require "./factorial.rb"
=> true

OK, 这次我们再来计算一次100000的阶乘的话就不会再出现栈溢出的情况了,但是计算出来的数字很大,我只能贴出其中一小部分了

> factorial(100000)

282422940796034787429342157802453551847749492609122485057891808654297795090106301787255177141383116361071361173736196295147499618312391802272607340909383242200555696886678403803773794449612683801478751119669063860449261445381113700901607668664054071705659522612980419........

4. 尾声

这篇文章首先用递归的方式来实现阶乘函数,但是我们发现在计算较大的数的时候就会有栈溢出的现象。这个时候我们可以采用尾递归来优化我们原来的阶乘函数,使之能够在常量计算空间内完成整个递归过程。尾递归并不是某些语言的专属,许多语言都可以写出尾递归的代码(Ruby, Python等等),但这些语言里面并不是所有都能够支持尾递归优化,Ruby默认就没有开启尾递归优化,为此我在最后简单地讲了下在Ruby里面如何修改配置启动尾递归优化,让我们的尾递归代码能够生效。

参考文档

Happy Coding and Writing!!

共收到 13 条回复

递归调用出现在函数末尾,而且该调用的返回值就是当前函数的返回值。

这时候,执行递归调用的堆栈空间不依赖递归调用之前的堆栈数据(上下文),因为在调用回归的时候,没有和之前的上下文有交互。所以在代码编译执行的时候,就可以只关注当前调用的堆栈数据,不用维护每一次递归调用的堆栈数据。不管函数递归多少次,需要维护的堆栈信息的数量就等于单次调用的数量,是一个常数,不会因为调用次数增加而翻倍。

这样就可以在一个有限的堆栈空间中,执行该递归函数,不会栈溢出。 我暂时的理解是这样的。

请教一个问题, 既然尾递归可以 一定程度 上解决递归导致的内存泄漏问题, 为什么这个参数没有默认开启呢? 尾递归的开销是什么呢?

解释器,先把字符串读到语法树中,之后对语法书进行求值(evaluate)。 比如 a = 1; a + 1; eval 到 "a + 1" 的时候,需要知道 a 的值是什么,所以需要存 a = 1 这个信息,这个就是 context。

Ruby 是 Lexical Scope,每一个方法,都是一个新的 scope,所以需要一个新的 context 来做存储(全局变量啥的,先不考虑)。

比如:

def foo(a)
  a
end

eval("foo(1)"),需要记录 a 的值。

如果 foo 里面出现了递归,

def foo(a)
  a + foo(a + 1)
end

首先会把 a 这个变量存到上下文理,然后 eval("foo(a + 1)"),由于上下文一直增长,所以造成了栈溢出。

而尾递归是这种递归

def foo(a)
  foo(a + 1)
end

可以不需要存储上下文,所以不会有栈溢出。

dengqinghua 回复

Guido van Rossum wrote about why he is against supporting TCO in Python. One major problem he points out is that TCO messes up the stack traces, and therefore makes debugging harder. For this reason, he does not support implementing TCO in Python. 这篇文章的最后有写,这个是Python的原因,估计Ruby默认不开启的部分原因也是这个。

early 回复

😆 我暂时理解也是这样。

yfractal 回复

勉强看懂了,mike大神。 😄

Ruby 的尾递归优化选项,可以局部开启,比如可以针对某个方法单独开启的

虽然没遇见过,不过感谢楼主的科普

dengqinghua 回复

尾递归不会导致内存泄漏啊。

另外能用尾递归写出来的逻辑,一般也能用循环实现吧。通常只有函数式编程才会倾向于写成尾递归的形态。

numbcoder 回复

这个倒还没试过。🐭

13楼 已删除
jasl 将本帖设为了精华贴 06月09日 00:24

虽然尾递归版本和普通递归版本算法已经区别很大了(正向循环vs逆向递归),但是没有尾调用优化的时候,尾递归版本的调用栈并不比普通递归短。

如果不改算法的话,尾递归并不会节省一些计算资源。

在堆内存上模拟栈内存的变化,就可以看到两个版本最大栈深度都一样。

def fac_heap(n)
  if n <= 1
    return 1
  end
  stack = []
  context = Struct.new(:n, :fac_n_1).new(n, nil)
  stack << context
  while context.fac_n_1.nil? or stack.size > 1
    if context.n <= 1 and context.fac_n_1.nil?
      context.fac_n_1 = 1
    elsif context.fac_n_1.nil?
      # 模拟函数调用
      stack << Struct.new(:n, :fac_n_1).new(context.n - 1, nil)
    else
      # 模拟函数返回
      res = context.n * context.fac_n_1
      stack.pop
      context = stack.last
      context.fac_n_1 = res
    end
    context = stack.last
    p "stack size: #{stack.size}, n: #{context.n}"
  end
  context.n * context.fac_n_1
end

def fac_tail_heap(n, tco)
  if n <= 1
    return 1
  end
  stack = []
  context = Struct.new(:i, :n, :a, :res).new(1, n, 1, nil)
  stack << context
  while context.res.nil? or stack.size > 1
    if context.i == context.n and context.res.nil?
      context.res = context.a
    elsif context.i < context.n and context.res.nil?
      # 模拟函数调用
      if tco
        stack.pop # 此context后续不再需要,可以丢弃,减少栈深度
      end
      stack << Struct.new(:i, :n, :a, :res).new(context.i + 1, context.n, context.a * (context.i + 1), nil)
    else
      # 模拟函数返回
      res = context.res
      stack.pop
      context = stack.last
      context.res = res
    end
    context = stack.last
    p "stack size: #{stack.size}, i: #{context.i}"
  end
  context.res
end
n = 6
p fac_heap(n)
p fac_tail_heap(n, false)
p fac_tail_heap(n, true)
"stack size: 2, n: 5"
"stack size: 3, n: 4"
"stack size: 4, n: 3"
"stack size: 5, n: 2"
"stack size: 6, n: 1"
"stack size: 6, n: 1"
"stack size: 5, n: 2"
"stack size: 4, n: 3"
"stack size: 3, n: 4"
"stack size: 2, n: 5"
"stack size: 1, n: 6"
720
"stack size: 2, i: 2"
"stack size: 3, i: 3"
"stack size: 4, i: 4"
"stack size: 5, i: 5"
"stack size: 6, i: 6"
"stack size: 6, i: 6"
"stack size: 5, i: 5"
"stack size: 4, i: 4"
"stack size: 3, i: 3"
"stack size: 2, i: 2"
"stack size: 1, i: 1"
720
"stack size: 1, i: 2"
"stack size: 1, i: 3"
"stack size: 1, i: 4"
"stack size: 1, i: 5"
"stack size: 1, i: 6"
"stack size: 1, i: 6"
720

因为堆内存不像栈内存那么容易爆,所以在堆内存上自己维护一个stack数据结构,就能把普通递归在不改算法的情况下转成循环,避免爆栈。

n = 100000
p fac_heap(n)
...
"stack size: 4, n: 99997"
"stack size: 3, n: 99998"
"stack size: 2, n: 99999"
"stack size: 1, n: 100000"
282422...

尾递归和尾调用优化是纯函数式语言为了避免爆栈而发明的workaround(本来想说是trick),混合范式的语言里尾递归和尾调用优化就没那么重要了。

需要 登录 后方可回复, 如果你还没有账号请点击这里 注册