广泛的递归教程

Question

一些需要递归的问题总是让我陷入困境.我并不总是能够提出递归算法,但我知道这个问题有一个递归的解决方案.

我发现像factorial和fibonacci这样的问题很容易使用递归方法实现.但是当我遇到更复杂的问题,例如生成一个数字http://en.wikipedia.org/wiki/Partition_%28number_theory%29的分区时,我知道有一种可能的递归方法,但是我被困在那里.我无法设计递归算法.假设我想要打印字符串的所有组合,或者如果我想使用递归来强制使用Coin Change问​​题,我无法设计递归方法.

是否有任何特定的方式来思考以便提出递归方法？是否有任何广泛的递归算法教程可以帮助我解决更高级的问题？

Answer 1

阅读《计算机程序的结构和解释》一书，该书在 Stack Overflow 上强烈推荐，并且可以在线免费获取。它使用Scheme编程语言来教授有关编程的基本概念。由于Scheme是一种函数式编程语言，因此递归在任何地方都被广泛使用——不仅在C或PHP等命令式编程语言中使用它，而且在通常使用循环构造的地方。如果你愿意的话，书中的例子和问题展示了自然环境中的递归，而不是通过复杂的虚构场景。