[Python知识库]Python中递归的几个例子

本文程序用递归分别解决如下问题：

1.基本的调用递归实现顺序和倒序输出1-10的整数。
2.递归打印九九乘法表。
3.舍罕王赏麦问题（64格2倍递增求和）。
4.递归遍历文件。
5.递归实现求Fibonacci数列中的第n项。
6.循环求Fibonacci数列。（效率比递归求解更高）

# coding=utf-8
# 递归调用：声明一个方法，并在方法中设定条件，在条件下调用自身，即在方法中调用自己，若不符合条件，则停止调用。
# 条件：1.把要解决的问题转化成一个新问题，且新问题的求解方法与原问题相同，只是处理对象发生变化。
#      2.不能无限制调用自身，必须有一个出口，以便跳出递归，避免死循环。


# 例 2-1 模拟循环，从1循环到10
# 尾递归：递归位置在方法最后。
def forFun_1(i):  # 传入最小的数1
    if i <= 10:
        print(i)
        forFun_1(i + 1)  # 尾递归


# 例 2-2 倒序循环，从10循环到1（方法一：书上的）
def forFun_3(i):
    if i <= 10:
        forFun_3(i + 1)
        print(i)


# 例 2-2 倒序循环，从i(大于等于1)循环到1：(方法二：自己改的)
def forFun_2(i):  # 传入最大的数
    if i >= 1:
        print(i)
        forFun_2(i - 1)  # 尾递归


# 例 2.3 用递归打印九九乘法表。
def multiplication_1(n):  # n表示从第n行开始到底10行
    if n < 10:
        for m in range(1, n + 1):
            print('%d * %d = %d' % (m, n, m * n), end="\t")  # "\t"是不换行制表符，等同tab键
        # print("\n")
        print()  # 默认输出换行符"\n"
        multiplication_1(n + 1)  # 递归调用，行号递增


# 例 2.3 用递归打印九九乘法表(我自己改的)
def multiplication_2(n):  # n代表行，从n行到第一行
    if n >= 1:
        for m in range(1, n + 1):  # m代表列
            print("%d * %d = %d" % (m, n, m * n), end="\t")
        print()
        multiplication_2(n - 1)


# 印度舍罕王赏麦问题：8*8的格子，第一个格子1粒麦子，此后每一小格的麦子比前一个多1倍。
# 每轮用前一个格子的麦子数乘以2，再加上以前所有格子中麦子的数量，如此递归64次可得到总的需要赏赐的麦子数量。
# 例 2-4 计算64个格子2倍递增求和：
def wheat(n):
    if n > 1:  # 从第二个格子开始
        sum, rs = wheat(n - 1)  # 每次先调用前一个格子的计算方法，算完再执行本格子的算法
        rs = rs * 2  # 算出当前格子印方的麦子数量（前一个格子的麦子数量*2）
        sum = sum + rs  # 之前所有格子的麦子数量 + 当前格子麦子数量
        return sum, rs  # 返回值有两个数：总数、当前数
        # sum += rs
    else:  # 当递归到第一个格子时
        return 1, 1  # 第一个格子有1粒麦子，第i个格子加上前面所有格子的麦子和还是1粒


# 递归遍历文件
# 思路：1.传入最外层文件路径，用Python中的listdir方法遍历路径下的文件和文件夹。
#     2.循环中用Python中的isfile方法识别是否是文件夹。如果遍历到文件夹，继续递归调用，依次深入到最深层，从而打印出整个路径下的全部文件。
# 例 2-5 递归遍历指定路径下的所有文件和文件夹。
import os
def displayFile(path):
    for each in os.listdir(path):  # 遍历路径下的文件和文件夹
        absolute_path = os.path.join(path, each)    # 得到文件的绝对路径
        is_file = os.path.isfile(absolute_path)     # 得到是否为文件还是目录的布尔值（是文件则True，是文件夹则False）
        if is_file:    # 是文件就直接打印
            print(each)
        else:  # 如果是文件夹就递归
            print('++++', each, '++++')  # 文件夹范围开始标识
            displayFile(absolute_path)
            print("++++", each, "++++")  # 文件夹范围结束标识


# 递归实现斐波那契数列
# 斐波那契数列又称黄金分割数列：0,1,1,2,3,5,8,13,21,34,55,89....
# 编程思路：1.声明求解函数f，参数为n（表示数列的第n项）
#       2.下标从0开始，首先判断输入的n是否大于1，若小于等于1，则直接返回
#       3.若n大于1，递归计算f(n-1)和f(n-2)的值，并将两个值相加，得到斐波那契数列在位置n的值。
# 2.6 递归求裴波那契数列的第n项（Fibonacci）
def fib_digui_1(n):  # 返回第n项裴波那契数列值
    if n > 1:
        return fib_digui_2(n - 1) + fib_digui_2(n - 2)
    else:
        return n

# 仅仅是交换了一下分支：（等同于上一个方法）
def fib_digui_2(n):
    if n <= 1:
        return n
    else:
        return fib_digui_2(n - 1) + fib_digui_2(n - 2)


# Fibonacci存在的问题分析：递归实现裴波那契数列的解法有很严重的效率问题。
#       求解方法的树图中有很多节点是重复的（由于是两支递归相加），重复的节点数会随着n的增大而急剧增大。
#       递归计算Fibonacci的时间复杂度是以n的指数方式递增的。因此递归不适合求它。
# 改进思路：慢的原因是重复太多，需要避免重复计算。可以用循环方式从头到尾计算。根据：f(0)+f(1)=f(2),f(1)+f(2)=f(3),....
# 例 2.7 循环方式求解裴波那契数列。（方法一）
def fib_xunhuan_1(n):
    if n > 1:
        a = 0
        b = 1
        fibN = 0    # 裴波那契数列第n项临时数据存储单元
        for i in range(2, n+1):
            fibN = a + b
            a = b    # 算出第n项后，通过数据交换，a、b成为待求i+1项的前两项
            b = fibN
        return fibN
    else:
        return 1


# 例 2.7 循环方式求解裴波那契数列。（方法二）
def fib_xunhuan_2(n):  # 获取前n个斐波那契数列的列表（自己写的）
    a = 0
    b = 1
    result = []
    for x in range(n):
        result.append(a)
        a, b = b, a+b
    return result


# 主函数：
if __name__ == "__main__":
    print()  # 默认输出一个换行
    print("------1-10正序输出------")
    forFun_1(1)  # （1-10正序输出）
    print("------1-10倒序输出--1------")
    forFun_2(10)  # （1-10倒序输出）
    print("------1-10倒序输出--2------")
    forFun_3(1)  # （1-10倒序输出）
    print("------打印九九乘法表------")
    multiplication_1(1)  # 打印九九乘法表
    print("------打印 n * n 乘法表------")
    multiplication_2(9)
    print("------舍罕王赏麦64个格子的总麦子数量：--------")
    sum, rs = wheat(64)  # 两个并列的返回值
    print(sum)
    print("------舍罕王赏麦第64个格子的麦子数量：--------")
    sum, rs = wheat(64)  # 两个并列的返回值
    print(rs)
    print("------递归遍历文件：--------")
    displayFile(r"C:\Users\lv\Desktop\Python\Python-入门-imooc")
    print("------递归--实现裴波那契数列：--------")
    Fibs_1 = []  # 用于保存裴波那契数列每一个位置上的数
    Fibs_2 = []
    for i in range(15):  # 得到前面十五个
        Fibs_1.append(fib_digui_1(i))  # 调用方法，添加返回的值到列表中
        Fibs_2.append(fib_digui_2(i))
    print(Fibs_1)
    print(Fibs_2)
    print("------循环--实现裴波那契数列：--------")
    # 方法二：
    res = fib_xunhuan_2(15)
    print(res)
    Fibs_3 = []
    # 方法一：
    for i in range(15):
        Fibs_3.append(fib_xunhuan_1(i))
    print(Fibs_3)

最终的运行结果如下：

C:\Users\lv\Desktop\Python\其他代码集\python算法\digui\venv\Scripts\python.exe C:/Users/lv/Desktop/Python/其他代码集/python算法/digui/main.py

------1-10正序输出------
1
2
3
4
5
6
7
8
9
10
------1-10倒序输出--1------
10
9
8
7
6
5
4
3
2
1
------1-10倒序输出--2------
10
9
8
7
6
5
4
3
2
1
------打印九九乘法表------
1 * 1 = 1	
1 * 2 = 2	2 * 2 = 4	
1 * 3 = 3	2 * 3 = 6	3 * 3 = 9	
1 * 4 = 4	2 * 4 = 8	3 * 4 = 12	4 * 4 = 16	
1 * 5 = 5	2 * 5 = 10	3 * 5 = 15	4 * 5 = 20	5 * 5 = 25	
1 * 6 = 6	2 * 6 = 12	3 * 6 = 18	4 * 6 = 24	5 * 6 = 30	6 * 6 = 36	
1 * 7 = 7	2 * 7 = 14	3 * 7 = 21	4 * 7 = 28	5 * 7 = 35	6 * 7 = 42	7 * 7 = 49	
1 * 8 = 8	2 * 8 = 16	3 * 8 = 24	4 * 8 = 32	5 * 8 = 40	6 * 8 = 48	7 * 8 = 56	8 * 8 = 64	
1 * 9 = 9	2 * 9 = 18	3 * 9 = 27	4 * 9 = 36	5 * 9 = 45	6 * 9 = 54	7 * 9 = 63	8 * 9 = 72	9 * 9 = 81	
------打印 n * n 乘法表------
1 * 9 = 9	2 * 9 = 18	3 * 9 = 27	4 * 9 = 36	5 * 9 = 45	6 * 9 = 54	7 * 9 = 63	8 * 9 = 72	9 * 9 = 81	
1 * 8 = 8	2 * 8 = 16	3 * 8 = 24	4 * 8 = 32	5 * 8 = 40	6 * 8 = 48	7 * 8 = 56	8 * 8 = 64	
1 * 7 = 7	2 * 7 = 14	3 * 7 = 21	4 * 7 = 28	5 * 7 = 35	6 * 7 = 42	7 * 7 = 49	
1 * 6 = 6	2 * 6 = 12	3 * 6 = 18	4 * 6 = 24	5 * 6 = 30	6 * 6 = 36	
1 * 5 = 5	2 * 5 = 10	3 * 5 = 15	4 * 5 = 20	5 * 5 = 25	
1 * 4 = 4	2 * 4 = 8	3 * 4 = 12	4 * 4 = 16	
1 * 3 = 3	2 * 3 = 6	3 * 3 = 9	
1 * 2 = 2	2 * 2 = 4	
1 * 1 = 1	
------舍罕王赏麦64个格子的总麦子数量：--------
18446744073709551615
------舍罕王赏麦第64个格子的麦子数量：--------
9223372036854775808
------递归遍历文件：--------
++++ python入门.assets ++++
image-20210911122325988.png
image-20210911122825874.png
image-20210911122901549.png
image-20210911123655527.png
image-20210911124928712.png
image-20210911215839730.png
image-20210912205833493.png
++++ python入门.assets ++++
python入门.md
------递归--实现裴波那契数列：--------
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
------循环--实现裴波那契数列：--------
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]
[1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377]

进程已结束，退出代码为 0