19 递归算法之一

递归是最奇妙的思想

大纲

• 什么是递归算法

• 用递归来求和

• 用递归来找最大值

• 用递归来计算阶乘

什么是递归算法

大家都听过这个故事吧：从前有座山，山上有座庙，庙里有个老和尚，老和尚在讲故事给小和尚听：从前有座山，山上有座庙，庙里有个老和尚，老和尚在讲故事给小和尚听：从前座山，山上有座庙，庙里有个老和尚，老和尚在讲故事给小和尚听………

story = '从前有座山，山上有座庙，庙里有个老和尚，老和尚在讲故事给小和尚听:'
count = 0
def recursive(story=story):
    global count
    # 停止条件
    if count == 3:
        return story
    else:
        count += 1
        return story + recursive(story)

recursive()

'从前有座山，山上有座庙，庙里有个老和尚，老和尚在讲故事给小和尚听:从前有座山，山上有座庙，庙里有个老和尚，老和尚在讲故事给小和尚听:从前有座山，山上有座庙，庙里有个老和尚，老和尚在讲故事给小和尚听:从前有座山，山上有座庙，庙里有个老和尚，老和尚在讲故事给小和尚听:'

在上面这个函数里，它自己调用了自己，最后拼接出了一个嵌套的故事。

用递归来求和

直观上理解，递归是函数套函数，自己调用自己。递归是一种优雅的算法思想，刚接触递归的时候可能不大容易理解，我们先用一个具体的例子来看一下。例如计算一个列表求和值。可以直接用循环来完成。

def sum_list(x):
    total = 0
    for value in x:
        total = total + value
    return total
sum_list([14,6,7,4,9,30])

70

让我们换个思路，考虑极端情况，如果一个列表里只有一个值，那么求和就是它本身，如果一个列表中再多一个值，就把两个值相加。

def sum_recursion(x):
    print(x)  
    if len(x) == 1:  # 极端条件或者是停止条件
        return x[0]
    else:
        return x[0] + sum_recursion(x[1:]) #不满足条件则进行分拆，同时调用自身

sum_recursion([14,6,7,4,9,30])

[14, 6, 7, 4, 9, 30]
[6, 7, 4, 9, 30]
[7, 4, 9, 30]
[4, 9, 30]
[9, 30]
[30]





70

让我们来理解了下上面的代码，为了理解方便，我们在函数的开始去打印输入列表x，在一开始的时候这是有六个数字元素的完整列表，然后进入条件判断，如果这个列表只有一个值，就是出现了极端情况，直接输出这个值，如果不满足条件，说明列表中有多个值，我们就把当前状态的x进行分拆。

分拆思路是这样的，把第一个位置的数字拿出来，再去求和函数去求剩下数字的和。此时函数还没有计算完，程序会暂停住，去计算里面那个调用自身的函数。可以注意到这里函数内部又再次调用了自身，这就是递归的不同之处，因为列表有6个数字，所以它反复调用自己到第6次的时候，才发现满足len(x)等于1的条件，输出了30，然后回到第5次调用函数的时候，将30和9相加，再回到第4次调用函数的时候，39和4相加，以此类推，回到最外层函数，得到最终70的答案。

如果你看过电影盗梦空间的话，递归这种自己调用自己的作法就好像进入不同的梦境，只有在最底层梦境满足极端条件的时候，才会真正算出一个值，同时依次返回上次梦境，得到最终的答案。

所以我们总结一下写递归函数的几个要点：

• 需要明确这个函数的目的

• 函数中的终止条件是什么

• 函数中的分拆方法是什么

用递归来找最大值

前面的课程我们学习过，使用循环可以找最大值

x = [31, 2,101, 23, 28, 65, 7]
def find_max(x):
    x_max = x[0]
    for i in x:
        if x_max<i:
            x_max = i
    return x_max
find_max(x)

101

下面我们来模仿之前的例子来用递归实现一下。

def find_max_recursion(x):
    print(x)
    if len(x) <2:  # 极端条件或者是停止条件
        return x[0]
    else:
        m = len(x)//2
        x1 = x[:m]
        x2 = x[m:]
        u = find_max_recursion(x1)
        v = find_max_recursion(x2)
        if u>v:
            return u
        else:
            return v

x = [31, 2,101, 23, 28, 65, 7]
find_max_recursion(x)

[31, 2, 101, 23, 28, 65, 7]
[31, 2, 101]
[31]
[2, 101]
[2]
[101]
[23, 28, 65, 7]
[23, 28]
[23]
[28]
[65, 7]
[65]
[7]





101

用递归来计算阶乘

再看一个递归用来计算阶乘的例子，3!表示计算3的阶乘，也就是等于3,2,1相乘

def fac_Recursionr(x):
    print(x)
    if x == 1:
        return 1
    else:
        return x * fac_Recursionr(x-1)

fac_Recursionr(4)

4
3
2
1





24

同样用来调试理解方便，这里将x打印了出来。先判断是否满足极端条件，如果x等于1，那么它的阶乘就是1，如果不满足极端状态，我们就要把x进行分拆，将它往极端情况去推，同时考虑当前状态和缩减状态的关系是一个乘法的关系。

小结：递归算法会在函数中调用自己，通常先会有一个条件判断，判断输入是否满足极端状态，如果满足则直接得到解，如果不满足极端状态，就要把输入问题进行分拆，分拆成更小的子问题，将它往极端状态去推，同时考虑当前状态和缩减后状态的关系。