Python递归的几个经典案例

当我们碰到诸如需要求阶乘或斐波那契数列的问题时，使用普通的循环往往比较麻烦，但如果我们使用递归时，会简单许多，起到事半功倍的效果。这篇文章主要和大家分享一些和递归有关的经典案例，结合一些资料谈一下个人的理解，也借此加深自己对递归的理解和掌握一些递归基础的用法。

一、递归的简介

1、递归的百度百科定义

程序调用自身的编程技巧称为递归（ recursion）。

递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或
间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。

递归的能力在于用有限的语句来定义对象的无限集合。一般来说，递归需要有边界条件、递归前进
段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。

2、递归的通俗理解

递归就是在函数内部调用自己的函数被称之为递归。

3、几个关于递归通俗的比喻

1.我们使用的词典，本身就是递归，为了解释一个词，需要使用更多的词。当你查一个词，发现这个词的解释中某个词仍然不懂，于是你开始查这第二个词，可惜，第二个词里仍然有不懂的词，于是查第三个词，这样查下去，直到有一个词的解释是你完全能看懂的，那么递归走到了尽头，然后你开始后退，逐个明白之前查过的每一个词，最终，你明白了最开始那个词的意思。

2.一个小朋友坐在第10排，他的作业本被小组长扔到了第1排，小朋友要拿回他的作业本，可以怎么办？他可以拍拍第9排小朋友，说：“帮我拿第1排的本子”，而第9排的小朋友可以拍拍第8排小朋友，说：“帮我拿第1排的本子”…如此下去，消息终于传到了第1排小朋友那里，于是他把本子递给第2排，第2排又递给第3排…终于，本子到手啦！这就是递归，拍拍小朋友的背可以类比函数调用，而小朋友们都记得要传消息、送本子，是因为他们有记忆力，这可以类比栈。

3.一个洋葱是一个带着一层洋葱皮的洋葱。

4、最简单的递归的实例

# 将 10不断除以2，直至商为0，输出这个过程中每次得到的商的值。
def recursion(n):
    v = n//2 # 地板除，保留整数
    print(v) # 每次求商，输出商的值
    if v==0:
        ''' 当商为0时，停止，返回Done'''
        return 'Done'
    v = recursion(v) # 递归调用，函数内自己调用自己
recursion(10) # 函数调用
1
2
3
4
5
6
7
8
9

输出结果：

5
2
1
0
1
2
3
4

5、递归的特点

通过以上的介绍，我们大致可以总结出递归的以下几个特点：

1、必须有一个明确的结束条件
2、每次进入更深一层递归时，问题规模(计算量)相比上次递归都应有所减少
3、递归效率不高，递归层次过多会导致栈溢出（在计算机中，函数调用是通过栈（stack）这种数据结构实现的，每当进入一个函数调用，栈就会加一层栈帧，每当函数返回，栈就会减一层栈帧。由于栈的大小不是无限的，所以，递归调用的次数过多，会导致栈溢出）

关于递归还有两个名词，可以概括递归实现的过程

递推：像上边递归实现所拆解，递归每一次都是基于上一次进行下一次的执行，这叫递推

回溯：则是在遇到终止条件，则从最后往回返一级一级的把值返回来，这叫回溯

二、递归经典案例

1、递归求阶乘

实例如下：

'''
学习中遇到问题没人解答？小编创建了一个Python学习交流群：711312441
寻找有志同道合的小伙伴，互帮互助,群里还有不错的视频学习教程和PDF电子书！
'''
# 1！+2！+3！+4！+5！+...+n!
def factorial(n):
    ''' n表示要求的数的阶乘 '''
    if n==1:
        return n # 阶乘为1的时候，结果为1,返回结果并退出
    n = n*factorial(n-1) # n! = n*(n-1)!
    return n  # 返回结果并退出
res = factorial(5) #调用函数，并将返回的结果赋给res
print(res) # 打印结果
1
2
3
4
5
6
7
8
9
10
11
12
13

2、递归推斐波那契数列

实例如下：

# 1，1，2，3，5，8，13，21，34，55，试判断数列第十五个数是哪个？
def fabonacci(n):
    ''' n为斐波那契数列 '''
    if n <= 2:
        ''' 数列前两个数都是1 '''
        v = 1
        return v # 返回结果，并结束函数
    v = fabonacci(n-1)+fabonacci(n-2) # 由数据的规律可知，第三个数的结果都是前两个数之和，所以进行递归叠加
    return v  # 返回结果，并结束函数
print(fabonacci(15)) # 610    调用函数并打印结果
1
2
3
4
5
6
7
8
9
10

3、二分法找有序列表指定值

实例如下：

data = [1,3,6,13,56,123,345,1024,3223,6688]
def dichotomy(min,max,d,n):
    '''
    min表示有序列表头部索引
    max表示有序列表尾部索引
    d表示有序列表
    n表示需要寻找的元素
    '''
    mid = (min+max)//2
    if mid==0:
        return 'None'
    elif d[mid]<n:
        print('向右侧找！')
        return dichotomy(mid,max,d,n)
    elif d[mid]>n:
        print('向左侧找！')
        return dichotomy(min,mid,d,n)
    else:
        print('找到了%s'%d[mid])
        return 
res = dichotomy(0,len(data),data,222)
print(res)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22