- Python3从入门到实战
- 董洪伟
- 1367字
- 2020-08-27 19:57:35
3.4 递归函数（调用自身的函数）
3.4.1 递归函数的使用方法
1．什么是递归函数
由上述讲解可知，一个函数可以在其内部调用其他函数。如果一个函数在其内部存在调用该函数自身的语句，就称为递归函数。
递归是一种将任务分解的解决问题的方法，一个大的问题如果能够分解成和它类似的子问题，且子问题的解决方法和大问题一样，只不过问题的规模有所区别而已，则这种情况就可以采用递归的方法来解决这个问题。
例如，求一个n的阶乘问题，可以通过n和n-1的阶乘相乘而得到，即问题规模为n的阶乘问题分解成了规模更小的n-1的阶乘问题，即n!=n×（n-1）!
因此，可以编写下面的代码来求n阶乘：
def fact（n）:
if n==1: #如果n等于1，就直接返回值1
return 1
return n ＊ fact（n -1） #如果n大于1，就是n和fact（n-1）的乘积
fact（4） #输出： 24
输出：
24
当n=1时，就不需要再分解了，即不需要再递归为更小的子问题了。这种不需要再分解的问题，即“规模是n=1的阶乘问题”称为“基问题”。
递归是一个嵌套的过程。例如，fact（4）的递归计算过程如下：
===> fact（4） ===> 4 ＊ fact（3） ===> 4 ＊（3 ＊ fact（2）） ===> 4 ＊（3 ＊（2 ＊ fact（1））） ===> 4 ＊（3 ＊（2 ＊ 1）） ===> 4 ＊（3 ＊ 2） ===> 4 ＊ 6 ===> 24
2．斐波那契数列
斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称“兔子数列”，指的是数列{f（n）|n=0,1,2, …}。例如：
f（0）=1, f（1）=1，当n>=2时，f（n）=f（n-1）+f（n-2）
可编写如下的递归函数：
def fib（n）:
if n<=2 :
return 1
else:
return fib（n-1）+fib（n-2）
for i in range（8）:
print（fib（i）, end=', '）
输出：
1,1,1,2,3,5,8,13,
3．最大公约数
最大公约数也是一个递归问题：
可编写如下的递归函数：
def gcd（m, n）:
if n==0 :
return m
else:
return gcd（n, m%n）
print（gcd（72,27））
print（gcd（24,36））
输出：
9 12
3.4.2 实战：二分查找的递归实现
本书第2章中的二分查找问题可以看作一个递归问题，在非空的原序列上的查找问题，被分解为三个子问题：（1）和中间的元素的直接比较问题；（2）左区间上的查找问题；（3）右区间上的查找问题。可以编写基于递归的二分查找程序：
def binarySearch（alist, value）:
if len（alist）==0: #（0）空序列
return -1
else:
Middle=len（alist）//2
if alist[Middle]==value: #（1）中间元素直接比较
return Middle
else:
if value<alist[Middle]:
return binarySearch（alist[:Middle], value）#（2）左区间查找
else:
return binarySearch（alist[Middle+1:], value）#（3）右区间查找
可以用下列代码测试这个递归二分查找函数：
testlist=[5,7,12,25,34,37,43,46,58,80,82,105] print（binarySearch（testlist, 25）） print（binarySearch（testlist, 13））
输出：3-1
3.4.3 实战：汉诺塔问题
汉诺塔问题（如图3-2所示）是由法国数学家爱德华·卢卡斯在1883年发明的（他的灵感来自一个印度教传说）。假设有三根柱子a、b、c，其中a柱子上有n个（n > 1）盘子，盘的尺寸从下到上依次变小。现在要求将盘子全部移到c柱子，每次只能移动一个盘子，且小盘必须在大盘之上，当然，盘子只能放在三个柱子之一上。
图3-2 汉诺塔问题
假设采用蛮力尝试法，处于一个柱子上的盘子最多有两个选择（移动到另外两个柱子之一）, n个盘子都这样尝试，至少需要n次尝试，因此至少需要移动2n-1次，但由于每个盘子不可能只尝试一次，所以总的次数会远远大于这个数字。
如果采用“分而治之”的解决问题方法，就可以将“n个盘子的移动（从a柱子借助b柱子移到c柱子）”分解为如下子问题（如图3-3所示）：
图3-3 汉诺塔的递归分解
●（上面的）n-1个盘子的移动（从a柱子借助c柱子移到b柱子）。
● 最大盘子的移动：直接从a柱子移到c柱子。
● n-1个盘子的移动（从b柱子借助a柱子移到c柱子）。
当然，对于n=1的“基问题”，不需要分解，直接移动即可。因此，可以编写下列代码：
#一个盘子：直接移动
def moveDisk（i, x, y）:
print（"moving disk", i, " from", x, "to", y）
#盘子数，起始柱，中转柱，目标柱
def move（n, a, b, c）:
if n>=1:
move（n-1, a, c , b） #n-1个盘子从a柱子借助c柱子移到b柱子
moveDisk（n, a, c） #第n号盘子直接从a柱子移到c柱子
move（n-1, b, a, c） #n-1个盘子从b柱子借助a柱子移到c柱子
下面的代码对n=3调用这个move（）函数：
move（3, 'A', 'B', 'C'）
输出直接移动的步骤：
moving disk 1 from a to c moving disk 2 from a to b moving disk 1 from c to b moving disk 3 from a to c moving disk 1 from b to a moving disk 2 from b to c moving disk 1 from a to c
3.4.4 实战：快速排序算法
对一组数进行排序的快速排序是一个递归过程。首先在这组数中任意选取一个数作为“基准”，将这组数分为两部分，其中一部分的所有数不大于基准元素，而另外一部分的所有数不小于基准元素。例如，有一组数：
34,2,89,47,29,13
假设任意选取一个数34作为基准元素，然后将这组数按照34分为两部分：
2,29,13, [34],89,47
将一个序列按基准元素34一分为二，其中，左半部分的数都小于等于34，右边部分的都大于等于34，这个过程称为“一次划分”，对分割好的两部分重复上述过程，如此进行下去，直到每个部分的长度不超过1。
因此，整个快速排序算法（假设叫作qsort）分为三个步骤：首先一次划分；再对左、右部分分别调用这个快速排序算法（qsort）。可以编写如下代码：
#对[start, end]区间的元素进行快速排序
def qsort（arr, start , end）:
if start<end:
pivot=partition（arr, start, end）#将[start, end]之间的序列一次划分为两部分
#pivot是基准的位置
qsort（arr, start, pivot-1） #对[start, pivot-1]之间的序列调用qsort快速排序过程
qsort（arr, pivot+1, end） #对[pivot+1, end]之间的序列调用qsort快速排序过程
递归函数qsort（）里调用了对一个区间完成一次划分的函数partition（），其过程如图3-4所示。假设第一个元素是基准元素，则可以使用首尾两个指示器，当右指示器指向的元素大于等于基准元素时，则该指示器向左移动，否则就停止；当左指示器指向的元素小于等于基准元素时，则该指示器向右移动，否则就停止。当两个指示器都停止时，左、右指示器指向的元素都分别大于或小于基准元素，这时就交换它们指向的元素值，再继续这个“两个指示器向内靠拢”的过程。直到两个指示器相遇，这个位置就是基准元素的目标位置。
图3-4 “一次划分”过程
函数partition（）代码如下：
def partition（alist, start, end）:
pivotvalue=alist[start] #假设选择start的元素为基准元素，并暂存到pivotvalue中
L=start+1 #左指示器指向区间左侧
R=end #右指示器指向区间右侧
done=False
while not done:
while L <=R and alist[L] <=pivotvalue:
L=L + 1
while alist[R] >=pivotvalue and R >=L:
R=R -1
if R < L:
done=True
else:
alist[L], alist[R]=alist[R], alist[L]
#temp=alist[L]
#alist[L]=alist[R]
#alist[R]=temp
#R<L时的位置R就是基准元素的目标位置
alist[R], alist[start]=alist[start], alist[R] #交换基准元素和R位置的元素
return R #返回基准元素的位置
调用对一个区间的快速排序递归函数qsort（），可对一个序列进行快速排序。例如：
def quickSort（alist）:
qsort（alist,0, len（alist）-1） #调用递归函数qsort对[0, len-1]区间进行快速排序
alist=[49,38,27,97,76,13,27,49]
quickSort（alist）
print（alist）
输出：
[13, 27, 27, 38, 49, 49, 76, 97]
如果不追求效率，还可以采用一种取巧的简单方法：遍历这个数组列表，将其中小于基准元素的数放入一个新的列表，而大于等于基准元素的数则放入另外一个新的列表，然后将这两个新列表的快速排序的结果合并起来。例如：
def quicksort（arr）:
if len（arr）<=1: #如果输入序列长度小于等于1，则直接返回
return arr
pivot=arr[len（arr）// 2] #任意选择一个元素作为基准元素
#将原序列一分为二
left=[x for x in arr if x < pivot] #left是小于基准元素组成的子序列
middle=[x for x in arr if x==pivot] #middle是等于基准元素组成的子序列
right=[x for x in arr if x > pivot] #right是大于基准元素组成的子序列
return quicksort（left）+ middle + quicksort（right） #对left、right重复上述过程
print（quicksort（[49,38,27,97,76,13,27,49]））
输出：
[13, 27, 27, 38, 49, 49, 76, 97]
因为这个算法需要移动函数，所以这个算法的效率比较低，并且还要消耗更多的空间。
3.4.5 实战：迷宫问题
给定一个迷宫，指明迷宫的起点和终点，找出从起点出发到终点的有效路径，这就是迷宫问题（maze problem），如图3-5所示。
图3-5 迷宫问题
迷宫可以用二维数组来存储表示。例如，0表示通路，1表示障碍，2表示终点。坐标以行和列表示，均从0开始。假设给定起点（0, 0）和终点（5, 5），迷宫表示如下：
maze=[[0, 0, 0, 0, 0, 1],
[1, 1, 0, 0, 0, 1],
[0, 0, 0, 1, 0, 0],
[0, 1, 1, 0, 0, 1],
[0, 1, 0, 0, 1, 0],
[0, 1, 0, 0, 0, 2]]
迷宫求解问题可以描述为一个递归过程。
对于一个当前位置，判断该位置是否为终点（2）、墙（1）、已经走过（3）。如果不是上述情况，则说明该位置可通但未走过（0）。可从该位置走向其四邻（上、下、左、右四个位置）。对于每个邻接点，重复这个过程。例如：
def go_maze（x, y）:
#该位置是否为终点（2）、墙（1）、已经走过（3）
if maze[x][y]==2:
print（’到达终点：', x, ", ", y）
return True
elif maze[x][y]==1:
#print（’墙：', x, ", ", y）
return False
elif maze[x][y] >=3:
#print（’已经访问过：', x, ", ", y）
return False
#从该位置向四邻探索
print（’访问 %d, %d' %（x, y））
maze[x][y]=3 #标记该位置已经访问过
# 向4邻探索
if（（x < len（maze）-1 and go_maze（x+1, y））
or（y > 0 and go_maze（x, y-1））
or（x > 0 and go_maze（x-1, y））
or（y < len（maze）-1 and go_maze（x, y+1）））:
return True
maze[x][y]=4 #此路也不通
return False
go_maze（0, 0）
print（＊maze, sep='\n'）
输出：
访问 0,0 访问 0,1 访问 0,2 访问 1,2 访问 2,2 访问 2,1 访问 2,0 访问 3,0 访问 4,0 访问 5,0 访问 1,3 访问 0,3 访问 0,4 访问 1,4 访问 2,4 访问 3,4 访问 3,3 访问 4,3 访问 5,3 访问 5,2 访问 4,2 访问 5,4 到达终点： 5 , 5 [[3, 3, 3, 3, 3, 1], [1, 1, 3, 3, 3, 1], [4, 4, 4, 1, 3, 0], [4, 1, 1, 3, 3, 1], [4, 1, 4, 3, 1, 0], [4, 1, 4, 3, 3, 2]]
思考：打印的位置还包括回退的位置，如何打印一个没有回退的路径？