递归算法
- 简单递归实例
- 递归算法的不足
- 递归不足的改进
- python中的最大地柜深度
- 线性递归
- 二路递归
- 多重递归
- 设计递归算法
-
- 参数化递归
- 消除尾递归
递归指通过一个函数在执行过程中一次或多次调用其本身，或者通过一种数据结构在其表示中依赖于相同类型的更小结构的实例，类似于俄罗斯套娃，每个娃娃都是空心的，里面嵌套一个更小的空心娃娃，如果依次打开，到最后会有一个实心的娃娃，终止这种嵌套结构。
下面我们就来探讨一些应用了递归算法的实例。
简单递归实例 为了说明递归的机制，我们先编写一个读取文件系统的代码作为例子。首先我们先创建一个文件系统：
文章图片
下面给大家介绍一下读取文件位置和大小所要用到的python的操作系统模块：
在程序执行的过程中，os模块提供了强大的与操作系统交互的工具。这是一个丰富的函数库，但此处我们只需要以下四个函数：
- os.path.getsize(path)返回由字符串路径（如：E:\数据结构\Python版\section3）标识的文件或者目录使用的即时磁盘空间大小（单位是字节）；
- os.path.isdir(path)如果字符串路径指定的条目是一个子目录，返回True，否则返回False；
- os.listdir(path)返回一个字符串列表，它是字符串路径指定的目录中所有条目的名称。在样例文件系统中，如果参数是E:\数据结构\Python版\section3，那么返回字符串列表[‘test1.py’, ‘分层1’, ‘分层2’];
- os.path.join(path,filename)生成路径字符串和文件名字符串，并用一个适当的分隔符在两者之间分割。返回表示文件完整路径的字符串。
import os
path='E:\数据结构\Python版\section3'def disk_usage(path):
total=os.path.getsize(path) # 如果当前path是一个文件，将这个文件的大小赋值给total，否则total为0
if os.path.isdir(path):# 确定当前的路径还有可进入的文件夹
for filename in os.listdir(path): # 将当前路径中非文件夹文件标记成filename
# 第一次进入该函数时，os.listdir(path)内容为['test1.py', '分层1', '分层2']
childpath=os.path.join(path,filename) # childpath标记当前filename文件(夹)所在的完整路径
# print(childpath)
total+=disk_usage(childpath) # 递归调用
print('{0:<7d}'.format(total),path) # 输出total内容后在7列处继续输出path内容
return totalprint(disk_usage(path))
让我们看看输出的结果：
文章图片
下面我们简要分析一下这段代码：
文章图片
如果大家有什么不理解的地方，可以按照这个思路分析下去，还不理解的可以将第十行代码取消注释，然后debug一下，实在不理解的小伙伴也没关系，后面还有更简单的递归实例分析。
递归算法的不足 递归虽然是一种非常强大的工具，它可以以比较简洁的代码实现相对复杂的功能，有些时候递归实现是很难被其他算法代替的。但很多情况下递归并不能被合理应用。一个糟糕的递归实现可能会导致严重的效率低下。下面我们用几个例子来讨论错用递归导致的效率问题以及如何避免类似问题的策略。
- 元素唯一性测试函数
下面我们用递归算法写一个函数，用以判断列表元素是否有重复：
def unique(series,start,stop): # series列表没有重复元素返回True if start>=stop-1:return True elif not unique(series,start,stop-1):return False elif not unique(series,start+1,stop):return False else:return series[start]!=series[stop-1]S=[1,3,2] print(unique(S,0,len(S))) # 结果为：True
这个结果代表着元素没有重复。这样的代码初看起来确实让人耳目一新，但是下面我们来具体分析一下它究竟是如何工作的：
文章图片
很惊讶，一个仅需要比较三次的算法竟然反复七次进入递归。仔细观察李子就不难发现，如果我们传入大小为n的列表，那么对unique函数的单一调用会导致对两个列表长度为（n-1）的调用，而这两个调用又会分别产生两个大小为（n-2）的调用，以此类推，最终的调用次数可以表示为：
文章图片
很难想象一个比较次数仅仅为Cn2的算法它的时间复杂程度居然是O(2n)，事实上，这样的时间消耗远大于使用双重循环逐个元素的比较。
2. 低效的斐波那契数列
def fib(n): if n<=1: return n else: return fib(n-2)+fib(n-1)print(fib(6)) # 输出为：8
下面我们照例分析一下这个算法消耗的时间：
文章图片
可以发现，我们需要进行了12次运算，并且很多都是重复的操作，比如我们使用递归运算了2次fib(4)，2次fib(3)等，这导致了算力和时间的极大浪费。思考一下，如果我们调用的fib(n)，每次都产生两个fib(n-2)的递归，那么花费的时间大概是2n/2，如果每次都产生两个fib(n-1)，则花费的时间大概是2n，而这个算法中，每次递归调用产生的是一个fib(n-2)和一个fib(n-1)，也就是说这个算法花费的时间在2n/2到2n之间。因此它的时间复杂程度为O(2n)。
3.计算幂的递归算法
下面的例子我们来介绍一个计算xn的算法。首先，我们给出一个简单的递归定义：
文章图片
根据这个定义，我们给出代码：
def power(x,n): if n==0: return 1 else: return x*power(x,n-1)print(power(2,5)) # 输出为：32
这也是一个很简单的算法，时间复杂程度为O(n)。但是这也不是最好的算法，我们可以加以改进减少运行时间。
递归不足的改进
- 1.元素唯一性测试算法改进
上述递归测试元素唯一性的算法，因为不考虑进入后续递归地完整走完一层，最多需要调用两次自己，并且使用递归实现，又很难从算法层面进行改进，因此我们可以改为循环算法； - 2.递归产生斐波那契数列算法改进
和上个算法类似，这个算法也是完整执行完一层递归，至多要调用两次自己本身，并且潜藏着大量重复的运算。改进这种算法需要我们减少调用自身的次数，并且最好消除掉重复的运算。改进如下：def fib(n): if n<=1: return(n,0) else: a,b=fib(n-1) return a+b,a # 一次性返回两个数print(fib(6)) # 输出为：(8,5)
就效率而言，这个算法比之前的好了很多。由于完整走完一层递归需要调用一次自己，因此这个算法的时间复杂程度为O(n)。 - 3.计算幂递归算法改进
我们采用平方技术重新定义xn。用k=n//2表示递归层数，我们只需要用x2*k（或x2*k+1）计算：当n/2是整数时，用x2*k计算即可，如果n/2有效数，则需要用x2*k+1计算，因此得出的递归定义如下：
文章图片
使用这种算法写出的代码如下：def power(x,n): if n==0: return 1 else: partial=power(x,n//2) result=partial*partial if n%2==1: result*=x return resultprint(power(2,11)) # 输出为：2048
这样一来，我们的递归次数就会有明显的减少，每一次都会把当前的标记递归次数的n减半，因此时间复杂程度就变成了O(logn)。关于递归算法的改进，后续还会有一些经验性的总结，大家先不必着急。
def err(n):
return err(n)
err(1)
运行结果如下：
文章图片
出现这样的结果，就是因为递归的深度超过了最大的设定。所谓递归深度，就是递归函数自己能够调用自己的最多次数。如果递归函数在某些位置出现只进入不退出递归的现象，那么在达到1000次（默认的设定次数）调用的时候，系统会抛出一个RecursionError，即代表超过最大的递归深度。因为我们大多数的合法递归调用，1000层合法的嵌套函数的限制是足够的，有了这样的设定我们可以让计算机资源不会因为错误的递归而被一下子消耗殆尽。然而依然有一些合法情况会超过这个限制：
def demo(n): # 返回递归深度
if n>0:
return demo(n-1)+1
else:
return 0print(demo(120))
print(demo(1020))
结果会显示成：
文章图片
从第一个结果可以看出，这个算法是合法的。然而当我们增大n，人为制造超过最大的递归深度的情况，计算机同样会报错。
幸运的是，python解释器可以动态重置，以更改默认的递归限制。这需要通过sys模块来实现，示例如下：
import sys
# old=sys.getrecursionlimit() # 可以获取当前的递归深度
sys.setrecursionlimit(1050) # 更改最大的递归深度为1050def demo(n): # 返回递归深度
if n>0:
return demo(n-1)+1
else:
return 0print(demo(1020))
# 输出为：1020
线性递归 以上，我们已经了解了一些递归的基础知识，下面我们继续补充一些常识。首先说线性递归，如果一个递归函数被设计成使得所述主体的每次调用至多执行一个新的递归调用，这样的递归就是线性递归。上述例子中，改进的斐波那契数列生成算法，两种求幂的算法都是线性递归。需要注意的是，如果执行的函数里有多个调用自己的语句，但是具体执行时每次却只能进入一个调用，这样的递归也叫线性递归：
def find(data,target,low,high):
if low>high:return False
else:
mid=(low+high)//2
if target==data[mid]:return True
elif target上述算法一定要注意一点，在进入下一层递归之前一定要调整好传入的参数是mid+1还是mid-1或是mid，弄不对的话可能会引发无限递归。通常情况下时间复杂程度还是较为令人满意的。
二路递归 二路递归听起来很高端，实际上和线性递归的定义非常类似：如果一个递归函数被设计成使得所述主体的每次调用至多执行两个新的递归调用，这样的递归就是二路递归。一个典型的二路递归的例子就是改进前的斐波那契数列生成算法。当然，在这里再给大家介绍一个二路递归的例子：动态规划求解背包问题。大家可以通过视频了解基本的算法思路，这里直接给到大家算法的代码实现：
import pandas as pd
import copy
class Knapsack:
__compare=[]
def __init__(self,size=6,mes = {3: 25,2: 20,1: 15, 4: 40, 5: 50}):# mes字典的键存储重量，值存储价值
self.size = size+1
self.mes = mes
self.res =[[0] * self.size for i in range(len(self.mes.keys())+1)] # 列表格存储内容
def __OptimalSolution(self,maxnumber,nowsize,add_val=0):
if nowsize < min(self.mes.keys()) or maxnumber == []: # 当前可选物品为空时结束
self.__compare.append(add_val)next = copy.deepcopy(maxnumber)for i in maxnumber: # 当前物品编号，对应mes字典下标
if list(self.mes.keys())[i-1]<=nowsize: # 如果当前物品重量小于背包容量
next.remove(i)# 更新可选标签
self.__OptimalSolution(next, nowsize, add_val) # 不装并删掉对应物品add_val+=list(self.mes.values())[i-1]
nowsize-=list(self.mes.keys())[i-1]
self.__OptimalSolution(next, nowsize, add_val) # 装
else:
next.remove(i)# 更新可选标签
self.__OptimalSolution(next, nowsize, add_val) # 不装def Show_Knapsack(self):
s=[]
for i in range(1,self.size): # 背包容量
for j in range(1,len(list(self.mes.keys()))+1): # 物品种类
s.append(j)
self.__OptimalSolution(s, i)
(self.res[j])[i] = max(self.__compare)
self.__compare.clear()
s.clear()
df = pd.DataFrame(data=https://www.it610.com/article/self.res,index=[0,1,2,3,4,5])
return dftest=Knapsack()
print(test.Show_Knapsack())输出的结果如下：
文章图片
这也是一个典型的二路递归，当然其实还可以有更节省时间的改进方法，大家可以根据以下内容进行代码上的调整，这里不做赘述。
多重递归 由二路递归的定义可推知，一个函数在执行过程中多于两次的调用自身的情况即可被定义为多重递归。实际上，最开始给大家举例用的读取文件系统的代码，就是一种多重递归，只是由于设计的文件系统比较简单，看起来并没有多重递归的复杂感。
设计递归算法 一般来说，使用递归算法通常具有以下的形式：
- 1.对基本情况的测试。首先测试一组基本情况（至少应该有一个）。这些基本情况应该都是有定义的，以便每个可能的递归调用链最终会达到一中基本情况，并且每个基本情况的处理不需要使用递归。
- 2.测试递归。如果此时调用函数不是一种基本情况，则执行一个或多个递归调用。这个递归步骤可能包括一个测试，该测试决定执行哪几种可能的递归调用。我们应该定义每个可能的递归调用，以便使调用向一种基本情况靠近。
消除尾递归 算法设计的递归方法的主要优点是，它使我们能够简洁地利用重复结构呈现诸多问题。通过使算法描述以递归的方式利用重复结构，我们经常可以避开复杂的案例分析和嵌套循环。这种方法会得出可读性更强的算法描述，而且十分有效。但是，递归的可用性要基于合适的成本。特别是python的解释器必须保持跟踪每个嵌套调用的状态活动记录。在某些计算机空间十分紧张或珍贵的情况下，能够把递归算法改写成非递归形式是很有必要的。
尾递归是一种著名的递归形式，它指的是当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分。一个典型的尾递归实例就是我们线性递归中介绍的二分法查找递归算法，在执行某一个递归调用之后，该层递归不会有其他的任何多余的运算操作。而典型的非尾递归就像未优化的求幂算法，因为return语句中的递归调用不是函数体中最后执行的语句，我们假设power(x,n-1)的值为y，那么第一层递归最后执行的语句实际上是return x*y。
尾递归都是线性递归，并且尾大多数现代的编译器会利用尾递归的特点自动生成优化的代码。因为通过重新分配现存参数的值以及用新的参数来代替下一个递归的结果，就可以将递归简化成循环，比如我们这样的循环就可以代替为改进的计算幂的递归算法：
def power(x,n):
res=1
for i in range(n+1,1,-1):
res*=x
return res
【数据结构|递归算法简介】其实，就算是普通的线性递归，也都可以比较容易地改写成非递归的算法，或许这种改写不会降低时间复杂度，但是却可以较大幅度降低空间复杂程度。
关于递归的讲述，到这里就告一段落了。本节讲述了关于递归的具体分析，也给大家看了线性递归、二路递归、多重递归的使用案例。至此，我们已经完成了数据结构的入门了，下节开始，我们会继续学习基于数组的序列，大家一起加油吧~
推荐阅读
- 数据结构|面对对象编程细则（三）
- 数据结构|浅谈算法分析
- Windows核心编程|Windows提取环境变量
- 数据分析|机器学习基础篇（十）——聚类
- python|PyTorch入门,帮你构建自己的神经网络模型
- c语言|学习了循环碰到了编写计算n的阶乘的题目，由此引发了一系列问题，包括一些初学者常见的坑，以及如何简化代码
- 算法|基于MATLAB的图像去噪与边缘检测技术
- python全栈开发|进军Python全栈开发--14.Python中的数据结构与算法
- CS224W|CS224W-图神经网络 笔记4.3（Community Structure in Networks - 网络中重叠社区的挖掘——BigCLAM 算法）