language-agnostic - 规划问题的递归解决方案的最佳方法是什么？

Question

我正在学习递归。我已经使用递归解决了一些其他问题，例如创建二叉树、汉诺塔等。所以，我明白什么是递归，但我发现自己很难规划和实现正确的递归解决方案。

是否有任何关于规划、思考或实现问题递归解决方案的一般提示？

Answer 1

递归就是识别 “自相似性”在解决问题的过程中。递归的一个典型例子，计算一个正整数的阶乘就很好地展示了这个过程。

由于阶乘，n! , 定义为 n * (n-1) * (n-2) ... * 1 ，你应该能够看到
n! = n * (n-1)!
换句话说， n 的阶乘是“(n-1) 的阶乘的 n 倍” .

如果您能理解该语句，以及它如何表现出“自相似”的行为，那么您就已经做好了处理递归的准备。编程递归时的关键是确定何时停止，而不是执行递归调用。在阶乘的情况下，当您尝试确定阶乘的数字为 1 时停止。结果简单地定义为 1，因此您返回该值而不是返回递归函数调用的值。

因此，在考虑如何递归解决问题时，我的建议是尝试识别手头问题中的这种自相似性。如果您可以轻松识别此类相似性，那么该问题可能具有高效且优雅的递归解决方案。如果这种自相似性不明显，则它可能更适合迭代方法。