递归时堆栈级别太深（SystemStackError）

我想做这个简单的计算，但它抱怨堆栈不够深，即使对于非常小的数字如n，例如4.其他类似主题的SO帖子推荐尾部递归，但在这里不适用，因为只有在达到基本情况时才添加到累加值。递归时堆栈级别太深（SystemStackError）

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)

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

来源

2017-05-03 Thalatta

'puts'永远不会在第一个if条件下执行 – Ruslan

@Ruslan true。但这与问题是正交的。 – Thalatta

elsif而不是elif？我没有在RubyVM上运行这个，所以我不确定这会产生什么影响 –

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

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，所以我不会在这里提供我的解决方案。然而，我会给你一个提示：保存你的工作。

来源

2017-05-04 03:47:33 Kathryn

是的，我正在解决这个问题。我记得那和帕斯卡尔的三角形有关系，我最终设计了一个O（n^2）解决方案，谢天谢地！ – Thalatta

递归时堆栈级别太深（SystemStackError）

回答

相关问题