浅谈浅谈Python 递归算法指归递归算法指归
1. 递归概述递归概述
递归( recursion)是一种编程技巧,某些情况下,甚至是无可替代的技巧。递归可以大幅简化代码,看起来非常简洁,但递
归设计却非常抽象,不容易掌握。通常,我们都是自上而下的思考问题, 递归则是自下而上的解决问题——这就是递归看起
来不够直观的原因。那么,究竟什么是递归呢?让我们先从生活中找一个栗子。
我们都有在黑暗的放映厅里找座位的经验:问问前排的朋友坐的是第几排,加上一,就是自己当前所处位置的排号。如果前排
的朋友不知道自己是第几排,他可以用同样的方法得到自己的排号,然后再告诉你。如果前排的前排的朋友也不知道自己是第
几排,他就如法炮制。这样的推导,不会无限制地进行下去,因为问到第一排的时候,坐在第一排的朋友一定会直接给出答案
的。这就是递归算法在生活中的应用实例。
关于递归,不太严谨的定义是“一个函数在运行时直接或间接地调用了自身”。严谨一点的话,一个递归函数必须满足下面两个
条件:
至少有一个明确的递归结束条件,我们称之为递归出口,也有人喜欢把该条件叫做递归基。
有向递归出口方向靠近的直接或间接的自身调用(也被称作递归调用)。
递归虽然晦涩,亦有规律可循。掌握了基本的递归理论,才有可能将其应用于复杂的算法设计中。
2. 线性递归线性递归
我们先从最经典的两个递归算法开始——阶乘(factorial)和斐波那契数列(Fibonacci sequence)。几乎所有讨论递归算法
的话题,都是从从它们开始的。阶乘的概念比较简单,唯一需要说明的是,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,n∈N,N为正整数集)
阶乘和斐波那契数列的递归算法如下:
def factorial(n):
if n == 0: # 递归出口
return 1
return n*factorial(n-1) # 向递归出口方向靠近的自身调用
def fibonacci(n):
if n < 2: # 递归出口
return 1
return fibonacci(n-1) + fibonacci(n-2) # 向递归出口方向靠近的自身调用
这两个函数的结构都非常简单,递归出口和自身调用清晰明了,但二者有一个显著的区别:阶乘函数中,只用一次自身调用,
而斐波那契函数则有两次自身调用。
阶乘递归函数每一层的递归对自身的调用只有一次,因此每一层次上至多只有一个实例,且它们构成一个线性的次序关系。此
类递归模式称作“线性递归”,这是递归最基本形式。非线性递归(比如斐波那契递归函数)在每一层上都会产生两个实例,时
间复杂度为 ,极易导致堆栈溢出。
其实,用循环的方法同样可以简洁地写出上面两个函数。的确,很多情况下,递归能够解决的问题,循环也可以做到。但是,
更多的情况下,循环是无法取代递归的。因此,深入研究递归理论是非常有必要的。
3. 尾递归尾递归
接下来,我们将上面的阶乘递归函数改造一下,仍然用递归的方式实现。为了便于比较,我们把两种算法放在一起。
def factorial_A(n):
if n == 0: # 递归出口
return 1
return n*factorial_A(n-1) # 向递归出口方向靠近的自身调用
def factorial_B(n, k=1):
if n == 0: # 递归出口
return k
k *= n
n -= 1
return factorial_B(n,k) # 向递归出口方向靠近的自身调用