【黑马程序员】Python基础教程、Python入门教程之递归算法.doc

《【黑马程序员】Python基础教程、Python入门教程之递归算法.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、优选【黑马程序员】Python基础教程、Python入门教程之递归算法文章目录1.递归概述2.线性递归3.尾递归4.单向递归5.深度优先与广度优先1.递归概述递归（recursion）是一种编程技巧，某些情况下，甚至是无可替代的技巧。递归可以大幅简化代码，看起来非常简洁，但递归设计却非常抽象，不容易掌握。通常，我们都是自上而下的思考问题，递归则是自下而上的解决问题——这就是递归看起来不够直观的原因。那么，究竟什么是递归呢？让我们先从生活中找一个栗子。我们都有在黑暗的放映厅里找座位的经验：问问前排的朋友坐的是第几排，加上一，就是自己当前所处位置的排号。

2、如果前排的朋友不知道自己是第几排，他可以用同样的方法得到自己的排号，然后再告诉你。如果前排的前排的朋友也不知道自己是第几排，他就如法炮制。这样的推导，不会无限制地进行下去，因为问到第一排的时候，坐在第一排的朋友一定会直接给出答案的。这就是递归算法在生活中的应用实例。关于递归，不太严谨的定义是“一个函数在运行时直接或间接地调用了自身”。严谨一点的话，一个递归函数必须满足下面两个条件：至少有一个明确的递归结束条件，我们称之为递归出口，也有人喜欢把该条件叫做递归基。有向递归出口方向靠近的直接或间接的自身调用（也被称作递归调用）。递归虽然晦涩，亦有规律可循。

3、掌握了基本的递归理论，才有可能将其应用于复杂的算法设计中。2.线性递归我们先从最经典的两个递归算法开始——阶乘（factorial）和斐波那契数列（Fibonaccisequence）。几乎所有讨论递归算法的话题，都是从从它们开始的。阶乘的概念比较简单，唯一需要说明的是，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

4、，n∈4/4优选N，N为正整数集）1阶乘和斐波那契数列的递归算法如下：deffactorial(n):    ifn==0:#递归出口        return1    returnn*factorial(n-1)#向递归出口方向靠近的自身调用deffibonacci(n):    ifn<2:#递归出口        return1    returnfibonacci(n-1)+fibonacci(n-2)#向递归出口方向靠近的自身调用这两个函数的结构都非常简单，递归出口和自身调用清晰明了，但二者有一个显著的区别：阶乘函数中，只用一次自身调用，

5、而斐波那契函数则有两次自身调用。阶乘递归函数每一层的递归对自身的调用只有一次，因此每一层次上至多只有一个实例，且它们构成一个线性的次序关系。此类递归模式称作“线性递归”，这是递归最基本形式。非线性递归（比如斐波那契递归函数）在每一层上都会产生两个实例，时间复杂度为O(n2)O(n^2)O(n 2)，极易导致堆栈溢出。其实，用循环的方法同样可以简洁地写出上面两个函数。的确，很多情况下，递归能够解决的问题，循环也可以做到。但是，更多的情况下，循环是无法取代递归的。因此，深入研究递归理论是非常有必要的。3.尾递归接下来，我们将上面的阶乘递归函数改造一下，仍

6、然用递归的方式实现。为了便于比较，我们把两种算法放在一起。deffactorial_A(n):    ifn==0:#递归出口        return1    returnn*factorial_A(n-1)#向递归出口方向靠近的自身调用deffactorial_B(n,k=1):    ifn==0:#递归出口        returnk    k*=n    n-=1    returnfactorial_B(n,k)#向递归出口方向靠近的自身调用比较factorial_A()和factorial_B()的写法，就会发现很有意思的问题。fa

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

8、的阶乘，下图所示的计算过程，清晰展示了尾递归的优势：不用花费大量的栈空间来保存上次递归中的参数、局部变量等，