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