python数据结构之递归方法讲解

目录
  • 1.递归概念
  • 2. 递归三原则
    • 2.1 实现任意进制的数据转换

今天我们来学习python中最为重要的内容之递归，对以往内容感兴趣的同学可以查看下面：

python数据类型: python数据结构：数据类型.
python的输入输出: python数据结构之输入输出、控制和异常.
python面向对象: python数据结构之面向对象.
python算法分析: python数据结构算法分析.
python数据结构之栈、队列和双端队列

递归是在进行重复性工作中经常考到的问题，非常值得学习。

1.递归概念

递归是解决问题的一种方法，它将问题不断地分成更小的子问题，直到子问题可以用普通的方法解决。通常情况下，递归会使用一个不停调用自己的函数。尽管表面上看起来很普通，但是递归可以帮助我们写出非常优雅的解决方案。对于某些问题，如果不用递归，就很难解决。
上面的话很难理解，我们用一个例子来说明：我们需要求解一个数组的所有数值之和。

#用for循环的简单函数
def getsum(numlist):
    a=0
    for i in numlist:
        a=i+a
    return a

结果如下：

如果暂时没有 while 循环和 for 循环。应该如何计算结果呢? 这个时候就需要想到我们计算加法的时候，是接受2个参数的函数，根据这个思想，我们将求一列数之和重新定义成求数字对之和。

注：最内层的括号对(7 + 9)不用 循环或者其他特殊语法结构就能直接求解。
拟代码表示

#first(list)返回列表中的第一个元素，rest(list)则返回其余元素。用 Python 可以轻松地实现这个等式，
getsum(list)=first(list)+getsum(rest(list))

代码表示：

#这是一个递归小案例，这个函数在函数内部自己调用了自listsum(numlist[1:])
def listsum(numlist):
    if len(numlist)==1:#当数组的长度为1时，代表是数组是一个数了
        return numlist[0]
    else:
        return numlist[0] + listsum(numlist[1:])#第一个数加上后面的数，这里自己调用了自己，是数组不断递归的条件

在这一段代码中，有两个重要的思想值得探讨。首先，第 2 行检查列表是否只包含一个元素。 这个检查非常重要，同时也是该函数的退出语句。对于长度为 1 的列表，其元素之和就是列表中的数。其次，listsum 函数在第 5 行调用了自己!这就是我们将 listsum 称为递归函数的原因——递归函数会调用自己。

演示一下相加过程

2. 递归三原则

递归算法有三个重要的原则：

  • 递归算法必须有停止条件
  • 递归算法必须改变其状态并向停止条件靠近
  • 递归算法必须递归地调用自己

让我们看看我们第一个案例是怎么实现这个部分的：

  • len(numlist)==1 用来判断停止条件
  • numlist[1:] 代表问题的数据以某种方式变得更小
  • return numlist[0] + listsum(numlist[1:]) 代表递归地调用自己

递归的逻辑并不是循环，而是将问题分解成更小、更容易解决的子问题。

2.1 实现任意进制的数据转换

下面展示一下将10进制的29转换为2进制数的方法，按照这个方法，可以将10进制转化为任意进制的数。

这里我们用递归来实现2~16进制数的转换

#n代表要转化的10进制数，base代表你要实现的多少进制的数
def toStr(n, base):
    convertString = "0123456789ABCDEF"#取对应位置的字符
    if n < base:#如果10进制数小于你所转换的进制数位数，则直接选择字符
        return convertString[n]
    else:#递归核心，n//base获取结果，然后进行递归
        return toStr(n//base, base) + convertString[n%base]

将15转化为16进制数

将15转化为2进制数

到此这篇关于python数据结构之递归方法讲解的文章就介绍到这了,更多相关python递归内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • python数据结构:数据类型

    python数据结构:数据类型

    目录 1.数据是什么? 2.数据类型 2.1内建原子数据类型 2.2 内建集合数据类型 3.集合数据类型的方法 3.1 列表 3.2 字符串 3.3 元祖 3.4 集合 3.5 字典 1.数据是什么? 在 Python 以及其他所有面向对象编程语言中,类都是对数据的构成(状态)以及数据 能做什么(行为)的描述.由于类的使用者只能看到数据项的状态和行为,因此类与抽象数据类 型是相似的.在面向对象编程范式中,数据项被称作对象.一个对象就是类的一个实例. 2.数据类型 2.1内建原子数据类型 Pyth

  • 基于Python数据结构之递归与回溯搜索

    目录 1. 递归函数与回溯深搜的基础知识 2. 求子集 (LeetCode 78) 3. 求子集2 (LeetCode 90) 4. 组合数之和(LeetCode 39,40) 5. 生成括号(LeetCode 22) 6. N皇后(LeetCode 51,52) 7. 火柴棍摆正方形(LeetCode 473) 1. 递归函数与回溯深搜的基础知识 递归是指在函数内部调用自身本身的方法.能采用递归描述的算法通常有这样的特征:为求解规模为N的问题,设法将它分解成规模较小的问题,然后从这些小问题的解

  • python数据结构之栈、队列及双端队列

    python数据结构之栈、队列及双端队列

    目录 1.线性数据结构的定义 2.栈 2.1 栈的定义 2.2 栈的数据类型 2.3 用python实现栈 2.4 栈的应用 3. 队列 3.1 队列的定义 3.2 队列抽象数据类型 3.3 用python实现队列 3.3 队列的应用 4. 双端队列 4.1 双端队列的定义 4.2 双端队列抽象数据类型 4.3 用python实现双端队列 4.3 双端队列的应用 5.链表 5.1 链表定义 5.2 用python实现链表 前文学习: python数据类型: python数据结构:数据类型. py

  • python数据结构输入输出及控制和异常

    python数据结构输入输出及控制和异常

    目录 1. 输入 input 2. 输出 print 2.1 普通输出 2.2 格式化输出 3. 控制语句 4. 异常处理 前言: python数据类型: python数据结构之数据类型. 今天我们主要来介绍一些内置函数,比如输入输出,控制,和异常的用法,尤其是输出和控制,用的太多了,写算法题,输出数据格式问题,对以后都会很有帮助. 1. 输入 input 程序经常需要与用户进行交互,以获得数据或者提供某种结果.Python 提供了一个函数,它使得我们可以要求用户输入数据并且返回一个字 符串的引

  • Python 函数的递归详解

    Python 函数的递归详解

    目录 1.1.递归函数的特点 1.2 递归案例 ----- 计算数字累加 总结 函数调用自身的 编程技巧 称为递归. 1.1.递归函数的特点 特点: 一个函数 内部 调用自己. 函数内部可以调用其他函数,当然在函数内部也可以调用自己. 代码特点: 1).函数内部的 代码 是相同的,只是针对 参数 不同,处理的结果不同: 2).当 参数满足一个条件 时,函数不再执行: 这个非常重要,通常被称为递归的出口,否则 会出现死循环! def sum_number(num): print(num) # 递归

  • Python基础学习之深浅拷贝问题及递归函数练习

    Python基础学习之深浅拷贝问题及递归函数练习

    目录 一.深浅拷贝问题 二.递归函数练习 1. 求阶乘 2. 猴子吃桃问题 3. 打印斐波那契数列 一.深浅拷贝问题 在实际工作中,经常涉及到数据的传递,在数据传递使用过程中,可能会发生数据被修改的问题.为了防止数据被修改,就需要在传递一个副本,即使副本被修改,也不会影响原数据的使用.为了生成这个副本,就产生了拷贝.下面先了解一下几个概念:对象.可变类型.引用 Python对象:在 Python 中,对象有一种很通俗的说法是,万物皆对象.说的就是构造的任何数据类型都是一个对象,无论是数字,字符串

  • python数据结构之面向对象

    python数据结构之面向对象

    目录 1. 面向对象编程 2. 构建类 3. 继承 3.1 继承案例 python数据结构:数据类型.  python数据结构输入输出及控制和异常. 今天我们来学习面向对象编程,面向对象这种编程方式非常重要,我们以后学习到的栈.队列.链表都是通过面向对象的方式实现的. 1. 面向对象编程 定义:面向对象是按照人们客观世界的系统思维方式,采用基于对象(实体)的概念建立模型 ,模拟客观世界分析,设计,实现软件的办法.通过面向对象的理念使计算机软件系统能与现实世界中的系统的一一对应. 听到这很多同学应

  • Python全栈之递归函数

    Python全栈之递归函数

    目录 1. 递归函数 2. 递归练习 3. 小练习 总结 1. 递归函数 # ### 递归函数 """ 递归函数 : 自己调用自己的函数 , 叫做递归函数 递 : 去 归 : 回 一去一回叫做递归 """ def digui(n): print(n,"<==1==>") if n > 0: digui(n-1) print(n,"<==2==>") digui(5) "

  • python数据结构算法分析

    python数据结构算法分析

    目录 1.算法分析的定义 2. 大O记法 3. 不同算法的大O记法 3.1 清点法 3.2 排序法 3.3 蛮力法 3.4 计数法 4. 列表和字典操作的复杂度 4.1 列表 4.2 字典 前文学习: python数据类型: python数据结构:数据类型. python的输入输出: python数据结构输入输出及控制和异常. python面向对象: python数据结构面向对象. 今天我们来学习的内容是面试题中都避免不小了的问题,就是算法分析了,什么是算法分析,算法分析是用来分析一个算法的好坏

  • python数据结构之递归方法讲解

    python数据结构之递归方法讲解

    目录 1.递归概念 2. 递归三原则 2.1 实现任意进制的数据转换 今天我们来学习python中最为重要的内容之递归,对以往内容感兴趣的同学可以查看下面: python数据类型: python数据结构:数据类型. python的输入输出: python数据结构之输入输出.控制和异常. python面向对象: python数据结构之面向对象. python算法分析: python数据结构算法分析. python数据结构之栈.队列和双端队列 递归是在进行重复性工作中经常考到的问题,非常值得学习.

  • Python数据结构之递归方法详解

    Python数据结构之递归方法详解

    目录 1.学习目标 2.递归 2.1递归的基本概念 2.2递归的重要性 2.3递归三原则 2.4递归的应用 3.递归示例 3.1列表求和 3.2汉诺塔(Towers of Hanoi)问题 1.学习目标 递归函数是直接调用自己或通过一系列语句间接调用自己的函数.递归在程序设计有着举足轻重的作用,在很多情况下,借助递归可以优雅的解决问题.本节主要介绍递归的基本概念以及如何构建递归程序. 通过本节学习,应掌握以下内容: 理解递归的基本概念,了解递归背后蕴含的编程思想 掌握构建递归程序的方法 2.递归

  • python数据结构之搜索讲解

    python数据结构之搜索讲解

    目录 1. 普通搜索 2. 顺序搜索 1.1 无序下的顺序查找 1.2 有序下的顺序查找 2.二分查找 3.散列查找 3.1 几种散列函数 3.2 处理散列表冲突 3.3 散列表的实现(加1重复) 4.参考资料 往期学习: python数据类型: python数据结构:数据类型. python的输入输出: python数据结构之输入输出及控制和异常. python面向对象: python数据结构面向对象. python算法分析: python数据结构之算法分析. python栈.队列和双端队列:

  • python数据结构之链表的实例讲解

    python数据结构之链表的实例讲解

    在程序中,经常需要将⼀组(通常是同为某个类型的)数据元素作为整体 管理和使⽤,需要创建这种元素组,⽤变量记录它们,传进传出函数等. ⼀组数据中包含的元素个数可能发⽣变化(可以增加或删除元素). 对于这种需求,最简单的解决⽅案便是将这样⼀组元素看成⼀个序列,⽤ 元素在序列⾥的位置和顺序,表示实际应⽤中的某种有意义的信息,或者 表示数据之间的某种关系. 这样的⼀组序列元素的组织形式,我们可以将其抽象为线性表.⼀个线性 表是某类元素的⼀个集合,还记录着元素之间的⼀种顺序关系.线性表是 最基本的数据结构

  • python数据结构链表之单向链表(实例讲解)

    python数据结构链表之单向链表(实例讲解)

    单向链表 单向链表也叫单链表,是链表中最简单的一种形式,它的每个节点包含两个域,一个信息域(元素域)和一个链接域.这个链接指向链表中的下一个节点,而最后一个节点的链接域则指向一个空值. 表元素域elem用来存放具体的数据. 链接域next用来存放下一个节点的位置(python中的标识) 变量p指向链表的头节点(首节点)的位置,从p出发能找到表中的任意节点. 节点实现 class Node(object): """单链表的结点""" def __i

  • Python数据结构之递归可视化详解

    Python数据结构之递归可视化详解

    目录 1.学习目标 2.递归的调用 3.递归可视化 3.1 turtle 库简介 3.1 递归绘图 1.学习目标 递归函数是直接调用自己或通过一系列语句间接调用自己的函数.递归在程序设计有着举足轻重的作用,在很多情况下,借助递归可以优雅的解决问题.虽然使用递归可以快速的解决一些难题,但由于递归的抽象性,使递归难以掌握.为了更好的理解递归函数背后的思想,本节主要通过可视化方式来了解递归函数的执行步骤. 通过本节学习,应掌握以下内容: 提高对递归的理解 利用可视化理解递归函数背后的思想 2.递归的调

  • Python数据结构与算法之链表定义与用法实例详解【单链表、循环链表】

    本文实例讲述了Python数据结构与算法之链表定义与用法.分享给大家供大家参考,具体如下: 本文将为大家讲解: (1)从链表节点的定义开始,以类的方式,面向对象的思想进行链表的设计 (2)链表类插入和删除等成员函数实现时需要考虑的边界条件, prepend(头部插入).pop(头部删除).append(尾部插入).pop_last(尾部删除) 2.1 插入: 空链表 链表长度为1 插入到末尾 2.2 删除 空链表 链表长度为1 删除末尾元素 (3)从单链表到单链表的一众变体: 带尾节点的单链表

  • Python数据结构之双向链表的定义与使用方法示例

    Python数据结构之双向链表的定义与使用方法示例

    本文实例讲述了Python数据结构之双向链表的定义与使用方法.分享给大家供大家参考,具体如下: 和单链表类似,只不过是增加了一个指向前面一个元素的指针而已. 示意图: python 实现代码: #!/usr/bin/python # -*- coding: utf-8 -*- class Node(object): def __init__(self,val,p=0): self.data = val self.next = p self.prev = p class LinkList(obje

  • Python字典和集合讲解

    Python字典和集合讲解

    目录 一.Python字典 1.什么是字典 2.字典的创建方式 2.1 通过其他字典创建 2.2 通过关键字参数创建 2.3 通过键值对的序列创建 2.4 通过dict和zip结合创建 3.字典的访问 3.1 根据键访问值 3.2 使用get()方法访问值 4.in 和 not in 在字典中的使用 5.修改和添加字典中的元素 6.删除字典中的元素 7.更新字典 8.获取字典视图的三个方法 9.遍历字典 10.字典的特点 11.复制字典 二.Python集合(set) 1.什么是集合 2.集合创

  • Python数据结构列表

    Python数据结构列表

    目录 1 序列 2 列表 2.1 列表函数 2.2 列表排序 2.3 解析列表 正则小练习:匹配出以下字符串所有url, import re def find_url(sentence, show_urls=None, delete_urls=None): r = re.compile( r'(?i)\b((?:[a-z][\w-]+:(?:/{1,3}|[a-z0-9%])|www\d{0,3}[.]|[a-z0-9.\-]+[.][a-z]{2,4}/)(?:[^\s()<>]+|\(([

随机推荐