Python进阶之递归函数的用法及其示例

作者是一名沉迷于Python无法自拔的蛇友,为提高水平,把Python的重点和有趣的实例发在简书上。

一、递归

是指函数/过程/子程序在运行过程序中直接或间接调用自身而产生的重入现象。在计算机编程里,递归指的是一个过程:函数不断引用自身,直到引用的对象已知。使用递归解决问题,思路清晰,代码少。但是在主流高级语言中(如C语言、Pascal语言等)使用递归算法要耗用更多的栈空间,所以在堆栈尺寸受限制时(如嵌入式系统或者内核态编程),应避免采用。所有的递归算法都可以改写成与之等价的非递归算法。

(来源于百度,看不懂正常,术语就是不说人话)

下面是笔者的个人理解:递归就是在函数内部调用自己的函数被称之为递归。

看不懂?形象的举几个例子!

  1. 一个洋葱是一个带着一层洋葱皮的洋葱。
  2. 递归就是包子馅的包子,它的极限是馒头。

真的形象!有点扯远了...言归正传,下面我们通过递归来理解递归!

二、实例

#直接调用自己:
def func():
  print('from func')
  func()

func()
#间接调用自己
def foo():
  print('from foo')
  bar()

def bar():
  print('from bar')
  foo()

foo()
#递归的实现:
def age(n):
  if n == 1:
    return 18
  return age(n-1)+2

print(age(5))

# age(5)=age(4)+2 第一次进入
# age(4)=age(3)+2 第二次进入
# age(3)=age(2)+2 第三次进入
# age(2)=age(1)+2 第四次进入
# age(1)=18 第五次进入,最后判断终止条件

# age(n)=age(n-1)+2 #n>1 递归终止条件
# age(1)=18 #n=1     等于终止条件

三、递归的回溯与递推

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

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

# 实例
l =[1, 2, [3, [4, 5, 6, [7, 8, [9, 10, [11, 12, 13, [14, 15,[16,[17,]],19]]]]]]]

def search(l):
  for item in l:
    if type(item) is list:
      search(item)
    else:
      print(item)

search(l)

三、实例代码

阶乘

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

上面就是一个实现阶层的递归函数,我们来试一试。

>>> fact(1)
1
>>> fact(5)
120
>>>fact(100)
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

可能有点懵吧,来看一看计算过程吧:

===> fact(5)

===> 5 * fact(4)

===> 5 * (4 * fact(3))

===> 5 * (4 * (3 * fact(2)))

===> 5 * (4 * (3 * (2 * fact(1))))

===> 5 * (4 * (3 * (2 * 1)))

===> 5 * (4 * (3 * 2))

===> 5 * (4 * 6)

===> 5 * 24

===> 120

斐波那契数列

def fib(n):
  if n <2:
     return n
  else:
    return fib(n -1) + fib(n -2)

这个不难,还是去看下一个例子吧!

汉诺塔

def hanoti(n,x1,x2,x3):
  if(n == 1):
    print('move:',x1,'-->',x3)
    return
  hanoti(n-1,x1,x3,x2)
  print('move:',x1,'-->',x3)
  hanoti(n-1,x2,x1,x3)

哈哈,肯定看不懂吧,没事,看看流程图,你会豁然开朗~

总结

以上就是笔者为大家总结的关于Python递归的内容,希望大家能够喜欢~也希望大家多多支持我们。

(0)

相关推荐

  • 讲解Python中的递归函数

    在函数内部,可以调用其他函数.如果一个函数在内部调用自身本身,这个函数就是递归函数. 举个例子,我们来计算阶乘n! = 1 x 2 x 3 x ... x n,用函数fact(n)表示,可以看出: fact(n) = n! = 1 x 2 x 3 x ... x (n-1) x n = (n-1)! x n = fact(n-1) x n 所以,fact(n)可以表示为n x fact(n-1),只有n=1时需要特殊处理. 于是,fact(n)用递归的方式写出来就是: def fact(n):

  • 提升Python效率之使用循环机制代替递归函数

    斐波那契数列 当年,典型的递归题目,斐波那契数列还记得吗? def fib(n): if n==1 or n==2: return 1 else: return fib(n-1)+fib(n-2) 当然, 为了程序健壮性,加上 try...except... def fib(n): if isinstance(n, int): print('兄弟,输入正整数哈') return try: if n==1 or n==2: return 1 elif n <= 0: print('兄弟别输入0或负

  • Python3基础教程之递归函数简单示例

    概述 递归函数即直接或间接调用自身的函数,且递归过程中必须有一个明确的递归结束条件,称为递归出口.递归极其强大一点就是能够遍历任意的,不可预知的程序的结构,比如遍历复杂的嵌套列表. 递归求和 我们可以利用递归函数实现一个Python内置函数sum()的递归版. # 递归 def d_sum(L): if not L: return 0 else: return L[0] + d_sum(L[1:]) sum_l = d_sum(range(10)) print(sum_l) 示例结果 45 该递

  • Python进阶:生成器 懒人版本的迭代器详解

    从容器.可迭代对象谈起 所有的容器都是可迭代的(iterable),迭代器提供了一个next方法.iter()返回一个迭代器,通过next()函数可以实现遍历. def is_iterable(param): try: iter(param) return True except TypeError: return False params = [ 1234, '1234', [1, 2, 3, 4], set([1, 2, 3, 4]), {1:1, 2:2, 3:3, 4:4}, (1, 2

  • python使用 zip 同时迭代多个序列示例

    本文实例讲述了python使用 zip 同时迭代多个序列.分享给大家供大家参考,具体如下: zip 可以平行地遍历多个迭代器 python 3中zip相当于生成器,遍历过程中产生元祖,python2会把元祖生成好,一次性返回整份列表 zip(x,y,z)会生成一个可返回元组 (x,y,z) 的迭代器 >>> x = [1, 2, 3, 4, 5] >>> y = ['a', 'b', 'c', 'd', 'e'] >>> z = ['a1', 'b2'

  • python中的函数递归和迭代原理解析

    这篇文章主要介绍了python中的函数递归和迭代原理解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 一.递归 1.递归的介绍 什么是递归? 程序调用自身的编程技巧称为递归( recursion).递归做为一种算法在程序设计语言中广泛应用. 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大

  • Jacobi迭代算法的Python实现详解

    import numpy as np import time 1.1 Jacobi迭代算法 def Jacobi_tensor_V2(A,b,Delta,m,n,M): start=time.perf_counter()#开始计时 find=0#用于标记是否在规定步数内收敛 X=np.ones(n)#迭代起始点 x=np.ones(n)#用于存储迭代的中间结果 d=np.ones(n)#用于存储Ax**(m-2)的对角线部分 m1=m-1 m2=2-m for i in range(M): pr

  • Python递归函数定义与用法示例

    本文实例讲述了Python递归函数定义与用法.分享给大家供大家参考,具体如下: 递归函数 在函数内部,可以调用其他函数.如果一个函数在内部调用自身本身,这个函数就是递归函数. 举个例子,我们来计算阶乘 n! = 1 * 2 * 3 * ... * n,用函数 fact(n)表示,可以看出: fact(n) = n! = 1 * 2 * 3 * ... * (n-1) * n = (n-1)! * n = fact(n-1) * n 所以,fact(n)可以表示为 n * fact(n-1),只有

  • Python进阶之递归函数的用法及其示例

    作者是一名沉迷于Python无法自拔的蛇友,为提高水平,把Python的重点和有趣的实例发在简书上. 一.递归 是指函数/过程/子程序在运行过程序中直接或间接调用自身而产生的重入现象.在计算机编程里,递归指的是一个过程:函数不断引用自身,直到引用的对象已知.使用递归解决问题,思路清晰,代码少.但是在主流高级语言中(如C语言.Pascal语言等)使用递归算法要耗用更多的栈空间,所以在堆栈尺寸受限制时(如嵌入式系统或者内核态编程),应避免采用.所有的递归算法都可以改写成与之等价的非递归算法. (来源

  • Python进阶之尾递归的用法实例

    作者是一名沉迷于Python无法自拔的蛇友,为提高水平,把Python的重点和有趣的实例发在简书上. 尾递归 如果一个函数中所有递归形式的调用都出现在函数的末尾,我们称这个递归函数是尾递归的.当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时,这个递归调用就是尾递归.尾递归函数的特点是在回归过程中不用做任何操作,这个特性很重要,因为大多数现代的编译器会利用这种特点自动生成优化的代码. (来源于不说人话的某度) 下面是笔者的个人理解:把计算出的值存在函数内部(当然不止尾递归)

  • python re.match()用法相关示例

    学习python爬虫时遇到了一个问题,书上有示例如下: import re line='Cats are smarter than dogs' matchObj=re.match(r'(.*)are(.*?).*',line) if matchObj: print('matchObj.group():',matchObj.group()) print('matchObj.group(1):', matchObj.group(1)) print('matchObj.group(2):', matc

  • 前端进阶JS数组高级用法大全教程示例

    目录 1.批量制造数据 2.数组合并去重 3.创建数组的几种方式 4.类数组 常见的类数组 判断是否是类数组 类数组如何转换为数组 如何让类数组使用上数组丰富的内建方法 类数组和数组的区别 5.数组方法的使用注意事项 数组的长度 数组的空元素 empty 基于值进行运算,空位的值作为undefined join和toString,空位怎么处理 数组不会自动添加分号 indexOf与includes 数组可变长度问题 数组查找和过滤 改变自身的方法 delete误区 push vs concat

  • Python基础之函数基本用法与进阶详解

    本文实例讲述了Python基础之函数基本用法与进阶.分享给大家供大家参考,具体如下: 目标 函数参数和返回值的作用 函数的返回值 进阶 函数的参数 进阶 递归函数 01. 函数参数和返回值的作用 函数根据 有没有参数 以及 有没有返回值,可以 相互组合,一共有 4 种 组合形式 无参数,无返回值 无参数,有返回值 有参数,无返回值 有参数,有返回值 定义函数时,是否接收参数,或者是否返回结果,是根据 实际的功能需求 来决定的! 如果函数 内部处理的数据不确定,就可以将外界的数据以参数传递到函数内

  • Python多继承原理与用法示例

    本文实例讲述了Python多继承原理与用法.分享给大家供大家参考,具体如下: python中使用多继承,会涉及到查找顺序(MRO).重复调用(钻石继承,也叫菱形继承问题)等 MRO MRO即method resolution order,用于判断子类调用的属性来自于哪个父类.在Python2.3之前,MRO是基于深度优先算法的,自2.3开始使用C3算法,定义类时需要继承object,这样的类称为新式类,否则为旧式类 从图中可以看出,旧式类查找属性时是深度优先搜索,新式类则是广度优先搜索 C3算法

  • Python基础之变量基本用法与进阶详解

    本文实例讲述了Python基础之变量基本用法与进阶.分享给大家供大家参考,具体如下: 目标 变量的引用 可变和不可变类型 局部变量和全局变量 01. 变量的引用 变量 和 数据 都是保存在 内存 中的 在 Python 中 函数 的 参数传递 以及 返回值 都是靠 引用 传递的 1.1 引用的概念 在 Python 中 变量 和 数据 是分开存储的 数据 保存在内存中的一个位置 变量 中保存着数据在内存中的地址 变量 中 记录数据的地址,就叫做 引用 使用 id() 函数可以查看变量中保存数据所

  • python进阶collections标准库使用示例详解

    目录 前言 namedtuple namedtuple的由来 namedtuple的格式 namedtuple声明以及实例化 namedtuple的方法和属性 OrderedDict popitem(last=True) move_to_end(key, last=True) 支持reversed 相等测试敏感 defaultdict 小例子1 小例子2 小例子3 Counter对象 创建方式 elements() most_common([n]) 应用场景 deque([iterable[,

  • Python中str.join()简单用法示例

    本文实例讲述了Python中str.join()简单用法.分享给大家供大家参考,具体如下: Python join() 方法用于将序列中的元素以指定的字符连接生成一个新的字符串.其中,序列中的元素应是字符串类型. join()方法语法: str.join(sequence) 例子: >>> str='-' >>> l=['2016','5','9'] >>> t=('2016','5','9') >>> str.join(l) '20

  • Python进阶之使用selenium爬取淘宝商品信息功能示例

    本文实例讲述了Python进阶之使用selenium爬取淘宝商品信息功能.分享给大家供大家参考,具体如下: # encoding=utf-8 __author__ = 'Jonny' __location__ = '西安' __date__ = '2018-05-14' ''' 需要的基本开发库文件: requests,pymongo,pyquery,selenium 开发流程: 搜索关键字:利用selenium驱动浏览器搜索关键字,得到查询后的商品列表 分析页码并翻页:得到商品页码数,模拟翻页

随机推荐