该系列博客内容主要是《剑指Offer》中的经典题目，结合在刷题过程中见到的一些精彩的解题过程，从而在这里记录下来。代码以Python3实现。
文章图片
解法1
文章图片
文章图片
文章图片
对于这里递归的用法，起初并不是很清楚，看了答主给出的一段Java的代码，才恍然大悟。
文章图片
这里需要注意的是，因为recur(head.next)在前面，所以这行代码会一直运行下去，直到链表的最后端null，这里的recur(head.next)也是递归调用。之后再执行回溯即返回的时候，前面的函数才算执行完毕。这儿可能会有一个疑问，在返回的时候不就相当于退出这个recur函数了吗，为啥还会继续执行下面的tmp.add(head.val)？这正是递归函数的特点，当返回的时候， 返回的是最下层的 recur() ，而上层的 recur() 并没有退出，因此上层的 recur() 就会执行下面的 tmp.add(head.val)。
关于递归，我的理解是，递归的本质是通过函数体来进行的循环，只不过是通过循环体来调用自己来进行所谓的循环，因为最开始的计算机语言本质是汇编，没有什么循环一说。当要执行某个重复指令的时候，你就只能不断地反复跳到之前的那段指令。
递归：Recursion
1、从前有座山
2、山里有座庙
3、庙里有个和尚讲故事
4、返回1
这个就是所谓的递归。
在这里需要注意的是，当进到每一层递归的时候，相当于进入到了一个新的世界或者是互不干扰的世界，在里面做一些事情，然后再到下一层再做某些事情。如果要返回的话，只能是一层一层的返回。
文章图片
这里大概有四步：1）递归终结条件，不写终结条件会进入死循环 ；2）处理当前层逻辑；3）进入到下一层；4）递归结束，清理当前层。
【剑指offer刷题记录4--从头到尾打印链表】用一个比较通俗的说法来解释递归和回溯：
我们在路上走着，前面是一个多岔路口，因为我们并不知道应该走哪条路，所以我们需要尝试。尝试的过程就是一个函数。
我们选择了一个方向，后来发现又有一个多岔路口，这时候又需要进行一次选择。所以我们需要在上一次尝试结果的基础上，再做一次尝试，即在函数内部再调用一次函数，这就是递归的过程。
这样重复了若干次之后，发现这次选择的这条路走不通，这时候我们知道我们上一个路口选错了，所以我们要回到上一个路口重新选择其他路，这就是回溯的思想。
文章图片
文章图片
完整实现
文章图片
参考链接
