python数据结构与算法-10_递归

递归

Recursion is a process for solving problems by subdividing a larger
problem into smaller cases of the problem itself and then solving
the smaller, more trivial parts.

递归是计算机科学里出现非常多的一个概念,有时候用递归解决问题看起来非常简单优雅。
之前讲过的数据结构中我们并没有使用递归,因为递归涉及到调用栈,可能会让初学者搞晕。这一章我们开始介绍递归,
后边讲到树和一些排序算法的时候我们还会碰到它。我非常推荐你先看看《算法图解》第三章 递归,
举的例子比较浅显易懂。

什么是递归?

递归用一种通俗的话来说就是自己调用自己,但是需要分解它的参数,让它解决一个更小一点的问题,当问题小到一定规模的时候,需要一个递归出口返回。
这里举一个和其他很多老套的教科书一样喜欢举的例子,阶乘函数,我觉得用来它演示再直观不过。它的定义是这样的:

在这里插入图片描述

我们很容易根据它的定义写出这样一个递归函数,因为它本身就是递归定义的。

def fact(n):
    if n == 0:
        return 1
    else:
        return n * fact(n-1)

看吧,几乎完全是按照定义来写的。我们来看下递归函数的几个特点:

  • 递归必须包含一个基本的出口(base case),否则就会无限递归,最终导致栈溢出。比如这里就是 n == 0 返回 1
  • 递归必须包含一个可以分解的问题(recursive case)。 要想求得 fact(n),就需要用 n * fact(n-1)
  • 递归必须必须要向着递归出口靠近(toward the base case)。 这里每次递归调用都会 n-1,向着递归出口 n == 0 靠近

调用栈

看了上一个例子你可能觉得递归好简单,先别着急,我们再举个简单的例子,上边我们并没有讲递归如何工作的。
假如让你输出从 1 到 10 这十个数字,如果你是个正常人的话,我想你的第一反应都是这么写:

def print_num(n):
    for i in range(1, n + 1):    # 注意很多编程语言使用的都是 从 0 开始的左闭右开区间, python 也不例外
        print(i)


if __name__ == '__main__':
    print_num(10)

我们尝试写一个递归版本,不就是自己调用自己嘛:

def print_num_recursive(n):
    if n > 0:
        print_num_recursive(n-1)
        print(n)

你猜下它的输出?然后我们调换下 print 顺序,你再猜下它的输出

def print_num_recursive_revserve(n):
    if n > 0:
        print(n)
        print_num_recursive_revserve(n-1)

你能明白是为什么吗?我建议你运行下这几个小例子,它们很简单但是却能说明问题。
计算机内部使用调用栈来实现递归,这里的栈一方面指的是内存中的栈区,一方面栈又是之前讲到的后进先出这种数据结构。
每当进入递归函数的时候,系统都会为当前函数开辟内存保存当前变量值等信息,每个调用栈之间的数据互不影响,新调用的函数
入栈的时候会放在栈顶。视频里我们会画图来演示这个过程。

递归只用大脑不用纸笔模拟的话很容易晕,因为明明是同一个变量名字,但是在不同的调用栈里它是不同的值,所以我建议
你最好手动画画这个过程。

在这里插入图片描述

用栈模拟递归

刚才说到了调用栈,我们就用栈来模拟一把。之前栈这一章我们讲了如何自己实现栈,不过这里为了不拷贝太多代码,我们直接用 collections.deque 就可以
快速实现一个简单的栈。

from collections import deque


class Stack(object):
    def __init__(self):
        self._deque = deque()

    def push(self, value):
        return self._deque.append(value)

    def pop(self):
        return self._deque.pop()

    def is_empty(self):
        return len(self._deque) == 0


def print_num_use_stack(n):
    s = Stack()
    while n > 0:    # 不断将参数入栈
        s.push(n)
        n -= 1

    while not s.is_empty():    # 参数弹出
        print(s.pop())

这里结果也是输出 1 到 10,只不过我们是手动模拟了入栈和出栈的过程,帮助你理解计算机是如何实现递归的,是不是挺简单!现在你能明白为什么上边 print_num_recursive print_num_recursive_revserve 两个函数输出的区别了吗?

尾递归

上边的代码示例(麻雀虽小五脏俱全)中实际上包含了两种形式的递归,一种是普通的递归,还有一种叫做尾递归:

def print_num_recursive(n):
    if n > 0:
        print_num_recursive(n-1)
        print(n)


def print_num_recursive_revserve(n):
    if n > 0:
        print(n)
        print_num_recursive_revserve(n-1)    # 尾递归

概念上它很简单,就是递归调用放在了函数的最后。有什么用呢?
普通的递归, 每一级递归都产生了新的局部变量, 必须创建新的调用栈, 随着递归深度的增加, 创建的栈越来越多, 造成爆栈。虽然尾递归调用也会创建新的栈,
但是我们可以优化使得尾递归的每一级调用共用一个栈!, 如此便可解决爆栈和递归深度限制的问题!
不幸的是 python 默认不支持尾递归优化(见延伸阅读),不过一般尾递归我们可以用一个迭代来优化它。

汉诺塔问题

有三根杆子A,B,C。A杆上有N个(N>1)穿孔圆盘,盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆:
但是有两个条件:

  • 每次只能移动一个圆盘;
  • 大盘不能叠在小盘上面。

最早发明这个问题的人是法国数学家爱德华·卢卡斯。
传说越南河内某间寺院有三根银棒,上串64个金盘。寺院里的僧侣依照一个古老的预言,以上述规则移动这些盘子;预言说当这些盘子移动完毕,世界就会灭亡。
这个传说叫做梵天寺之塔问题(Tower of Brahma puzzle)。但不知道是卢卡斯自创的这个传说,还是他受他人启发。

在这里插入图片描述

理解这个问题需要我们一些思维上的转换,因为我们正常的思维可能都是从上边最小的盘子开始移动,但是这里我们从移动最底下的盘子开始思考。
假设我们已经知道了如何移动上边的四个盘子到 B(pole2),现在把最大的盘子从 A -> C 就很简单了。当把最大的盘子移动到
C 之后,只需要把 B 上的 4 个盘子从 B -> C 就行。(这里的 pole1, 2, 3 分别就是 A, B, C 杆)

在这里插入图片描述

问题是仍要想办法如何移动上边的 4 个盘子,我们可以同样的方式来移动上边的 4 个盘子,这就是一种递归的解法。
给定 n 个盘子和三个杆分别是 源杆(Source), 目标杆(Destination),和中介杆(Intermediate),我们可以定义如下递归操作:

  • 把上边的 n-1 个盘子从 S 移动到 I,借助 D 杆
  • 把最底下的盘子从 S 移动到 D
  • 把 n-1 个盘子从 I 移动到 D,借助 S

我们把它转换成代码:

def hanoi_move(n, source, dest, intermediate):
    if n >= 1:  # 递归出口,只剩一个盘子
        hanoi_move(n-1, source, intermediate, dest)
        print("Move %s -> %s" % (source, dest))
        hanoi_move(n-1, intermediate, dest, source)
hanoi_move(3, 'A', 'C', 'B')

# 输出,建议你手动模拟下。三个盘子 A(Source), B(intermediate), C(Destination)
"""
Move A -> C
Move A -> B
Move C -> B
Move A -> C
Move B -> A
Move B -> C
Move A -> C
"""

是不是很神奇,但是老实说这个过程仅凭大脑空想是比较难以想象出来的。人的大脑『栈』深度很有限,因为你甚至都没法同时记住超过 8 个以上的
无意义数字,所以用大脑模拟不如用纸笔来模拟下。(不排除有些聪明的同学能迅速在脑瓜里完成这个过程)

源码

# -*- coding: utf-8 -*-


def fact(n):
    if n == 0:
        return 1
    else:
        return n * fact(n - 1)


def print_num(n):
    for i in range(1, n + 1):    # 注意很多编程语言使用的都是 从 0 开始的左闭右开区间, python 也不例外
        print(i)


def print_num_recursive(n):
    if n > 0:
        print_num_recursive(n - 1)
        print(n)


def print_num_recursive_revserve(n):
    if n > 0:
        print(n)
        print_num_recursive_revserve(n - 1)


from collections import deque


class Stack(object):
    def __init__(self):
        self._deque = deque()

    def push(self, value):
        return self._deque.append(value)

    def pop(self):
        return self._deque.pop()

    def is_empty(self):
        return len(self._deque) == 0


def print_num_use_stack(n):
    s = Stack()
    while n > 0:    # 不断将参数入栈
        s.push(n)
        n -= 1

    while not s.is_empty():    # 参数弹出
        print(s.pop())


def hanoi_move(n, source, dest, intermediate):
    if n >= 1:  # 递归出口,只剩一个盘子
        hanoi_move(n - 1, source, intermediate, dest)
        print("Move %s -> %s" % (source, dest))
        hanoi_move(n - 1, intermediate, dest, source)


def flatten(rec_list):
    for i in rec_list:
        if isinstance(i, list):
            for i in flatten(i):
                yield i
        else:
            yield i


def test_flatten():
    assert list(flatten([[[1], 2, 3], [1, 2, 3]])) == [1, 2, 3, 1, 2, 3]

延伸阅读

递归是个非常重要的概念,我们后边的数据结构和算法中还会多次碰到它,我建议你多阅读一些资料加深理解:

  • 《算法图解》第三章 递归
  • 《Data Structures and Algorithms in Python》 第 10 章 Recursion
  • 《Python开启尾递归优化!》
  • 尾调用优化
  • 汉诺塔

思考题

  • 你能举出其他一些使用到递归的例子吗?
  • 实现一个 flatten 函数,把嵌套的列表扁平化,你需要用递归函数来实现。比如 [[1,2], [1,2,3] -> [1,2,1,2,3]
  • 使用递归和循环各有什么优缺点,你能想到吗?怎么把一个尾递归用迭代替换?
  • 递归有时候虽然很优雅直观,但是时间复杂度却不理想,比如斐波那契数列,它的表达式是 F(n) = F(n-1) + F(n-2),你能计算它的时间复杂度吗?请你画个树来表示它的计算过程,为什么这个时间复杂度很不理想?我们怎样去优化它。
  • python 内置的 dict 只能用 dict[‘key’] 的形式访问比较麻烦,我们想用 dict.key 的形式访问。tornado web 框架中提供了一个 ObjectDict,请你实现一个递归函数接收一个字典,并返回一个可以嵌套访问的 ObjectDict

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/175549.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

呼叫中心自建好还是云外呼好用?

传统的呼叫中心在科技的发展下已经被不适用了,都开始使用起智能化的呼叫中心,一个是自建式呼叫中心,一个是云外呼系统。那自建式呼叫中心与云外呼系统的区别有哪些呢? 1、企业自建呼叫中心 劣势 系统维护更新难:自建…

Proxifier联动BurpSuite抓取小程序

直接上软件包 Proxifier安装包https://pan.quark.cn/s/7fb9ad6deb7cProxifier配置文件https://pan.quark.cn/s/049c5f21c97e 无话可说直接操作 1、安装Proxifier步骤可以省略..... 2、将下面文件导入到Proxifier中 3、左上角文件-导入配置文件(因为我已经导入过…

快来瞧瞧这样制作出来的电子画册,还便于分享宣传呢!

说起电子画册制作,很多人都不知道从何入手。与传统纸质画册相比,电子画册最大的优点是便于传阅,通过微信、QQ等社交平台都能进行转发和分享。而且内容的排版基本上和纸质画册一致,不同的是,无论图片还是文字都可以赋予…

网络渗透测试(wireshark 抓取QQ图片)

1.打开wireshark 这里我用的wifi连接 所以点开wifi就好 打开wifi之后就开始在本机上进行抓包了 我们先给我们的QQ发送一张图片,用自己的手机发送给电脑 然后点击左上角的正方形,停止捕获抓包 QQ的关键词是oicq,所以我们直接找 打开oicq …

2023年国自然植物科学相关面上项目信息公布(小麦、大麦、棉花、大豆、玉米)

2024年申报国自然项目基金撰写及技巧http://mp.weixin.qq.com/s?__bizMzA4NTAwMTY1NA&mid2247575761&idx1&sn32dbacd3393f3b76a1e0668e4b8b3c89&chksm9fdd7c08a8aaf51ec31d4790067bb57751a09947eeb7e728b8c008d26b89adba37e0cab32a62&scene21#wechat_redi…

【23真题】难!下沙“小清华”难度爆增!

今天分享的是23年“下沙小清华”杭州电子科技大学843的信号与系统试题及解析。 本套试卷难度分析:22年杭电843考研真题,我也发布过,若有需要,戳这里自取!平均分为112分,最高分为145分!该院校23…

requests 库中响应最大文件大小和最大连接超时时间的设定

最近,requests-toolbelt库的开发者jvanasco提出了一项特性请求,即在发送请求时设置响应的最大文件大小和最大连接超时时间。 对于最大连接超时时间的问题,我们可以借鉴requests-toolbelt库的开发者kevinburke的建议,将请求放入线程…

基于变色龙算法优化概率神经网络PNN的分类预测 - 附代码

基于变色龙算法优化概率神经网络PNN的分类预测 - 附代码 文章目录 基于变色龙算法优化概率神经网络PNN的分类预测 - 附代码1.PNN网络概述2.变压器故障诊街系统相关背景2.1 模型建立 3.基于变色龙优化的PNN网络5.测试结果6.参考文献7.Matlab代码 摘要:针对PNN神经网络…

我的创作纪念日2048天

机缘 在这特殊的日子里,我要庆祝我的 CSDN 创作纪念日——已经坚持了整整2048天! 在这2048天里,我经历了很多成长和收获。作为一名技术写手,我投入了大量的时间和精力来分享我的知识和经验。我曾经写过关于数据库、数据同步、数…

系列四、ThreadLocal的工作原理

一、内存结构图 二、工作原理 (1)Thread有一个类型为ThreadLocal.ThreadLocalMap threadLocals 的实例变量,即每个线程都有一个属于自己的ThreadLocalMap; (2)ThreadLocalMap内部维护着Entry数组&#xff0…

leetcode:环形链表

题目描述 题目链接:141. 环形链表 - 力扣(LeetCode) 题目分析 我们先了解一个知识:循环链表 尾结点不指向NULL,指向头就是循环链表 那么带环链表就意味着尾结点的next可以指向链表的任意一个结点,甚至可…

指令不明,成员困惑,项目经理如何明确每个人的职责

有一个故事,讲述了一个餐厅客人在点餐时要求吃螃蟹,但是餐厅已经卖完了。幸运的是,楼下的商铺有售卖螃蟹。 经理吩咐小李去询问价格,小李迅速返回并汇报了价格。然而,经理进一步询问了螃蟹的数量,小李才意…

Git远程库操作(GitHub)

GitHub 网址:https://github.com/ 创建远程仓库 远程仓库操作 命令名称作用git remote -v查看当前所有远程地址别名git remote add 别名 远程地址起别名git push 别名 分支推送本地分支上的内容到远程仓库git clone 远程地址将远程仓库的内容克隆到本地git pull 别…

关于CRM系统中的客户,您需要知道这些

今天为大家讲解CRM中客户是什么?如何进行客户管理?CRM系统中有购买意向和已经购买了产品的消费者都属于客户。对于B2B企业,会将企业看作客户,而对于B2C企业来说每一位消费的个体都是客户。 CRM中的客户管理无疑是业务重点&#x…

计算机毕业设计项目选题推荐(免费领源码)java+springboot+mysql社区团购APP 02043

目录 摘要 1 绪论 1.1 研究背景 1.2国内外研究现状 1.3本课题主要工作 1.4论文结构与章节安排 2 社区团购系统分析 2.1 可行性分析 2.2 系统流程分析 2.2.1 数据流程 3.3.2 业务流程 2.3 系统功能分析 2.3.1 功能性分析 2.3.2 非功能性分析 2.4 系统用例分析 2.…

云数据仓库实践:AWS Redshift在大数据储存分析上的落地经验分享

🏆作者简介,黑夜开发者,CSDN领军人物,全栈领域优质创作者✌,CSDN博客专家,阿里云社区专家博主,2023年6月CSDN上海赛道top4。 🏆数年电商行业从业经验,历任核心研发工程师…

超级会员卡积分收银系统源码 会员卡+积分商城+收银功能+多门店系统 附带完整的搭建教程

线上线下的融合已经成为趋势。在这个过程中,会员卡积分收银系统成为了许多企业不可或缺的一部分。该系统以超级会员卡为基础,结合积分商城、收银功能以及多门店系统,为企业提供了一站式的解决方案,帮助企业实现线上线下会员一体化…

Python 第一行代码 —— 打印 hello world

第一个程序 print ("Hello world!")这种程序虽然简单,却有其用途:如果它能够在你的系统上正确地运行,你编写的任何 Python 程序都将如此。 如果没有看到这样的输出,请检查你输入的每个字符。你是不是将 print 的首字母…

sap系统连接其它系统

本文来自博客园,作者:Lovemywx2,转载请注明原文链接:https://www.cnblogs.com/1187163927ch/p/8669859.html JAVA连接ORACLE数据库 1,首先需要在Oracle安装完成之后新建一个用户 --新建用户 create user chenh iden…