递归：

如果问题可以拆分为和原问题相似的子问题时，可以用递归解决。
递归的基本思想：某个函数直接或者间接的调用自身，这就把原问题转换为许多性质相同但规模更小的子问题。
重难点：如何把原问题划分为符合条件的子问题，而不需要去研究这个子问题是如何被解决的。跳出细节，从整体上看问题。

image.png
在函数内部，可以调用其他函数。如果一个函数在内部调用自身本身，这个函数就是递归函数。
在计算机内部，函数调用是通过栈（stack）这种数据结构实现的。递归函数会使用栈这种数据结构，当函数调用时，栈的深度加1，当函数返回时，栈的深度减1。当栈的深度过大时，会发生“栈溢出”这种错误。
RecursionError: maximum recursion depth exceeded in comparison

定义：Recursion is a method of solving problems that involves breaking a problem down into smaller and smaller subproblems until you get to a small enough problem that it can be solved trivially. Usually recursion involves a function calling itself. While it may not seem like much on the surface, recursion allows us to write elegant solutions to problems that may otherwise be very difficult to program.

递归的三大准则：

1，停止递归的基准条件
一个递归函数的基准条件可能有多个，也可能只有一个
2，使问题的规模不断的缩小，直到满足基准条件，结束递归
3，递归就是自己不断的调用自己

image.png

举个例子，我们来计算阶乘n! = 1 x 2 x 3 x ... x n，用函数fact(n)表示，可以看出：

n不等于1时，fact(n)=n!=1×2×3×⋅⋅⋅×(n−1)×n=(n−1)!×n=fact(n−1)×n
n等于1时，fact（1）=1

def fact(n):
    if n==1:
        return 1
    return n * fact(n - 1)

如果我们计算fact(5)，可以根据函数定义看到计算过程如下：

===> fact(5)
===> 5 * fact(4)
===> 5 * (4 * fact(3))
===> 5 * (4 * (3 * fact(2)))
===> 5 * (4 * (3 * (2 * fact(1))))
===> 5 * (4 * (3 * (2 * 1)))
===> 5 * (4 * (3 * 2))
===> 5 * (4 * 6)
===> 5 * 24
===> 120

常见使用递归能够解决的问题

• 汉诺塔问题

def moveTower(height,fromPole, toPole, withPole):
    
    if height >= 1:
        if height==1:
            moveDisk(fromPole,toPole)
            return 1
        else:
            c1=moveTower(height-1,fromPole,withPole,toPole)
            moveDisk(fromPole,toPole)
        
            c2=moveTower(height-1,withPole,toPole,fromPole)
            return c1+c2+1

def moveDisk(fp,tp):
    print("moving disk from",fp,"to",tp)
print(moveTower(3,"A","B","C"))

• 判断是否为回文字符串问题

• 求和问题