Python递归的几个经典案例

当我们碰到诸如需要求阶乘或斐波那契数列的问题时,使用普通的循环往往比较麻烦,但如果我们使用递归时,会简单许多,起到事半功倍的效果。这篇文章主要和大家分享一些和递归有关的经典案例,结合一些资料谈一下个人的理解,也借此加深自己对递归的理解和掌握一些递归基础的用法。

一、递归的简介

1、递归的百度百科定义

程序调用自身的编程技巧称为递归( recursion)。

递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或
间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量。

递归的能力在于用有限的语句来定义对象的无限集合。一般来说,递归需要有边界条件、递归前进
段和递归返回段。当边界条件不满足时,递归前进;当边界条件满足时,递归返回。

2、递归的通俗理解

递归就是在函数内部调用自己的函数被称之为递归。

3、几个关于递归通俗的比喻

1.我们使用的词典,本身就是递归,为了解释一个词,需要使用更多的词。当你查一个词,发现这个词的解释中某个词仍然不懂,于是你开始查这第二个词,可惜,第二个词里仍然有不懂的词,于是查第三个词,这样查下去,直到有一个词的解释是你完全能看懂的,那么递归走到了尽头,然后你开始后退,逐个明白之前查过的每一个词,最终,你明白了最开始那个词的意思。

2.一个小朋友坐在第10排,他的作业本被小组长扔到了第1排,小朋友要拿回他的作业本,可以怎么办?他可以拍拍第9排小朋友,说:“帮我拿第1排的本子”,而第9排的小朋友可以拍拍第8排小朋友,说:“帮我拿第1排的本子”...如此下去,消息终于传到了第1排小朋友那里,于是他把本子递给第2排,第2排又递给第3排...终于,本子到手啦!这就是递归,拍拍小朋友的背可以类比函数调用,而小朋友们都记得要传消息、送本子,是因为他们有记忆力,这可以类比栈。

3.一个洋葱是一个带着一层洋葱皮的洋葱。

4、最简单的递归的实例 

# 将 10不断除以2,直至商为0,输出这个过程中每次得到的商的值。
def recursion(n):
    v = n//2 # 地板除,保留整数
    print(v) # 每次求商,输出商的值
    if v==0:
        ''' 当商为0时,停止,返回Done'''
        return 'Done'
    v = recursion(v) # 递归调用,函数内自己调用自己
recursion(10) # 函数调用

输出结果:

5
2
1
0

5、递归的特点

通过以上的介绍,我们大致可以总结出递归的以下几个特点:

1、必须有一个明确的结束条件
2、每次进入更深一层递归时,问题规模(计算量)相比上次递归都应有所减少
3、递归效率不高,递归层次过多会导致栈溢出(在计算机中,函数调用是通过栈(stack)这种数据结构实现的,每当进入一个函数调用,栈就会加一层栈帧,每当函数返回,栈就会减一层栈帧。由于栈的大小不是无限的,所以,递归调用的次数过多,会导致栈溢出)

关于递归还有两个名词,可以概括递归实现的过程

递推:像上边递归实现所拆解,递归每一次都是基于上一次进行下一次的执行,这叫递推

回溯:则是在遇到终止条件,则从最后往回返一级一级的把值返回来,这叫回溯

二、递归经典案例

1、递归求阶乘

实例如下:

'''
学习中遇到问题没人解答?小编创建了一个Python学习交流群:711312441
寻找有志同道合的小伙伴,互帮互助,群里还有不错的视频学习教程和PDF电子书!
'''
# 1!+2!+3!+4!+5!+...+n!
def factorial(n):
    ''' n表示要求的数的阶乘 '''
    if n==1:
        return n # 阶乘为1的时候,结果为1,返回结果并退出
    n = n*factorial(n-1) # n! = n*(n-1)!
    return n  # 返回结果并退出
res = factorial(5) #调用函数,并将返回的结果赋给res
print(res) # 打印结果

2、递归推斐波那契数列

实例如下:

# 1,1,2,3,5,8,13,21,34,55,试判断数列第十五个数是哪个?
def fabonacci(n):
    ''' n为斐波那契数列 '''
    if n <= 2:
        ''' 数列前两个数都是1 '''
        v = 1
        return v # 返回结果,并结束函数
    v = fabonacci(n-1)+fabonacci(n-2) # 由数据的规律可知,第三个数的结果都是前两个数之和,所以进行递归叠加
    return v  # 返回结果,并结束函数
print(fabonacci(15)) # 610    调用函数并打印结果

3、二分法找有序列表指定值

实例如下:

data = [1,3,6,13,56,123,345,1024,3223,6688]
def dichotomy(min,max,d,n):
    '''
    min表示有序列表头部索引
    max表示有序列表尾部索引
    d表示有序列表
    n表示需要寻找的元素
    '''
    mid = (min+max)//2
    if mid==0:
        return 'None'
    elif d[mid]<n:
        print('向右侧找!')
        return dichotomy(mid,max,d,n)
    elif d[mid]>n:
        print('向左侧找!')
        return dichotomy(min,mid,d,n)
    else:
        print('找到了%s'%d[mid])
        return 
res = dichotomy(0,len(data),data,222)
print(res)

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:Python递归的几个经典案例 - Python技术站

(0)
上一篇 2023年4月2日
下一篇 2023年4月2日

相关文章

  • Python3教程:math 模块的用法

    我们知道 Python 有很多运算符可以进行数学运算,如果是简单的问题还好说,但是要处理一些相对复杂的问题也要我们自己一行一行手动的来编写吗?答案当然不是,Python 提供了 math 模块对一些数学运算提供了支持。 1.简介 math 模块提供了对 C 标准定义的数学函数的访问,但该模块并不支持复数运算,如果想使用复数预算需使用 cmath 模块,将支持…

    Python开发 2023年4月2日
    00
  • Python中的关键字的用法

    Python有哪些关键字 Python常用的关键字 and, del, from, not, while, as, elif, global, or, with, assert, else, if, pass, yield, break, except, import, print, class, exec, in, raise, contiue, fina…

    Python开发 2023年3月31日
    00
  • Python中logging模块用法

    一、低配logging 日志总共分为以下五个级别,这个五个级别自下而上进行匹配 debug–>info–>warning–>error–>critical,默认最低级别为warning级别。 1.v1 import logging logging.debug(‘调试信息’) logging.info(‘正常信息’) loggi…

    Python开发 2023年3月31日
    00
  • Python关于异常处理的教程

    一、什么是异常 异常就是程序运行时发生错误的信号(在程序出现错误时,则会产生一个异常,若程序没有处理它,则会抛出该异常,程序的运行也随之终止),在python中,错误触发的异常如下 1 语法错误 语法错误,根本过不了python解释器的语法检测,必须在程序执行前就改正。 # 语法错误示范一 if # 语法错误示范二 def test: pass # 语法错误…

    Python开发 2023年3月31日
    00
  • Python模块:subprocess模块教程

    一.subprocess模块 subprocess是Python 2.4中新增的一个模块,它允许你生成新的进程,连接到它们的 input/output/error 管道,并获取它们的返回(状态)码。这个模块的目的在于替换几个旧的模块和方法,如: os.system os.spawn* 1.subprocess模块中的常用函数 函数 描述 subprocess…

    Python开发 2023年4月2日
    00
  • python中主要的英语单词汇总

    path [ pɑ:θ ] 路径 unexpected [ˌʌnɪkˈspektɪd] 不期望的 class [klɑ:s] 类 usage [ˈju:sɪdʒ] 使用 public [‘p ʌblik] 公共的,公用的 version [ˈvɜ:ʃn] 版本 private [‘praivit] 私有的,私人的 author [ˈɔ:θə®] 作者 sta…

    Python开发 2023年4月2日
    00
  • Python中可以用三种方法判断文件是否存在

    通常在读写文件之前,需要判断文件或目录是否存在,不然某些处理方法可能会使程序出错。所以最好在做任何操作之前,先判断文件是否存在。 这里将介绍三种判断文件或文件夹是否存在的方法,分别使用os模块、Try语句、pathlib模块。 1.使用os模块 os模块中的os.path.exists()方法用于检验文件是否存在。 判断文件是否存在 import os os…

    Python开发 2023年4月2日
    00
  • python学习:重用父类功能的两种方式

    在子类派生的新方法中如何重用父类的功能方式一:指名道姓调用某一个类下的函数=》不依赖于继承关系 class OldboyPeople: def __init__(self,name,age,sex): self.name=name self.age=age self.sex=sex def f1(self): print(‘%s say hello’ %se…

    Python开发 2023年4月2日
    00
合作推广
合作推广
分享本页
返回顶部