怎样设计递归算法
在实际编程中,有许多定义或者问题本身就具有递归性质.所以我们顺其自然就想到用递归来解决.这样不
仅代码少,而且结构清晰.但是问题是我们应该怎样设计递归呢?这确实一个问题,由于许多问题并不是很明
显的表现出递归的关系,所有很大一部分需要我们进行推导,从而得出递归关系,有了递归关系,编写代码就
相对的比较简单了.首先,我们了解递归算法的特点,所谓的递归,就是把一个大型的复杂的问题层层的转化
为一个与原问题相似的较少规模的问题,在逐步求解小问题后,再返回得到较大问题的解.由于递归只需要少
量的步骤就可描述解题过程中所需要的多次重复计算,所以大大的减少了代码量.递归算法设计的关键在于,
找出递归方程和递归终止条件(边界条件).递归关系就是使问题向边界条件转化的过程.因此,递归关系必须
能使问题越来越简单,规模越小.
因此,递归算法设计,通常有以下 3 个步骤:
(1)分析问题,得出递归关系.
(2)设置边界条件,控制递归.
(3)设计函数,确定参数.
好了，说了,这么多，我相信大家迫不及待要大显身手一番了吧,现在我们就通过一个具体的问题来前
面阐述递归算法的设计过程.
问题¯¯整数划分的问题
对于一个整数 n 的划分,就是把 n 表示成一系列的正整数的和的表达市.注意划分与次序无关.
例如,6 可以可以划分为
6;
5+1;
4+2,4+1+1
3+3,3+2+1,3+1+1+1
评论3