python中递归函数详解,python中递归是什么意思

　　1. 递归概述

　　递归是一种编程技能，在某些情况下，它甚至是不可替代的。递归可以大大简化代码，看起来非常简洁，但是递归设计非常抽象，很难掌握。通常我们是自上而下的思考问题，而递归是自下而上的解决问题。这就是为什么递归看起来不够直观。那么，什么是递归？我们先从生活中找个栗子。

　　我们都有在黑暗的影院找座位的经历：问前排的朋友，他们坐在哪一排，加一，就是我们当前位置的排号。如果前排的朋友不知道自己在哪一排，可以用同样的方法得到自己的排号，然后告诉你。如果前排的朋友不知道自己是哪一排，他也会这么做。这个推演不会系统的进行，因为问到第一排的时候，坐在第一排的朋友肯定会直接给出答案。这是递归算法在生活中的应用实例。

　　关于递归，不太严谨的定义是“一个函数在运行时直接或间接调用自己”。严格地说，递归函数必须满足以下两个条件：

　　(1)至少有一个确定的递归结束条件，我们称之为递归出口，也有人喜欢把这个条件称为递归基。

　　(2)有直接或间接的自调用(也叫递归调用)逼近递归出口。

　　递归虽然晦涩难懂，但还是有规律可循的。只有掌握了基本的递归理论，才能应用于复杂的算法设计。

　　2. 线性递归

　　先说两个经典的递归算法，阶乘3354和斐波那契数列。几乎所有关于递归算法的话题都是从它们开始的。阶乘的概念相对简单。唯一需要说明的是，0的阶乘是1而不是0。为此我特意咨询了女儿，她是数学专业的。斐波那契数列，又称黄金分割数列，指的是这样一个数列：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是一组正整数)阶乘和斐波那契数列的递归算法如下：

　　deffactorial(n):

　　IFN==03360 #递归退出

　　返回1

　　Returnn*factorial(n-1)#自调用向递归退出方向逼近

　　deffibonacci(n):

　　Ifn2:#递归退出

　　返回1

　　return Fibonacci(n-1)Fibonacci(n-2)#这两个函数的结构都很简单。递归的退出和自调用是明确的，但两者有显著的区别：在阶乘函数中，只使用一次自调用，而斐波那契函数有两次自调用。

　　阶乘递归函数每一层的递归只调用自己一次，所以每一层最多只有一个实例，它们形成线性的顺序关系。这种递归模式称为“线性递归”，是递归的最基本形式。非线性递归(如Fibonacci递归函数)每层会产生两个实例，时间复杂度为

　　，这很容易导致堆栈溢出。

　　其实上面两个函数也可以用loop方法简洁地写出来。的确，在很多情况下，递归可以解决问题，循环也可以。但是，在更多的情况下，递归是不能被循环代替的。因此，有必要深入研究递归理论。

　　3. 尾递归

　　接下来，我们将转换上述阶乘递归函数，并仍然以递归方式实现它。为了便于比较，我们把两种算法放在一起。

　　deffactorial_A(n):

　　IFN==03360 #递归退出

　　返回1

　　Return * factorial _ a (n-1) #自调用逼近递归出口

　　deffactorial_B(n，k=1):

　　IFN==03360 #递归退出

　　returnk

　　k*=n

　　n-=1

　　Returnfactorial_B(n，k)#比较factorial_A()和factorial_B()的写法，会发现一个很有意思的问题。factor _ a()的自调用是表达式的一部分，这意味着自调用不是函数的最后一步，而是自调用。

　　调用的结果后，需要再做一次乘法运算；factorial_B() 的自身调用则是函数的最后一步。像 factorial_B() 函数这样，当自身调用是整个函数体中最后执行的语句，且它的返回值不属于表达式的一部分时，这个递归调用就是尾递归（Tail Recursion）。尾递归函数的特点是在回归过程中不用做任何操作，这个特性很重要，因为大多数现代的编译器会利用这种特点自动生成优化的代码。

　　分别使用 factorial_A() 和 factorial_B() 计算5的阶乘，下图所示的计算过程，清晰展示了尾递归的优势：不用花费大量的栈空间来保存上次递归中的参数、局部变量等，这是因为上次递归操作结束后，已经将之前的数据计算出来，传递给当前的递归函数，这样上次递归中的局部变量和参数等就会被删除，释放空间，从而不会造成栈溢出。

factorial_A(5)
　　5*factorial_A(4)
　　5*4*factorial_A(3)
　　5*4*3*factorial_A(2)
　　5*4*3*2*factorial_A(1)
　　5*4*3*2*1*factorial_A(0)
　　5*4*3*2*1
　　5*4*3*2
　　5*4*6
　　5*24
　　120
　　factorial_B(5,k=1)
　　factorial_B(4,k=5)
　　factorial_B(3,k=20)
　　factorial_B(2,k=60)
　　factorial_B(1,k=120)
　　factorial_B(0,k=120)
　　120

尾递归虽然有低耗高效的优势，但这一类递归一般都可转化为循环语句。

　　4. 单向递归

　　前文中两个递归函数，不管是阶乘还是斐波那契数列，递归总是向着递归出口方向进行，没有分支，没有反复，这样的递归，我们称之为单向递归。在文件递归遍历等应用场合，搜索完一个文件夹，通常要返回至父级目录，继续搜索其他兄弟文件夹，这个过程就不是单向的，而是有分叉的、带回溯的。通常复杂递归都不是单向的，算法设计起来就比较困难。

importos
　　defergodic(folder):
　　forroot,dirs,filesinos.walk(folder):
　　fordir_nameindirs:
　　print(os.path.join(root,dir_name))
　　forfile_nameinfiles:
　　print(os.path.join(root,file_name))

上面是借助于 os 模块的 walk() 实现的基于循环的文件遍历方法。虽然是循环结构，如果不熟悉 walk() 的话，这个函数看起来还是很不直观。我更喜欢下面的递归遍历方法。

importos
　　defergodic(folder):
　　foriteminos.listdir(folder):
　　obj=os.path.join(folder,item)
　　print(obj)
　　ifos.path.isdir(obj):
　　ergodic(obj)

5. 深度优先与广度优先

　　遍历文件通常有两种策略：深度优先搜索 DFS（depth-first search）和广度优先搜索BFS（breadth-first search）。顾名思义，深度优先就是优先处理本级文件夹中的子文件夹，递归向纵深发展；广度优先就是优先处理本级文件夹中的文件，递归向水平方向发展。

importos
　　defergodic_DFS(folder):
　　"""基于深度优先的文件遍历"""
　　dirs,files=list(),list()
　　foriteminos.listdir(folder):
　　ifos.path.isdir(os.path.join(folder,item)):
　　dirs.append(item)
　　else:
　　files.append(item)
　　fordir_nameindirs:
　　ergodic(os.path.join(folder,dir_name))
　　forfile_nameinfiles
　　print(os.path.join(folder,file_name))
　　defergodic_BFS(folder):
　　"""基于广度优先的文件遍历"""
　　dirs,files=list(),list()
　　foriteminos.listdir(folder):
　　ifos.path.isdir(os.path.join(folder,item)):
　　dirs.append(item)
　　else:
　　files.append(item)
　　forfile_nameinfiles
　　print(os.path.join(folder,file_name))
　　fordir_nameindirs:
　　ergodic(os.path.join(folder,dir_name))

盛行IT软件开发工作室，免费的在线学习python平台，欢迎关注！

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

相关文章阅读