面试题：Ruby递归与尾调用优化在复杂数据结构中的应用

Question

给定一个树形数据结构（用Ruby类表示节点和树的关系），编写一个递归函数来遍历该树的所有节点。然后，说明如何通过尾调用优化来提高遍历大型树时的性能，并实际修改代码以应用尾调用优化。

Answer 1

1. 普通递归遍历树形结构

假设树形结构定义如下：

class TreeNode
  attr_accessor :value, :children

  def initialize(value)
    @value = value
    @children = []
  end
end

def traverse_tree(node)
  puts node.value
  node.children.each do |child|
    traverse_tree(child)
  end
end

2. 尾调用优化原理

尾调用优化（Tail Call Optimization, TCO）是一种优化技术，当一个函数的最后一个操作是调用另一个函数时，编译器或解释器可以重用当前栈帧而不是创建一个新的栈帧。这样可以避免栈溢出错误，特别是在处理深度递归或大型数据结构时。在Ruby中，从Ruby 2.5开始，支持有限的尾调用优化，主要在纯Ruby方法之间的尾调用上。

3. 应用尾调用优化修改代码

为了应用尾调用优化，我们需要将递归函数改造成尾递归形式，即递归调用是函数的最后一个操作。

class TreeNode
  attr_accessor :value, :children

  def initialize(value)
    @value = value
    @children = []
  end
end

def traverse_tree_tail_recursion(node, &block)
  stack = [node]
  while stack.any?
    current = stack.pop
    yield current
    stack.concat(current.children.reverse)
  end
end

使用方式：

root = TreeNode.new(1)
child1 = TreeNode.new(2)
child2 = TreeNode.new(3)
root.children << child1
root.children << child2

traverse_tree_tail_recursion(root) do |node|
  puts node.value
end

这种方法使用一个栈来模拟递归调用，避免了真正的递归调用栈增长，从而实现了类似尾调用优化的效果，提高了遍历大型树时的性能。