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

这篇文章主要介绍了python中的函数递归和迭代原理解析,文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下

一、递归

1、递归的介绍

什么是递归?

程序调用自身的编程技巧称为递归（ recursion）。递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。

递归要注意的是,它是直接或间接调用自身,所以在使用递归时,必须有一个明确的递归结束条件,称为递归出口,否则,他就会陷入死循环。

尾递归

如果一个函数中所有递归形式的调用都出现在函数的末尾，我们称这个递归函数是尾递归的。当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时，这个递归调用就是尾递归。尾递归函数的特点是在回归过程中不用做任何操作，这个特性很重要，因为大多数现代的编译器会利用这种特点自动生成优化的代码。

python不是一门函数式编程语言，本身不支持尾递归（没有对尾递归做优化），而且对递归的次数有限制，当递归深度超过1000时，会抛出异常，虽然可以通过sys模块修改提柜的深度，，但是因为不是尾递归，仍然要保存栈，内存大小一定，不可能无限递归，而且无限制地递归调用本身是毫无意义的

import sys
sys.getrecursionlimit()
sys.setrecursionlimit(2000) # 修改递归深度为2000

2、递归的应用

递归分为两个阶段：回溯和递推　　
递推 : 把复杂的问题的求解推到比原问题简单一些的问题的求解;

回溯 : 当获得最简单的情况（递归出口）后,逐步返回,依次得到复杂的解

下面通过一个例子来分析这个过程 ：

这是一个十进制转化为二进制的函数，十进制转化为二进制就是 将十进制不断地除以2，直到商为0，然后将余数从后到前排列起来

def Decbin(x):
  result = ''
  if x:
    return Decbin(x // 2) + str(x % 2)
  else:
    return result
print(Decbin(7))

当我们传入x为7时，很明显x不为0，所以我们便进入了下次一循环,注意这时的第一层函数并没有结束，而是一直在等待着下一层函数的返回结果。接着进入了第二层函数，参数为3，很明显也不为0，接着又进入了第三层函数，此时第二层函数也在等待下一层函数的返回结果，以此类推，这就是递归函数的回溯。当我们的参数为0的时候，便会执行else的代码，这时候函数就不再回溯，而是开始往前递推。

二、迭代与递归

1、什么是迭代？

Python中的迭代是指通过重复执行的代码处理相似的数据集的过程，并且本次迭代的处理数据要依赖上一次的结果继续往下做，上一次产生的结果为下一次产生结果的初始状态，如果中途有任何停顿，都不能算是迭代。常见的for循环遍历对象就是迭代。

2、用python实现递归算法，代码结构较为简单，但效率非常低下，而迭代算法可读性强，执行效率也非常之快。所以在运用递归算法时应谨慎。

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

赞 (0)

相关推荐

  • 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使用 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进阶:生成器 懒人版本的迭代器详解

    从容器.可迭代对象谈起 所有的容器都是可迭代的(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

  • 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进阶之递归函数的用法及其示例

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

  • 讲解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或负

  • 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中的函数递归和迭代原理解析

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

  • Python 中 -m 的典型用法、原理解析与发展演变

    在命令行中使用 Python 时,它可以接收大约 20 个选项(option),语法格式如下: python [-bBdEhiIOqsSuvVWx?] [-c command | -m module-name | script | - ] [args] 本文想要聊聊比较特殊的"-m"选项: 关于它的典型用法.原理解析与发展演变的过程. 首先,让我们用"--help"来看看它的解释: -m mod run library module as a script (ter

  • python中Genarator函数用法分析

    本文实例讲述了python中Genarator函数用法.分享给大家供大家参考.具体如下: Generator函数的定义与普通函数的定义没有什么区别,只是在函数体内使用yield生成数据项即可.Generator函数可以被for循环遍历,而且可以通过next()方法获得yield生成的数据项. def func(n): for i in range(n): yield i for i in func(3): print i r=func(3) print r.next() print r.next

  • Python中zip()函数用法实例教程

    本文实例讲述了Python中zip()函数的定义及用法,相信对于Python初学者有一定的借鉴价值.详情如下: 一.定义: zip([iterable, ...]) zip()是Python的一个内建函数,它接受一系列可迭代的对象作为参数,将对象中对应的元素打包成一个个tuple(元组),然后返回由这些tuples组成的list(列表).若传入参数的长度不等,则返回list的长度和参数中长度最短的对象相同.利用*号操作符,可以将list unzip(解压). 二.用法示例: 读者看看下面的例子,

  • 基于Python中求和函数sum的用法详解

    基于Python中求和函数sum的用法详解 今天在看<集体编程智慧>这本书的时候,看到一段Python代码,当时是百思不得其解,总觉得是书中排版出错了,后来去了解了一下sum的用法,看了一些Python大神写的代码后才发现是自己浅薄了!特在此记录一下.书中代码段摘录如下: from math import sqrt def sim_distance(prefs, person1, person2): # 得到shared_items的列表 si = {} for item in prefs[p

  • Python中zip()函数的解释和可视化(实例详解)

    zip()的作用 先看一下语法: zip(iter1 [,iter2 [...]]) -> zip object Python的内置help()模块提供了一个简短但又有些令人困惑的解释: 返回一个元组迭代器,其中第i个元组包含每个参数序列或可迭代对象中的第i个元素.当最短的可迭代输入耗尽时,迭代器将停止.使用单个可迭代参数,它将返回1元组的迭代器.没有参数,它将返回一个空的迭代器. 与往常一样,当您精通更一般的计算机科学和Python概念时,此模块非常有用.但是,对于初学者来说,这段话只会引发更

  • Python中zip函数如何使用

    介绍 zip() 函数用于将可迭代的对象作为参数,将对象中对应的元素打包成一个个元组,然后返回由这些元组组成的列表. ps. 如果各个迭代器的元素个数不一致,则返回列表长度与最短的对象相同,利用 * 号操作符,可以将元组解压为列表. 例子 a = [1,2,3] b = [4,5,6] c = [4,5,6,7,8] zipped = zip(a,b) # 打包为元组的列表 # 输出:[(1, 4), (2, 5), (3, 6)] zip(a,c) # 元素个数与最短的列表一致 # 输出:[(

  • python中zip()函数遍历多个列表方法

    在对列表的元素进行找寻时,会频繁的说到遍历的理念.对于复杂的遍历要求,如多个列表中查找就显然不适合用for循环.本篇所要带来的是zip() 函数的方法,能够对多个迭代器进行遍历.下面我们就python中zip的说明.语法.使用注意点进行讲解,然后带来遍历多个列表的实例. 1.说明 zip() 函数用于将可迭代的对象作为参数,将对象中对应的元素打包成一个个元组,然后返回由这些元组组成的列表.(注:在python3中返回的是zip对象) 2.语法 zip(iterable, ...) # 其中 it

  • python中super()函数的理解与基本使用

    python中super()函数的理解与基本使用

    目录 前言 super的用法 super的原理 Python super()使用注意事项 混用super与显式类调用 不同种类的参数 总结 前言 Python是一门面向对象的语言,定义类时经常要用到继承,在类的继承中,子类继承父类中已经封装好的方法,不需要再次编写,如果子类如果重新定义了父类的某一方法,那么该方法就会覆盖父类的同名方法,但是有时我们希望子类保持父类方法的基础上进行扩展,而不是直接覆盖,就需要先调用父类的方法,然后再进行功能的扩展,这时就可以通过super来实现对父类方法的调用.

  • python中similarity函数实例用法

    1.similarity函数接收两个列表,并返回由两个列表中相同元素组成的列表. 2.函数使用列表推导,遍历所有a列表中的元素,并使用in关键词来判断这些元素是否存在于b列表中. 实例 def similarity(a, b): return [item for item in a if item in b] # EXAMPLES similarity([1, 2, 3], [1, 2, 4]) # [1, 2] 知识点扩充: python 语义similarity_Python:string的

随机推荐