ruby - 递归时堆栈级别太深(SystemStackError)

Question

我想做这个简单的计算，但它提示堆栈不够深，即使对于 n 的非常小的数字(例如 4)也是如此。类似主题的其他 SO 帖子推荐尾递归，但是这在这里不适用，因为您只在达到基本情况时才添加到累积值。

RubyVM::InstructionSequence.compile_option = {
:tailcall_optimization => true,
:trace_instruction => false
}

def recursively_count_paths(x , y, n)
 if x == n &&  y == n
  return 1
  puts " we got a path people"
 elif x == n
  puts "x is done"
  return recursively_count_paths(x, y + 1, n)
 elif y == n
  puts "y is done"
  return recursively_count_paths(x + 1, y, n)
 else
 return (recursively_count_paths(x + 1, y, n) + 
recursively_count_paths(x, y + 1, n))
 end  
end

recursively_count_paths(0, 0, 20)

在其他情况下我不应该返回吗？

Answer 1

尾递归在这种情况下不相关。由于您多次递归调用该方法，因此编译器无法进行优化。大多数这些电话都是不必要的。我能够将您的代码重写为:

def recursively_count_paths(x, y, n)
  return 0 if x > n or y > n
  return 1 if x == n &&  y == n
  return recursively_count_paths(x+1, y, n) + recursively_count_paths(x, y+1, n)
end

第一行查找越界的路径，但不计算在内。第二行相当于您的第一个 if 语句。如果路径已完成，则返回 1。最后一行与最后的 return 语句相同，只是将所有向北的路径与所有向东的路径相加。由于我们两次调用 recursively_count_paths，尾调用优化仍然无济于事。

如果您使用 n=20 运行它，您可能会注意到它需要一段时间。这是因为随着网格大小的增加，该算法花费的时间呈指数增长。那是因为你一遍又一遍地计算相同的子路径。这也是欧拉计划Problem 15 ，所以我不会在这里提供我的解决方案。不过，我会给您一个提示:保存您的工作。