浅谈Python递归算法指归_ackerman函数递归算法python资源-CSDN下载

159 浏览量 2020-12-31 15:08:06 上传评论收藏 93KB PDF 举报

资源详情

资源评论

资源推荐

浅谈浅谈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) # 向递归出口方向靠近的自身调用

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余2页未读，立即下载

评论0

内容反馈

weixin_38724106

粉丝: 3

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip