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日

相关文章

  • Python中可以用三种方法判断文件是否存在

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

    Python开发 2023年4月2日
    00
  • Python3教程:Pandas模块删除数据的几种情况

    开始之前,pandas中DataFrame删除对象可能存在几种情况1、删除具体列2、删除具体行3、删除包含某些数值的行或者列4、删除包含某些字符、文字的行或者列本文就针对这四种情况探讨一下如何操作。 数据准备 模拟了一份股票交割的记录。 In [1]: import pandas as pd In [2]: data = { …: ‘证券名称’ : [‘…

    Python开发 2023年4月2日
    00
  • Python学习:property装饰器

    1.property 装饰器:装饰器是在不修改被装饰对象源代码以及调用方式的前提下为被装饰对象添加新功能的可调用对象 property是一个装饰器,是用来绑定给对象的方法伪造成一个数据属性 装饰器property,可以将类中的函数“伪装成”对象的数据属性,对象在访问该特殊属性时会触发功能的执行,然后将返回值作为本次访问的结果。 使用property有效地保证…

    Python开发 2023年4月2日
    00
  • Python模块:subprocess模块教程

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

    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
  • python3教程:默认参数为列表

    默认参数的坑 定义一个函数,传入一个list,添加一个end再返回 def add_end(L=[]): L.append(‘END’) return L 正常调用时,结果似乎不错 print (add_end([1,2,3])) #[1, 2, 3, ‘END’] 使用默认参数调用时,一开始结果也是对的,但是再次调用时,结果就不对了 ”’ 学习中遇到问题…

    Python开发 2023年4月2日
    00
  • Python中高阶函数与装饰器教程

    1高阶函数 1.1 数学概念 回顾下数学知识: y=f(x) 这是最开始接触的普通函数 y=g(f(x)) 这个就是我们接触到的高阶函数 在数学和计算机科学中,高阶函数至少应当是满足下面一个条件的函数: 1)接受一个或者多个函数作为参数 2)输出一个函数 程序中我们的高阶函数也类似 示例计数器的函数: def counter(base): def inc(s…

    Python开发 2023年3月31日
    00
  • 10道Python面试题

    1、Python里面如何拷贝一个对象?(赋值,浅拷贝,深拷贝的区别) 答:赋值(=),就是创建了对象的一个新的引用,修改其中任意一个变量都会影响到另一个。 浅拷贝:创建一个新的对象,但它包含的是对原始对象中包含项的引用(如果用引用的方式修改其中一个对象,另外一个也会修改改变){1,完全切片方法;2,工厂函数,如list();3,copy模块的copy()函数…

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