leetcode分类刷题：如何更好地理解递归

参考知乎上递归下的一个高赞回答，觉得写的非常好，挑选有助于自己理解的内容进行简单总结。

概念含义

1、递归(Recursion)是指在函数的定义中调用函数自身的方法；其包含了两个意思：递 和 归，这正是递归思想的精华所在。
2、有去（递去）有回（归来）——递 ：递归问题必须可以分解为若干个规模较小、与原问题形式相同的子问题，这些子问题可以用相同的解题思路来解决；归：若干个子问题会有一个明确的临界点，从这个临界点开始，原路返回到原点，原问题解决。

递归三要素

1、递归终止条件：递归有一个明确的临界点，一旦到达这个临界点，就不用继续递去而是开始归来；换句话说，该临界点就是一种简单情境，可以防止无限递归。
2、递归终止时的处理办法：在递归临界点的简单情境下，应该直接给出问题的答案。
3、提取重复的逻辑，缩小问题规模，即递归函数内部的操作：抽象出一个干净利落的重复的逻辑

递归算法的编程模型

1、在递去的过程中解决问题：

function recursion(大规模)：
    if end_condition:  # 明确的递归终止条件
        end  # 简单情景
    else:  # 在将问题转换为子问题的每一步，解决该步中剩余部分的问题
        solve  # 递去
        recursion(小规模)  # 递到最深处后，不断地归来
1
2
3
4
5
6

2、在归来的过程中解决问题：

function recursion(大规模)：
    if end_condition:  # 明确的递归终止条件
        end  # 简单情景
    else:  # 在将问题转换为子问题的每一步，解决该步中剩余部分的问题
        recursion(小规模)  # 递去
        solve  # 归来
1
2
3
4
5
6

递归问题分类

1、问题的定义是按递归定义的：斐波纳契数列、阶乘、杨辉三角的取值、回文字符串的判断、字符串全排列、二分查找
2、问题的解法是递归的：汉诺塔问题
3、数据结构是递归的：链表、二叉树等

递归vs循环(迭代)

1、递归通常很直白地描述了一个问题的求解过程，递归的使用能让代码变得简单清晰，逻辑变得易懂，因此也是最容易被想到解决方式；循环其实和递归具有相同的特性，即做重复任务，但有时使用循环的算法并不会那么清晰地描述解决问题步骤，可能会把逻辑隐藏起来——目前来说可能递归的方法还是代码写的太少，所以总是倾向于按照循环迭代的代码写，导致递归的方法特别不熟练
2、在实际开发中，因为函数调用的开销，递归常常会带来性能问题，特别是在求解规模不确定的情况下；而循环因为没有函数调用开销，所以循环效率会比递归高
3、递归求解方式和循环求解方式往往可以互换，也就是说，如果用到递归的地方可以很方便使用循环替换，而不影响程序的阅读，那么替换成循环往往是好的
4、递归实现转换成非递归：建立“堆栈”来保存这些内容以便代替系统栈；把对递归的调用转变为对循环处理

参考文献

1.对于递归有没有什么好的理解方法？