Python 递归函数

简介: 它能够把一个大型复杂的问题转化为一个与原问题相似的较小规模的问题来求解,用非常简洁的方法来解决重要问题。就像一个人站在装满镜子的房间中,看到的影像就是递归的结果。以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:1、1、2、3、5、8、13、21、34、……程序设计可以让你的工作由几天节约至几个小时,好的算法可能可以让你的程序运行时间从几个小时节约至几秒钟。被计算了无数次,如果我们能在第一次计算出来后就存储下来,以供后面使用,会不会快些?,基例不需要再次递归,它是确定的表达式;
✅作者简介:人工智能专业本科在读,喜欢计算机与编程,写博客记录自己的学习历程。
🍎个人主页: 小嗷犬的博客
🍊个人信条:为天地立心,为生民立命,为往圣继绝学,为万世开太平。
🥭本文内容:Python 递归函数

1.引入

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

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

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

这个关系给出了另一种方式表达阶乘的方式:
$n! =
\begin{cases} 1 & \text{n=0} \\ n*(n-1)! & \text{n>0} \end{cases}$

阶乘的例子揭示了递归的2个关键特征:
(1)存在一个或多个基例,基例不需要再次递归,它是确定的表达式;
(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、……


2.斐波那契数列

在数学上,斐波纳契数列以如下被以递推的方法定义:
$F(1)=1, F(2)=1, F(n)=F(n-1)+F(n-2)(n>=3, n∈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=' ')
和简单的递归相比较,速度是否快到让你怀疑人生?所以,有的时候 算法很重要。

程序设计可以让你的工作由几天节约至几个小时,好的算法可能可以让你的程序运行时间从几个小时节约至几秒钟。

目录
相关文章
|
13天前
|
存储 JavaScript Java
(Python基础)新时代语言!一起学习Python吧!(四):dict字典和set类型;切片类型、列表生成式;map和reduce迭代器;filter过滤函数、sorted排序函数;lambda函数
dict字典 Python内置了字典:dict的支持,dict全称dictionary,在其他语言中也称为map,使用键-值(key-value)存储,具有极快的查找速度。 我们可以通过声明JS对象一样的方式声明dict
68 1
|
13天前
|
算法 Java Docker
(Python基础)新时代语言!一起学习Python吧!(三):IF条件判断和match匹配;Python中的循环:for...in、while循环;循环操作关键字;Python函数使用方法
IF 条件判断 使用if语句,对条件进行判断 true则执行代码块缩进语句 false则不执行代码块缩进语句,如果有else 或 elif 则进入相应的规则中执行
101 1
|
13天前
|
Java 数据处理 索引
(numpy)Python做数据处理必备框架!(二):ndarray切片的使用与运算;常见的ndarray函数:平方根、正余弦、自然对数、指数、幂等运算;统计函数:方差、均值、极差;比较函数...
ndarray切片 索引从0开始 索引/切片类型 描述/用法 基本索引 通过整数索引直接访问元素。 行/列切片 使用冒号:切片语法选择行或列的子集 连续切片 从起始索引到结束索引按步长切片 使用slice函数 通过slice(start,stop,strp)定义切片规则 布尔索引 通过布尔条件筛选满足条件的元素。支持逻辑运算符 &、|。
76 0
|
24天前
|
设计模式 缓存 监控
Python装饰器:优雅增强函数功能
Python装饰器:优雅增强函数功能
232 101
|
1月前
|
缓存 测试技术 Python
Python装饰器:优雅地增强函数功能
Python装饰器:优雅地增强函数功能
170 99
|
1月前
|
存储 缓存 测试技术
Python装饰器:优雅地增强函数功能
Python装饰器:优雅地增强函数功能
150 98
|
1月前
|
缓存 Python
Python中的装饰器:优雅地增强函数功能
Python中的装饰器:优雅地增强函数功能
|
3月前
|
PHP Python
Python format()函数高级字符串格式化详解
在 Python 中,字符串格式化是一个重要的主题,format() 函数作为一种灵活且强大的字符串格式化方法,被广泛应用。format() 函数不仅能实现基本的插入变量,还支持更多高级的格式化功能,包括数字格式、对齐、填充、日期时间格式、嵌套字段等。 今天我们将深入解析 format() 函数的高级用法,帮助你在实际编程中更高效地处理字符串格式化。
373 0
|
2月前
|
Python
Python 函数定义
Python 函数定义
146 1
|
1月前
|
算法 安全 数据安全/隐私保护
Python随机数函数全解析:5个核心工具的实战指南
Python的random模块不仅包含基础的随机数生成函数,还提供了如randint()、choice()、shuffle()和sample()等实用工具,适用于游戏开发、密码学、统计模拟等多个领域。本文深入解析这些函数的用法、底层原理及最佳实践,帮助开发者高效利用随机数,提升代码质量与安全性。
243 0

推荐镜像

更多