• 浅谈尾递归 at 2018年06月10日

    虽然尾递归版本和普通递归版本算法已经区别很大了(正向循环 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),混合范式的语言里尾递归和尾调用优化就没那么重要了。