Python 递归函数

小嗷犬2022-10-062023-08-25

引入

递归是一种广泛应用算法。它能够把一个大型复杂的问题转化为一个与原问题相似的较小规模的问题来求解，用非常简洁的方法来解决重要问题。就像一个人站在装满镜子的房间中，看到的影像就是递归的结果。递归在数学和计算机应用上非常强大，能够非常简洁的解决重要问题。程序设计中，通过函数定义中调用函数自身的方式来实现递归。

数学上有个经典的递归例子叫阶乘，阶乘通常定义为：

$n! = n *(n-1)* (n-2)... *2* 1$

这个关系给出了另一种方式表达阶乘的方式：

$n! = \begin{cases} 1 & \text{n=0} \\ n*(n-1)! & \text{n>0} \end{cases}$

阶乘的例子揭示了递归的2个关键特征：

存在一个或多个基例，基例不需要再次递归，它是确定的表达式；
所有递归链要以一个或多个基例结尾。

根据用户输入的整数 n，计算并输出 n 的阶乘值：

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)

num = int(input("请输入一个整数: "))
print(f'{num}的阶乘为:{factorial(num)}')

基例有时不止一个，可能有多个。

斐波那契数列

斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）。以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……

在数学上，斐波纳契数列以如下被以递推的方法定义：

$F(1)=1, F(2)=1, F(n)=F(n-1)+F(n-2),(n \geq 3, n \in N)$

这个数列从第3项开始，每一项都等于前两项之和。

编写程序，用户输入正整数 n，输出斐波那契数列的前 n 项：

def fibo(i):
    if i in (0,1):
        return 1
    else:
        return fibo(i-1) + fibo(i-2)
    
num = int(input('请输入一个大于 3 的正整数 :'))
print('\n斐波那契数列的前 {} 项为：'.format(num))
for i in range(1, num+1):
    print(fibo(i), end=' ')

试试打印出前50项。

如此之慢的原因是什么？

每次在计算第i项值时，都需要递归调用直到fibo(0)，也就是说像fibo(0),fibo(1),fibo(2),fibo(3)被计算了无数次，如果我们能在第一次计算出来后就存储下来，以供后面使用，会不会快些？

让我们使用字典改进一下：

calculate_dic = {1: 1, 2: 1}

def fibByDic(n):
    if n not in calculate_dic:
        new_value = fibByDic(n-1) + fibByDic(n-2)
        calculate_dic[n] = new_value
    return calculate_dic[n]
num = int(input('请输入一个大于3的正整数:'))
print('\n斐波那契数列的前{}项为：'.format(num))
for i in range(1, num + 1):
    print(fibByDic(i), end=' ')