python数据结构教程 Day6

2020-07-18 本文已影响0人 XaviSong

python数据结构教程 Day6

本节重点

递归定义
递归调用的实现
简单递归的应用

一、递归

在python基础教程中，我们提过递归了，但是比较粗糙地带过了，局限在递归函数的书写规范上。这里主要是讲明递归是一种解决问题的思路、思想，我们要通过递归函数掌握这种方法。

定义：

递归是一种解决问题的方法，其精髓在于将问题分解为规模更小的相同子问题，持续分解，直到问题规模小到可以用非常简单直接的方式（递归函数的出口）来解决。其算法方面的明显特征就是：在算法流程中调用自身。

示例1：递归函数求数列和

def listnum(numlist):
    '''
    利用递归的方式进行列表的求和
    '''
    if len(numlist) == 1: # 基本结束条件
        return numlist[0]
    else:
        return numlist[0] + listnum(numlist[1:]) # 状态演进，求更短数列的求和问题

示例2：将数n转换为2-16中任意进制数

def toStr(n, base):
    '''
    递归转换为任意进制的数字
    '''
    convertTable = "0123456789ABCDEF"
    if n < base:
        return convertTable[n]
    else:
        return toStr(n//base,base) + convertTable[n%base]

递归算法三定律：

必须有一个基本结束条件，否则会形成无限递归。
必须能向改变状态向基本结束条件演进（减小问题规模）
递归算法必须调用自身（解决减小了问题规模的相同问题）

二、递归调用的实现

递归和栈之间的关系：

当一个函数被调用的时候，系统会把调用时的现场数据压入到系统调用栈。每次调用，压入栈的现场数据称为栈帧。当函数返回时，要从调用栈的栈顶取得返回地址，恢复现场，弹出栈帧，按地址返回。通俗来说，递归每向基本结束条件演进一层，原本层中的现场会入栈，待递归最基本的问题解决后，再逐一出栈返回，函数逐层返回结果。

在调试递归算法程序的时候经常会碰到这样的错误：RecursionError，即递归的层数太多，系统调用栈容量有限。这时候要检查程序中是否忘记设置基本结束条件，导致无限递归或者向基本结束条件演进太慢，导致递归层数太多，调用栈溢出。

在Python内置的sys模块可以获取和调整最大递归深度。

>>>import sys
>>>sys.getrecursionlimit()
1000
>>>sys.getrecursionlimit(3000)
>>>sys.getrecursionlimit()
>>>3000

三、简单递归的应用

经典问题：汉诺塔

传说在一个印度教寺庙里，有3根柱子，其中一根套着64个由小到大的黄金盘片，僧侣们的任务就是要把这一叠黄金盘从一根柱子搬到另一根，但有两个规则：一次只能搬1个盘子，大盘子不能叠在小盘子上，求移动总共的次数。

分解为递归形式：

将盘片塔从开始柱，经由中间柱，移动到目标柱：

首先将上层N-1个盘片的盘片塔，从开始柱，经由目标柱，移动到中间柱；
然后将第N个（最大的）盘片，从开始柱，移动到目标柱；
最后将放置在中间柱的N-1个盘片的盘片塔，经由开始柱，移动到目标柱。

基本结束条件，也就是最小规模问题是：

仅移动1个盘片的问题

def moveTower(height,fromPole,withPole,toPole):
    if height >= 1:
        moveTower(height-1,fromPole,toPole,withPole)
        moveDisk(height,fromPole,toPole)
        moveTower(height-1,withPole,fromPole,toPole)

def moveDisk(disk,fromPole,toPole):
    '''
    仅移动一片
    '''
    print(f"Moving disk[{disk}] from {fromPole} to {toPole}")

上一篇：python数据结构教程 Day5

python数据结构教程 Day6