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