热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

python递归函数简单实例_Python递归的经典案例

目录:一、递归的简介二、递归的经典应用2.1递归求阶乘2.2递归推斐波那契数列2.3二分法找有序列表指定值2.4递归解汉诺塔前言:当我们

目录 :

一、递归的简介

二、递归的经典应用

2.1 递归求阶乘

2.2 递归推斐波那契数列

2.3 二分法找有序列表指定值

2.4 递归解汉诺塔

前言:

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

一、递归的简介

1、递归的百度百科定义

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

递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或

间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题

来求解,递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量。

递归的能力在于用有限的语句来定义对象的无限集合。一般来说,递归需要有边界条件、递归前进

段和递归返回段。当边界条件不满足时,递归前进;当边界条件满足时,递归返回。

2、递归的通俗理解

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

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

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

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

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

1209144-20190330012058671-1022860303.jpg

我想到一个比较接近我们生活的例子,和那个传本子的例子类似,比如你喜欢一个女孩,你想告诉她,但你和她座位隔得很远,你写好了纸条,想同学传过去,于是,你把纸条传给你前面的同学,然后同学又向前传,直到传到你喜欢的那个女孩手里,但是女孩已经有喜欢的人了,于是,她也写了一个纸条让原来的同学再传回来给你,那么同学之间打招呼传纸条的行为就可以看作是函数调用,你是最初调用的函数,那个你喜欢的女孩就是最终的目的地,纸条上的信息就是初始值和最终答案。

4、最简单的递归的实例

#-*- coding:utf-8-*-#将 10不断除以2,直至商为0,输出这个过程中每次得到的商的值。

defrecursion(n):

v= n//2 #地板除,保留整数

print(v) #每次求商,输出商的值

if v==0:'''当商为0时,停止,返回Done'''

return 'Done'v= recursion(v) #递归调用,函数内自己调用自己

recursion(10) #函数调用

输出结果:

5

2

10

5、递归的特点

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

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

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

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

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

二、递归经典案例

1、递归求阶乘

实例如下:

#1!+2!+3!+4!+5!+...+n!

deffactorial(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) #打印结果

2、递归推斐波那契数列

实例如下:

#1,1,2,3,5,8,13,21,34,55,试判断数列第十五个数是哪个?

deffabonacci(n):'''n为斐波那契数列'''

if n <&#61; 2:&#39;&#39;&#39;数列前两个数都是1&#39;&#39;&#39;v&#61; 1

return v #返回结果&#xff0c;并结束函数

v &#61; fabonacci(n-1)&#43;fabonacci(n-2) #由数据的规律可知&#xff0c;第三个数的结果都是前两个数之和&#xff0c;所以进行递归叠加

return v #返回结果&#xff0c;并结束函数

print(fabonacci(15)) #610 调用函数并打印结果

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

实例如下&#xff1a;

data &#61; [1,3,6,13,56,123,345,1024,3223,6688]defdichotomy(min,max,d,n):&#39;&#39;&#39;min表示有序列表头部索引

max表示有序列表尾部索引

d表示有序列表

n表示需要寻找的元素&#39;&#39;&#39;mid&#61; (min&#43;max)//2

if mid&#61;&#61;0:return &#39;None&#39;

elif d[mid]n:print(&#39;向左侧找&#xff01;&#39;)returndichotomy(min,mid,d,n)else:print(&#39;找到了%s&#39;%d[mid])returnres&#61; dichotomy(0,len(data),data,222)print(res)

未完待续。。。



推荐阅读
  • 如何精通编程语言:全面指南与实用技巧
    如何精通编程语言:全面指南与实用技巧 ... [详细]
  • 第六章:枚举类型与switch结构的应用分析
    第六章深入探讨了枚举类型与 `switch` 结构在编程中的应用。枚举类型(`enum`)是一种将一组相关常量组织在一起的数据类型,广泛存在于多种编程语言中。例如,在 Cocoa 框架中,处理文本对齐时常用 `NSTextAlignment` 枚举来表示不同的对齐方式。通过结合 `switch` 结构,可以更清晰、高效地实现基于枚举值的逻辑分支,提高代码的可读性和维护性。 ... [详细]
  • 本文深入解析了Java 8并发编程中的`AtomicInteger`类,详细探讨了其源码实现和应用场景。`AtomicInteger`通过硬件级别的原子操作,确保了整型变量在多线程环境下的安全性和高效性,避免了传统加锁方式带来的性能开销。文章不仅剖析了`AtomicInteger`的内部机制,还结合实际案例展示了其在并发编程中的优势和使用技巧。 ... [详细]
  • 深入解析C语言中的动态规划算法:以背包问题为例
    本文深入探讨了C语言中动态规划算法的应用,以经典的背包问题为例进行详细解析。通过实例分析,展示了如何利用动态规划解决复杂优化问题,并提供了高效的代码实现方法。文章不仅涵盖了算法的基本原理,还讨论了其在实际编程中的应用技巧和优化策略,为读者提供了全面的理解和实践指导。 ... [详细]
  • 在编程笔试和面试中,全排列算法因其适中的难度而备受青睐,不仅能够考察应聘者的算法基础,还能测试其对递归和回溯的理解。本文将深入解析全排列算法的实现原理,探讨其应用场景,并提供优化建议,帮助读者更好地掌握这一重要算法。 ... [详细]
  • 在前文探讨了Spring如何为特定的bean选择合适的通知器后,本文将进一步深入分析Spring AOP框架中代理对象的生成机制。具体而言,我们将详细解析如何通过代理技术将通知器(Advisor)中包含的通知(Advice)应用到目标bean上,以实现切面编程的核心功能。 ... [详细]
  • 小王详解:内部网络中最易理解的NAT原理剖析,挑战你的认知极限
    小王详解:内部网络中最易理解的NAT原理剖析,挑战你的认知极限 ... [详细]
  • Python进阶笔记:深入理解装饰器、生成器与迭代器的应用
    本文深入探讨了Python中的装饰器、生成器和迭代器的应用。装饰器本质上是一个函数,用于在不修改原函数代码和调用方式的前提下为其添加额外功能。实现装饰器需要掌握闭包、高阶函数等基础知识。生成器通过 `yield` 语句提供了一种高效生成和处理大量数据的方法,而迭代器则是一种可以逐个访问集合中元素的对象。文章详细解析了这些概念的原理和实际应用案例,帮助读者更好地理解和使用这些高级特性。 ... [详细]
  • 清华大学出版社 | 杨丹:基于MATLAB机器视觉的黑色素瘤皮肤癌检测技术及源代码分析(第1689期)
    清华大学出版社 | 杨丹:基于MATLAB机器视觉的黑色素瘤皮肤癌检测技术及源代码分析(第1689期) ... [详细]
  • 计算机视觉领域介绍 | 自然语言驱动的跨模态行人重识别前沿技术综述(上篇)
    本文介绍了计算机视觉领域的最新进展,特别是自然语言驱动的跨模态行人重识别技术。上篇内容详细探讨了该领域的基础理论、关键技术及当前的研究热点,为读者提供了全面的概述。 ... [详细]
  • 在使用 SQL Server 时,连接故障是用户最常见的问题之一。通常,连接 SQL Server 的方法有两种:一种是通过 SQL Server 自带的客户端工具,例如 SQL Server Management Studio;另一种是通过第三方应用程序或开发工具进行连接。本文将详细分析导致连接故障的常见原因,并提供相应的解决策略,帮助用户有效排除连接问题。 ... [详细]
  • 手指触控|Android电容屏幕驱动调试指南
    手指触控|Android电容屏幕驱动调试指南 ... [详细]
  • 贪心策略在算法设计中的应用与优化
    贪心算法在算法设计中具有广泛的应用,特别是在解决优化问题时表现出色。本文通过分析经典问题“买卖股票的最佳时机II”,探讨了贪心策略的基本原理及其在实际问题中的应用。通过实例分析,展示了贪心算法如何通过局部最优选择逐步达到全局最优解,并讨论了其在时间和空间复杂度上的优势。此外,还提出了一些优化方法,以提高算法的效率和适用性。 ... [详细]
  • HTML 页面中调用 JavaScript 函数生成随机数值并自动展示
    在HTML页面中,通过调用JavaScript函数生成随机数值,并将其自动展示在页面上。具体实现包括构建HTML页面结构,定义JavaScript函数以生成随机数,以及在页面加载时自动调用该函数并将结果呈现给用户。 ... [详细]
  • Netty框架中运用Protobuf实现高效通信协议
    在Netty框架中,通过引入Protobuf来实现高效的通信协议。为了使用Protobuf,需要先准备好环境,包括下载并安装Protobuf的代码生成器`protoc`以及相应的源码包。具体资源可从官方下载页面获取,确保版本兼容性以充分发挥其性能优势。此外,配置好开发环境后,可以通过定义`.proto`文件来自动生成Java类,从而简化数据序列化和反序列化的操作,提高通信效率。 ... [详细]
author-avatar
手机用户2602883667
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有