Python递归及尾递归优化操作实例分析

本文实例讲述了Python递归及尾递归优化操作。分享给大家供大家参考，具体如下：

1、递归介绍

递归简而言之就是自己调用自己。使用递归解决问题的核心就是分析出递归的模型，看这个问题能拆分出和自己类似的问题并且有一个递归出口。比如最简单的就5的阶乘，可以把它拆分成5*4!，然后求4!又可以调用自己，这种问题显然可以用递归解决，递归的出口就是求1！，可以直接返回1。用Python实现如下：

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

运行结果：

120

2、尾递归优化

在上面的求递归中，也有一定的缺点，假如说求1000!的阶乘，会出现栈溢出的问题，因为在函数执行中，没调用一个函数都会把当前函数的调用位置和内部变量保存在栈里面，由于栈的空间不是无限大（具体栈的最大空间还没有查找到），假如说调用层数过多，就是出现栈溢出的情况。

这个时候就可以用尾递归优化来解决，尾调用的概念非常简单，一句话就能说清楚，就是指某个函数的最后一步是调用另一个函数。

function f(x){
 return g(x);
}

尾递归优化后的阶乘函数如下：

def fact(n):
  return fact_iter(n,1);
def fact_iter(num, product):
  if num == 1:
    return product
  return fact_iter(num - 1, num * product)
print(fact(5))
print(fact(1000))

尾调用由于是函数的最后一步操作，所以不需要保留外层函数的调用记录，因为调用位置、内部变量等信息都不会再用到了。所以尾递归优化可以有效的防止栈溢出，但是尾递归优化需要编译器或者解释器的支持，遗憾的是，大多数编程语言没有针对尾递归做优化，Python解释器也没有做优化，所以，即使把上面的fact(n)函数改成尾递归方式，也会导致栈溢出。

3、汉诺塔问题

汉诺塔问题也是一个经典的递归问题，具体题目就不说了，这里分析思路。假设hanoi(n, a, b, c)实现把a上的n个盘子移到c上。

当只有一个盘子时，直接从A移动到C即可

如果有3个盘子，可以这样：

# A --> C
# A --> B
# C --> B
# A --> C
# B --> A
# B --> C
# A --> C

如果有很多盘子，我们分析一下该怎么移动，首先，我们需要把n-1个盘子移动到b中，才可以实现最简单的一步，把a中最大的盘子移动到c中，具体怎么转移到b中后面再讨论。移动最大的盘子后，a和c都可以看成是空的，接下来，把b看成是a，把a看成是b，把a中的n-1个盘子（这里的n是已经减1的n）移动到b后，又可以移动第二大的盘子。这显然是一个递归问题。

递归的出口就是n等于1，直接从a移动到c即可。

那么怎么接下来讨论，怎么把n-1个盘子移动到b，这不又是一个递归问题嘛！可以调用它自己呀，只不过需要把b看成是c，把c看成是b。所以代码如下：

def hanoi(n,a,b,c):
  #只有一个盘子，直接移动
  if n==1:
    print(a,'->',c)
  else:
    #通过c把n-1个盘子移动到b
    hanoi(n-1, a,c,b)
    #移动最大的盘子
    print(a,'->',c)
    #通过a把n-1个盘子移动到c
    hanoi(n-1, b,a,c)
hanoi(3,'A','B','C')

运行结果：

A -> C
A -> B
C -> B
A -> C
B -> A
B -> C
A -> C

转自https://www.liaoxuefeng.com/wiki/0014316089557264a6b348958f449949df42a6d3a2e542c000/001431756044276a15558a759ec43de8e30eb0ed169fb11000

更多关于Python相关内容感兴趣的读者可查看本站专题：《Python数据结构与算法教程》、《Python列表(list)操作技巧总结》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》

希望本文所述对大家Python程序设计有所帮助。

赞 (0)

相关推荐

  • python中尾递归用法实例详解

    本文实例讲述了python中尾递归用法.分享给大家供大家参考.具体分析如下: 如果一个函数中所有递归形式的调用都出现在函数的末尾,我们称这个递归函数是尾递归的.当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时,这个递归调用就是尾递归.尾递归函数的特点是在回归过程中不用做任何操作,这个特性很重要,因为大多数现代的编译器会利用这种特点自动生成优化的代码. 原理: 当编译器检测到一个函数调用是尾递归的时候,它就覆盖当前的活跃记录而不是在栈中去创建一个新的.编译器可以做到这点,因

  • Python递归实现汉诺塔算法示例

    本文实例讲述了Python递归实现汉诺塔算法.分享给大家供大家参考,具体如下: 最近面试题,面试官让我5分钟实现汉诺塔算法(已然忘记汉诺塔是啥). 痛定思痛,回来查了一下汉诺塔的题目和算法.题干与实现如下: A基座有64个盘子,大在下小在上,每次移动一个盘子,每次都需要大在下小在上,全部移动到B基座,C基座为辅助基座. # -*- coding:utf-8 -*- # 汉诺塔回溯递归实现 # 假设参数中初始杆为a,借助杆为c,阶段终止杆为b # 第一步,a状态借助b移动到c # 第二步,a移动到

  • python二分查找算法的递归实现方法

    本文实例讲述了python二分查找算法的递归实现方法.分享给大家供大家参考,具体如下: 这里先提供一段二分查找的代码: def binarySearch(alist, item): first = 0 last = len(alist)-1 found = False while first<=last and not found: midpoint = (first + last)//2 if alist[midpoint] == item: found = True else: if ite

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

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

  • Python基于递归算法实现的走迷宫问题

    本文实例讲述了Python基于递归算法实现的走迷宫问题.分享给大家供大家参考,具体如下: 什么是递归? 简单地理解就是函数调用自身的过程就称之为递归. 什么时候用到递归? 如果一个问题可以表示为更小规模的迭代运算,就可以使用递归算法. 迷宫问题:一个由0或1构成的二维数组中,假设1是可以移动到的点,0是不能移动到的点,如何从数组中间一个值为1的点出发,每一只能朝上下左右四个方向移动一个单位,当移动到二维数组的边缘,即可得到问题的解,类似的问题都可以称为迷宫问题. 在python中可以使用list

  • 使用python实现递归版汉诺塔示例(汉诺塔递归算法)

    利用python实现的汉诺塔.带有图形演示 复制代码 代码如下: from time import sleep def disp_sym(num, sym):        print(sym*num, end='') #recusiondef hanoi(a, b, c, n, tray_num): if n == 1:  move_tray(a, c)  disp(tray_num)  sleep(0.7) else:  hanoi(a, c, b, n-1, tray_num)  move

  • 详解python使用递归、尾递归、循环三种方式实现斐波那契数列

    在最开始的时候所有的斐波那契代码都是使用递归的方式来写的,递归有很多的缺点,执行效率低下,浪费资源,还有可能会造成栈溢出,而递归的程序的优点也是很明显的,就是结构层次很清晰,易于理解 可以使用循环的方式来取代递归,当然也可以使用尾递归的方式来实现. 尾递归就是从最后开始计算, 每递归一次就算出相应的结果, 也就是说, 函数调用出现在调用者函数的尾部, 因为是尾部, 所以根本没有必要去保存任何局部变量. 直接让被调用的函数返回时越过调用者, 返回到调用者的调用者去.尾递归就是把当前的运算结果(或路

  • Python中使用装饰器来优化尾递归的示例

    尾递归简介 尾递归是函数返回最后一个操作是递归调用,则该函数是尾递归. 递归是线性的比如factorial函数每一次调用都会创建一个新的栈(last-in-first-out)通过不断的压栈,来创建递归, 很容易导致栈的溢出.而尾递归则使用当前栈通过数据覆盖来优化递归函数. 阶乘函数factorial, 通过把计算值传递的方法完成了尾递归.但是python不支出编译器优化尾递归所以当递归多次的话还是会报错(学习用). eg: def factorial(n, x): if n == 0: ret

  • python 递归深度优先搜索与广度优先搜索算法模拟实现

     一.递归原理小案例分析 (1)# 概述 递归:即一个函数调用了自身,即实现了递归 凡是循环能做到的事,递归一般都能做到! (2)# 写递归的过程 1.写出临界条件 2.找出这一次和上一次关系 3.假设当前函数已经能用,调用自身计算上一次的结果,再求出本次的结果 (3)案例分析:求1+2+3+...+n的数和 # 概述 ''' 递归:即一个函数调用了自身,即实现了递归 凡是循环能做到的事,递归一般都能做到! ''' # 写递归的过程 ''' 1.写出临界条件 2.找出这一次和上一次关系 3.假设

  • python实现汉诺塔递归算法经典案例

    python实现汉诺塔递归算法经典案例

    学到递归的时候有个汉诺塔的练习,汉诺塔应该是学习计算机递归算法的经典入门案例了,所以本人觉得可以写篇博客来表达一下自己的见解.这markdown编辑器还不怎么会用,可能写的有点格式有点丑啦,各位看官多多见谅. 网上找了一张汉诺塔的图片,汉诺塔就是利用用中间的柱子把最左边的柱子上的圆盘依次从大到小叠上去,说白了就是c要跟原来的a一样 废话少说,先亮代码 def move(n, a, buffer, c): if(n == 1): print(a,"->",c) return mov

  • Python基于递归算法实现的汉诺塔与Fibonacci数列示例

    Python基于递归算法实现的汉诺塔与Fibonacci数列示例

    本文实例讲述了Python基于递归算法实现的汉诺塔与Fibonacci数列.分享给大家供大家参考,具体如下: 这里我们通过2个例子,学习python中递归的使用. 1. 找出Fibonacci数列中,下标为 n 的数(下标从0计数) Fibonacci数列的形式是这样的:0,1,1,2,3,5,8,13-- ① 使用while循环,python2代码如下: def fib(n): a,b=0,1 count=0 while count<n: a,b=b,a+b count=count+1 pri

随机推荐