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

yipeiwu_com5年前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实现递归算法,代码结构较为简单,但效率非常低下,而迭代算法可读性强,执行效率也非常之快。所以在运用递归算法时应谨慎。

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持【听图阁-专注于Python设计】。

相关文章

matplotlib subplots 调整子图间矩的实例

在matplotlib中,用subplots画子图时,有时候需要调整子图间矩,包括子图与边框的间矩,子图间上下间矩,子图间左右间矩,可以使用fig.tight_layout()函数:...

Python自定义线程池实现方法分析

Python自定义线程池实现方法分析

本文实例讲述了Python自定义线程池实现方法。分享给大家供大家参考,具体如下: 关于python的多线程,由与GIL的存在被广大群主所诟病,说python的多线程不是真正的多线程。但多...

Python利用BeautifulSoup解析Html的方法示例

介绍 Beautiful Soup提供一些简单的、python式的函数用来处理导航、搜索、修改分析树等功能。它是一个工具箱,通过解析文档为用户提供需要抓取的数据,因为简单,所以不需要多少...

详解python使用pip安装第三方库(工具包)速度慢、超时、失败的解决方案

详解python使用pip安装第三方库(工具包)速度慢、超时、失败的解决方案

人生苦短,我用python!为什么很多人喜欢用python,因为包多呀,各种调包。但是调包有的时候也调的闹心,因为安装包不是失败就是很慢,很影响自己的工作进度,这里给出一个pip快速安装...

python+OpenCV实现车牌号码识别

python+OpenCV实现车牌号码识别

基于python+OpenCV的车牌号码识别,供大家参考,具体内容如下 车牌识别行业已具备一定的市场规模,在电子警察、公路卡口、停车场、商业管理、汽修服务等领域已取得了部分应用。一个典型...