Python递归算法经典实例,Python函数递归(带实例演示)

　　目录：

　　递归简介

　　二、递归的经典应用

　　2.1递归阶乘

　　2.2递归推送斐波那契数列

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

　　2.4汉诺塔的递归解

　　前言：

　　当我们遇到要求阶乘或斐波那契数列等问题时，使用普通循环往往比较麻烦，但如果使用递归，就会简单很多，事半功倍。本文主要和大家分享一些与递归相关的经典案例，结合一些资料谈谈个人的理解，从而加深对递归的理解，掌握一些基本递归的用法。

　　递归简介

　　1.递归百度百科定义

　　调用程序本身的编程技巧叫做递归。

　　作为一种算法，递归在编程语言中被广泛使用。过程或函数在其定义或描述中有一个直接的或

　　一种间接调用自身的方法，通常将一个大的复杂问题转化为一个与原问题相似的较小问题。

　　求解问题，递归策略只需要少量的程序来描述求解过程中所需的重复计算，大大减少了程序的代码量。

　　递归的能力是用有限的语句定义无限的对象集。一般来说，递归需要边界条件和递归。

　　且分段递归地返回分段。当边界条件不满足时，递归推进；当满足边界条件时，它递归返回。

　　2.递归的通俗理解。

　　递归就是在函数内部调用自己的函数，这叫递归。

　　3.关于递归的几种常见隐喻。

　　1.我们用的字典就是递归本身。为了解释一个词，我们需要使用更多的词。老实的孙查了一个字，发现这个字的解释里有些字还是没看懂，于是就开始查第二个字。可惜第二个单词还有你不懂的单词，你就查第三个单词，以此类推，直到有你能完全理解的单词解释。然后递归就结束了，然后你开始退一步，理解之前检查的每个单词。最后，你理解了第一个词的意思。

　　2.一个孩子坐在第10排，作业被组长扔到第1排。孩子想拿回作业怎么办？他可以拍拍第9排的孩子说：‘帮我把笔记本拿到第1排’，而第9排的孩子可以拍拍第8排的孩子说：‘帮我把笔记本拿到第1排’.就这样，消息终于传到了第1排的孩子那里，于是他把笔记本递给了第2排，第2排又递给了第3排.终于，笔记本到手了！这就是递归，拍拍孩子的背可以类比成函数调用，孩子记得发消息和笔记本是因为有记忆，可以类比成栈。

　　3.洋葱是有一层洋葱皮的洋葱。

　　我想到一个更贴近我们生活的例子，类似于传笔记本的例子。比如你喜欢一个女生，你想告诉她，但是你离她的座位很远。你写了一张纸条，想让你的同学传下去。于是，你把它传给你前面的同学，然后同学再传下去，直到传到你最喜欢的焦虑衫。但是女孩已经有喜欢的人了，所以也写了纸条。那么同学之间打招呼、传纸条的行为就可以看作是一个函数调用。你是第一个被调用的函数，你喜欢的女生是最终的归宿，纸条上的信息是初始值，也是最终的答案。

　　4.递归最简单的例子

　　#-*-编码：utf-8-*-#将10除以2，直到商为0，输出此过程中每次得到的商的值。

　　定义递归(n):

　　V=n//2 #楼划分，保留整数

　　Print(v) #每次求商，输出商的值

　　如果==0:“当商为0时，停止并返回Done”

　　Return Donev=recursion(v) #递归调用，函数调用自身。

　　递归(10) #函数调用

　　输出结果：

　　五

　　2

　　10

　　5.递归的特征

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

　　1.必须有明确的结束条件。2.每进入一个更深层次的递归，问题的规模(计算量)都要比上一次递归减少。3.递归效率不高，递归层次太多会导致堆栈溢出。(在计算机中，函数调用是通过栈等数据结构实现的。每进入一次函数调用，堆栈就会增加一层堆栈帧，每返回一次函数，堆栈就会减去一层堆栈帧。因为堆栈的大小不是无限的，过多的递归调用会导致堆栈溢出)

　　关于递归有两个术语，可以概括递归的过程。

　　递归：正如上面的递归实现所分解的，每次递归都是基于下一次的最后一次执行，这被称为递归。

　　回溯：当满足终止条件时，从最后一级返回该值，称为回溯。

　　第二，递归的经典案例

　　1.递归查找阶乘

　　例子如下：

　　#1!2!3!4!5!n！

　　Defial (n): n表示所需数字的阶乘 。

　　If==1:当阶乘if n==1:return n #为1时，结果为1，所以返回结果并退出。

　　n=n *阶乘(n-1) #n！=n*(n-1)！

　　返回结果并退出

　　Res=factorial(5) #调用函数，将返回的结果赋给Res。

　　打印(结果)#打印结果

　　2.递归推斐波那契数列。

　　例子如下：

　　#1，1，2，3，5，8，13，21，34，55，试着确定哪个是序列中的第十五个数字？

　　费波纳契(n): n是费波纳契数列

　　If=2:序列中的前两个数字都是1v=1

　　Return v #返回结果并结束函数

　　v=fabonacci(n-1)fabonacci(n-2)#根据数据规律，第三个数的结果是前两个数之和，所以进行递归叠加。

　　Return v #返回结果并结束函数

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

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

　　例子如下：

　　Data=[1，3，6，13，56，123，345，1024，3223，6688] def二分法(min，max，d，n): min表示有序列表头的索引。

　　Max表示有序列表末尾的索引。

　　d表示有序列表。

　　n表示要查找的元素 mid=(最小值最大值)//2

　　如果mid==0:返回“无”

　　印刷(向左看！)返回二分法(min，mid，d，n)else:print( found % s % d[mid])return RES=二分法(0，len (data)，data，222) print (res)

　　未完待续。

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。