|
|
|
|
|
|
|
能采用递归描述的算法通常有这样的特征：为求解规模为N的问题，设法将它分解成一些规模较小的问题，然后从这些小问题的解方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的分解和综合方法，分解成规模更小的问题，并从这些更小问题的解构造出规模稍大问题的解。特别地，当规模N=1时，能直接得到解。
|
|
|
|
递归算法的执行过程分为递推和回归两个阶段。在递推阶段，把较复杂的问题的求解推到比原问题简单一些的问题的求解；在回归阶段，当获得最简单情况的解后，逐级返回，依次获得稍复杂问题的解。
|
|
|
|
|
|
（1）Fibonacci数列：Fibonacci数列的递归算法实现如下（注意与递推实现比较）。
|
|
|
|
|
|
（2）背包问题：所谓背包问题，是指有不同价值、不同重量的物品n件，求从这n件物品中选取一部分物品的选择方案，使选中物品的总重量不超过指定的限制重量，但选中物品的价值之和最大。
|
|
|
|
典型做法是逐个考查每一件物品，对于第i件物品的选择考虑有两种可能。
|
|
|
|
.考虑物品i被选择，这种可能仅当包含它不会超过方案总重量限制时才是可行的。选中后继续递归考虑其余物品的选择。
|
|
|
|
.考虑物品i不被选择，这种可能仅当不包含物品i也有可能找到价值更大的方案时才是可行的。
|
|
|
|
|
|
|
