- 1. 递归的基础定义
- 2. 递归解题思路
- 3. 递归的应用
- 3.1递归求阶乘
- 3.2青蛙跳台阶/爬梯子问题（剑指offer10-2/LC70）
- 3.3斐波那契数列（509）
- 3.4汉诺塔问题
- 4. 链表与递归
- 4.1删除链表中的元素（203）
1. 递归的基础定义
递归的本质是一种解决问题的思想：将规模大的问题转化为规模小的问题来解决。
举个例子，假设游戏一共有10关，当每关的BOSS被打败时，会随机掉落金币。金币的数量 = 当前关数 * 一个1到100以内的随机数。
如果使用循环遍历每关，依次加上金币数：
如果用递归的思想：
函数调用本身是通过栈来实现的，所以我们把整个递归过程看成如下：
如果不给递归一个终止条件，将会一直消耗栈的空间，则可能会导致栈的溢出（Stack Overflow）了。所以要有一个明确的结束递归的条件。
再来看下图这个函数的递归调用过程，实际上从上到下是问题拆解的过程，从下到上是问题求解的过程。
总结如下：
用回上面的例子，假设用函数 f(n) 表示我们要求解的问题：第n关累积的金币数。那么 f(n-1)显然是比f(n)规模更小的问题。并且还容易知道，如果已知 f(n-1)，f(n) = f(n-1) + 第n关的金币数也即 f(n) = f(n-1) + currentCoin(n)。
#硬币
import random
rand = random.sample(range(1,100),10)
def goldCoin(current):
return current * rand[current-1]
def totalCoin(n):
total = 0
for i in range(1,n+1):
coin = goldCoin(i)
total = total + coin
return total
print(totalCoin(10))
因此总结了递归的四步解：
用四步法试一下：
#阶乘
def factorial(n):
if n == 1:
return 1
else:
return n * factorial(n-1)
print(factorial(5))
3.2青蛙跳台阶/爬梯子问题（剑指offer10-2/LC70）
不妨假设跳上n级台阶的跳法总数是 f(n)，我们无法直接得知f(n)和n的关系，也即无法直接给出函数f(n)的表达式。因此当我不知道问题的通用解法，但个别解法能得知时，我们希望能从个别解推出通用的解（归纳推理法）。
所以，我们从f(1)开始归纳推理
f(1) = 1 [1]
f(2) = 2 [11,2]
f(3) = 3 [111,12,21]
f(4) = 5 [1111,112,121,211,22]
f(5) = 8 [11111,1112,1121,1211,2111,122,212,221]
f(6) = 13
到此，我们发现是f(n) = f(n-1) + f(n-2)。结束的边界条件是n等于1或2时。
用四步法过一遍思路：
#青蛙跳台阶
def frog(n):
if n == 1 :
return 1
elif n == 2:
return 2
else:
return frog(n-1)+frog(n-2)
print(frog(7))
3.3斐波那契数列（509）
这题跟前面的题目基本一致，我们通过这个递归关系式，即可直到斐波那契数列中任意一个位置的数值。
#斐波那契-递归
class Solution:
def fib(self, N: int) -> int:
# 初始化边界
if N <= 1:
return N
return self.fib(N-1) + self.fib(N-2)
但我们要发现一个问题，就是这个过程中时有很多重复的步骤的。举个n=10的递归树的例子，
我们引出一个概念——最优子结构：下一级最优解可以作为上一级最优解的基础。即我们如果构造出子问题的最优解，就可以得出问题的最优解。举个例子理解，我知道每个班级的最高分，当要计算全校最高分的时候，我不再需要遍历全校每个人的分数，只需要比较每个班的最高分即可。
回到递归树，我们可以发现fib(7)和fib(8)其实都是计算多过一遍的了。
这种即是重叠子问题：重复调用同一个子问题的解，解决的思路是：针对重复的计算，我们可以建造一个备忘录，每次算出子问题的解不着急着返回，而是记在备忘录里后再返回，之后再遇到子问题，则到备忘录里查查，如果之前就解决过这个问题，直接就把答案拿出来用。
所以我们要做的就是在原来的递归树上剪枝，而我们把这种带备忘录的方法称作记忆搜索。
但是，如果每一个子问题都是不同的解，就无法优化也不必优化了（比如下一道汉诺塔问题）。
#斐波那契-记忆搜索
class Solution:
def fib(self, N: int) -> int:
if N <= 1: #初始化边界
return N
self.cache = {0: 0, 1: 1}
return self.memoize(N)
def memoize(self, N: int) -> {}:
if N in self.cache.keys(): #遇到子问题先查备忘录，如果计算过，就不再计算了
return self.cache[N]
self.cache[N] = self.memoize(N-1) + self.memoize(N-2)
return self.memoize(N)
3.4汉诺塔问题
如果A柱子只有一个金片：
如果A柱子有两个金片：3步
如果A柱子有三个金片：7步
回忆一下流程，n=3时，第1-3步我们是把3-1=2个金片从A移到B，第4步是把A最下面的金片移动到C，第5-7步时把3-1=2个金片从B移到C。那么推广之，当n无论多大，我们先把n-1个金片从A移到B，再把A最下面的金片移动到C，最后把n-1个金片从B移到C。其实我们做的就是把规模为n的问题转换为规模为n-1的问题，这就是递归的思想！
但落实代码需要再按四步法思考一下，
1.问题是什么
记住要包含三根柱子！
def Hanoi(n,first,second,third): if n==1: print(first+'-->'+third) Hanoi(1,'A','B','C')
2.规模大的问题和小的问题之间的关系（回顾我们讲的递归思想）
3.‘递’的结束条件
n == 1 时，print( first + ‘–>’ + third)
4.在“递”、“归”的过程中做什么
#汉诺塔
def Hanoi(n,first,second,third):
if n==1:
print(first+'-->'+third)
else:
Hanoi(n-1,first,third,second)
print(first+'-->'+third)
Hanoi(n-1,second,first,third)
Hanoi(3,'A','B','C')
4. 链表与递归
链表本身具有天然的递归性，我们可以把一条链表理解为一个头结点+一个更短的链表。
之前我们是通过迭代循环，比较节点的值和删除值val，相等则删去。现在我们用递归函数去解决。
先把链表看成头结点e后面跟着一个更短的链表，然后执行删除值为val的节点的操作。
#leetcode203
class Solution(object):
def removeElements(self, head, val):
"""
:type head: ListNode
:type val: int
:rtype: ListNode
"""
if not head:
return None
head.next = self.removeElements(head.next,val) #将该元素和后面所有元素分为两组递归
return head.next if head.val == val else head
