严格来讲,“递归”不是算法,而是算法的一个分类。而且递归类型的算法一般都
是基于一个递归定义的模型的。例如树的中序遍历,它基于一个递归定义:先访问左子树,
再根节点,最后访问右子树。其中“子树”可以是“树”或“叶子”,这就是一个递归
定义。在理解了这个模型之后,直接把模型写成递归的程序就可以了。所以看懂一个递归
算法,关键是看懂模型,程序反而是其次。(当然,如果你编程比数学好,可以通过程序
去理解模型,但最终了解问题的递归模型是最重要的)
迭代同样也是一类算法,它在数学上的定义是把不断地函数的结果作为自变量代入同
一函数,也就是f(f(f(...f(f(x))...))))。但函数的设计应该保证每一次的计算结果都能
逼近最终结果。因此要了解迭代算法,主要是了解这个函数的本身。例如辗转相除求最大公
约数,就是不停的把A,B两个数进行一定的处理,然后把上一步得出的A,B作为下一步开始
的A,B。
而回溯法是一个纯粹的计算机算法,说白了就是高级版的穷举。它的思路是:如果能前
进,就前进。如果不能前进,就后退。如果找到结果,就成功,如果退回到起点,就失败。
按我的个人经验,理解回溯法就应该从简单的例程(走迷宫,八皇后,回溯法求全排列)去
分析。关键是了解:1)前进条件,2)前进时的处理,3)回溯条件,4)回溯时的处理
回溯的关键是从例程上去分析,理解前进和后退的