python递归函数详解,Python递归算法经典实例
1.递归概述
递归是一种编程技能，在某些情况下，它甚至是不可替代的。递归可以大大简化代码，看起来非常简洁，但是递归设计非常抽象，很难掌握。通常，我们自顶向下思考问题，而递归自底向上解决问题——这就是为什么递归看起来不够直观。那么，什么是递归？我们先从生活中找个栗子。
我们都有在黑暗的影院找座位的经历：问前排的朋友，他们坐在哪一排，加一，就是我们当前位置的排号。如果前排的朋友不知道自己在哪一排，可以用同样的方法得到自己的排号，然后告诉你。如果前排的朋友不知道自己是哪一排，他也会这么做。这个推演不会无限期的进行下去，因为问到第一排的时候，坐在第一排的朋友肯定会直接给出答案。这是递归算法在生活中的应用实例。
递归被宽泛地定义为“一个函数在运行时直接或间接调用自己”。严格地说，递归函数必须满足以下两个条件：
至少有一个确定的递归结束条件，我们称之为递归出口，也有人喜欢称这个条件为递归基。
有直接或间接的自调用(也称为递归调用)接近递归出口。
递归虽然晦涩难懂，但还是有规律可循的。只有掌握了基本的递归理论，才能应用于复杂的算法设计。
2.线性递归
先说两个经典的递归算法――阶乘和yydy序列。几乎所有关于递归算法的话题都是从它们开始的。阶乘的概念相对简单。唯一需要说明的是，0的阶乘是1而不是0。为此我特意咨询了库大的饼干，他是数学专业的。Yydy数列，又称黄金分割数列，指的是这样一个数列：1，1，2，3，5，8，13，21，34，…数学上，斐波那契数列定义如下：
F(0)=1，F(1)=1，F(n)=F(n-1) F(n-2)(n=2，nN，N是一组正整数)
阶乘和yydy序列的递归算法如下：
定义阶乘(n):
如果==0: #递归退出
返回1
Return n*factorial(n-1) #自调用向递归退出方向逼近
定义斐波那契(n):
If 2: #递归退出
返回1
返回斐波纳奇(n-1)斐波纳奇(n-2) #自呼接近递归退出方向
这两个函数的结构都很简单，递归的退出和自调用都很清晰，但两者有一个显著的区别：在阶乘函数中，只使用了一个自调用，而yydy函数有两个自调用。
阶乘递归函数每一层的递归只调用自己一次，所以每一层最多只有一个实例，它们形成线性的顺序关系。这种递归方式称为‘线性递归’，是递归的最基本形式。非线性递归(如yydy递归函数)每层会产生两个实例，时间复杂度为
，这很容易导致堆栈溢出。
其实上面两个函数也可以用loop方法简洁地写出来。的确，在很多情况下，递归可以解决问题，循环也可以。但是，在更多的情况下，递归是不能被循环代替的。因此，有必要深入研究递归理论。
3.尾部递归
接下来，我们将转换上述阶乘递归函数，并仍然以递归方式实现它。为了便于比较，我们把两种算法放在一起。
def阶乘_A(n):
如果==0: #递归退出
返回1
Return * factorial _ a (n-1) #自调用逼近递归出口
def factorial_B(n，k=1):
如果==0: #递归退出
返回k
k *=n
n -=1
Return factorial_B(n，k) # Self-call逼近递归退出方向
对比factorial_A()和factorial_B()的写法，会发现一些有趣的问题。factorial_A()的自调用是表达式的一部分，这意味着自调用不是函数的最后一步，而是自调用的结果得到后需要再次做乘法运算；factor _ b()的自调用是函数的最后一步。和factorial_B()函数一样，当它自己的调用是整个函数体中执行的最后一条语句，并且它的返回值不是表达式的一部分时，这个递归调用就是尾递归。递归函数的特点是在回归过程中不需要做任何事情。这个特性非常重要，因为大多数现代编译器都会利用这个特性自动生成优化的代码。
Factorial_A()和factorial_B()分别用于计算5的阶乘。下图所示的计算过程清楚地显示了尾递归的优势：你不必花费大量的堆栈空间来保存最后一次递归中的参数和局部变量。这是因为在最后一次递归操作之后，前面的数据已经被计算并传递给了当前的递归函数，所以最后一次递归中的局部变量和参数将被删除，从而释放空间，因此它不会
阶乘_A(5)
5 *阶乘_A(4)
5 * 4 *阶乘_A(3)
5 * 4 * 3 *阶乘_A(2)
5 * 4 * 3 * 2 *阶乘_A(1)
5 * 4 * 3 * 2 * 1 *阶乘_A(0)
5 * 4 * 3 * 2 * 1
5 * 4 * 3 * 2
5 * 4 * 6
5 * 24
120
阶乘_B(5，k=1)
阶乘_B(4，k=5)
阶乘_B(3，k=20)
阶乘_B(2，k=60)
阶乘_B(1，k=120)
阶乘_B(0，k=120)
120
虽然尾部递归具有成本低、效率高的优点，但这种递归一般可以转化为循环语句。
4.单向递归
对于本文的前两个递归函数，不管是阶乘还是yydy序列，递归总是往递归出口的方向走，没有分支，没有重复。这种递归称为单向递归。在文件递归遍历等应用中，搜索一个文件夹后，通常需要返回父目录，继续搜索其他兄弟文件夹。这一过程不是单向的，而是分支的和回顾性的。通常复杂的递归不是单向的，所以算法的设计比较困难。
导入操作系统
定义遍历(文件夹):
对于os.walk(文件夹)中的根目录、目录和文件：
对于目录中的目录名：
print(os.path.join(root，dir_name))
对于文件中的文件名：
print(os.path.join(root，file_name))
以上是os模块的walk()实现的基于循环的文件遍历方法。虽然是循环结构，但是如果不熟悉walk()，这个函数看起来还是很直观的。我更喜欢下面的递归遍历方法。
导入操作系统
定义遍历(文件夹):
对于os.listdir(文件夹)中的项目：
obj=os.path.join(文件夹，项目)
打印(对象)
if os.path.isdir(obj):
遍历的
5.深度优先，广度优先。
遍历文件通常有两种策略：深度优先搜索(DFS)和广度优先搜索(BFS)。滑稽鸵鸟，深度优先是优先考虑相应级别文件夹中的子文件夹，递归式深度开发；广度优先是指优先考虑相应级别文件夹中的文件，向水平方向递归发展。
导入操作系统
def遍历_DFS(文件夹):
基于深度优先文件遍历
dirs，files=list()，list()
对于os.listdir(文件夹)中的项目：
if os.path.isdir(os.path.join(文件夹，项目)):
目录追加(项目)
否则：
files.append(项目)
对于目录中的目录名：
遍历(os.path.join(文件夹，目录名))
对于文件中的文件名
print(os.path.join(文件夹，文件名))
def遍历_BFS(文件夹):
基于广度优先文件遍历
dirs，files=list()，list()
对于os.listdir(文件夹)中的项目：
if os.path.isdir(os.path.join(文件夹，项目)):
目录追加(项目)
否则：
files.append(项目)
对于文件中的文件名
print(os.path.join(文件夹，文件名))
对于目录中的目录名：
遍历(os.path.join(文件夹，目录名))
这就是本文的全部内容。希望对大家的学习有帮助，也希望大家能支持剧本之家。
如何查看电脑配置历史中提交的图片或压缩文件？
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。