递归+回溯这个理解起来还是挺有难度的哈哈。
我们先看下递归吧。我感觉递归的主要难点在于,它非常"不直接"。对于非递归代码,通常我们看完了整个代码,大概就知道它在干什么了。因为每行代码都很直白而且是非常明确的,比如有个for循环它是要遍历某个数组,或者有个if来判断某个条件是否成立,并根据真假执行后面的不同语句。而递归代码,有一个让人感到麻烦的地方在于,当代码执行到一定步骤之后,它又会去调用自己(只是参数取值有所不同),那代码看到这里之后,就比较容易困惑了。"我本来就是想着把代码完整读一遍来知道它在干嘛的,结果我还没搞清楚它在干嘛,又遇到它自己了"。这个有点"无穷无尽"的意思了哈哈。
我觉得想要理解递归的话可以分两个阶段。第一阶段是,找一个递归代码,就从第一次调用它开始,把代码走一遍,把每次调用的所有细节都写下来(比如参数取值),直到遇到递归的终止条件停止。这个阶段主要是帮助自己熟悉递归代码的运行方法,运行过程,和运行细节,练习多了之后也能消除一些对递归的"恐惧"。
第二阶段要尝试从相对抽象,概括的角度去理解递归了,这样才能比较熟练得写出自己的递归代码。我一般是这么想的,当我们尝试用递归函数fun(n)来解决问题的时候,我们先解决当前输入参数下能解决的一部分问题(这部分代码应该是直白明确的),至于剩下的问题就通过再次调用递归函数解决。我们要坚信递归函数可以帮我们完成剩余的问题,并且我们无需关注它到底是怎么实现的。比如说用递归函数计算n的阶乘n!吧。
fun(n)的作用是返回n!的结果,而且我们知道n!=n * (n-1)!,那当输入为n的时候,我可以把"n*"这一项直白明确的写下来,然后剩下的计算(n-1)!就交给fun(n-1)来解决,我们坚信它可以完成自己的任务,并且我们也不关注它到底怎么完成任务的。那么,就可以写出我们自己的代码了(显示的时候缩进好像有点问题)
int fun(n){
if(n == 1) return 1; // 终止条件
return n * fun(n - 1); // 坚信fun(n-1)可以正确计算(n-1)!
}
完全理解了递归以后,现在再说说递归+回溯吧。这个多了一个难点是"回溯"部分,而且通常递归函数里会多一个for循环。这个,我也是建议可以找一个代码像"第一阶段"那样,把所有细节全部自己走一遍。我这里就直接说"第二阶段"了哈。
一个相对抽象/概括的理解是,对于递归+回溯的函数fun(n),对于输入参数为n的时候,我们有多种"选择"。可以对比一下计算n的阶乘,那里其实只有一种选择,就是乘上n(但是通常,我们不会这么去刻意得想)。当有多种选择的时候,一般我们就要通过一个for循环来枚举每个可能的选择,而当选择确定后,我们可以解决这个选择下的一部分问题,并把剩下的问题再次交给递归了(我们坚信递归可以帮我们解决剩余的问题),最后,在这里递归返回之后,相当于我们已经知道了在当前选择下的最终结果,然后我们需要"恢复状态",这也是回溯思想的关键!"恢复状态"是因为当前的选择可能会改变一些"状态",比如全排列中数组的取值,你这个代码的话就是path数组会发生变化,八皇后问题里棋盘中皇后的位置。我们只有恢复状态之后,才可以进入下一次循环,来尝试另一个选择的情况。整体来说,递归+回溯的常见结构是
void fun(){
终止条件
for循环尝试多种选择 {
做出第i个选择,可能会改变一些状态
递归解决剩余问题
恢复做出第i个选择前的状态,为尝试第i+1个选择做准备
}
}
这个递归+回溯,想要理解的话主要还是要自己多练习哈,可以看看全排列问题和八皇后问题,正好我写过这两个问题,给自己宣传一波哈哈..