算法学习递归算法

应用条件

本博客在学习北京大学陈斌老师《数据结构与算法》MOOC课程中总结反思形成。

递归是一种一种优雅的理解问题的方式&＃xff0c;也是我曾经比较学习过程中比较困惑的一个地方。

理解递归&＃xff0c;不妨牢记递归应用的三要素&＃xff1a;

1. 基本结束条件

2. 缩小问题规模

3. 调用自身

递归的优点和缺点也及其显著&＃xff0c;优点&＃xff1a;肯定能够寻找到最优解&＃xff1b;缺点&＃xff1a;低效&＃xff08;重复计算太多&＃xff09;

案例分析

本博客分析一个经典的应用场景“找零问题”&＃xff0c;分别给出自己的解法和陈斌老师的解法&＃xff0c;以帮助分析和理解递归

问题描述

某货币体系中找零兑换的最少货币数问题

解法分享

分析问题&＃xff0c;牢牢从三要素出发。

基本结束条件&＃xff1a;找零正好是货币体系中的一张面额&＃xff0c;返回1&＃xff1b;

缩小问题规模和调用自身&＃xff1a;找零减去某张面额后&＃xff0c;求兑换硬币最少数量&＃xff08;递归调用自身&＃xff09;&＃xff1b;

本人解法如下&＃xff1a;

def OddChange(valuelist, change):if change in valuelist:return 1elif change >&＃61; 25:return min(1 &＃43; OddChange(valuelist, change - 1), 1 &＃43; OddChange(valuelist, change - 5),1 &＃43; OddChange(valuelist, change - 10), 1 &＃43; OddChange(valuelist, change - 25))elif change >&＃61; 10:return min(1 &＃43; OddChange(valuelist, change - 1), 1 &＃43; OddChange(valuelist, change - 5),1 &＃43; OddChange(valuelist, change - 10))elif change >&＃61; 5:return min(1 &＃43; OddChange(valuelist, change - 1), 1 &＃43; OddChange(valuelist, change - 5))else:return 1 &＃43; OddChange(valuelist, change - 1)


陈斌老师解法如下&＃xff1a;

def recMC(coinValueList, change):minCoins &＃61; change# 最小规模&＃xff0c;直接返回if change in coinValueList:return 1else:for i in [c for c in coinValueList if c <&＃61; change]:# 减小规模&＃xff0c;调用自身numCoins &＃61; 1 &＃43; recMC(coinValueList, change - i)if numCoins

使用timeit分析时间开销如下&＃xff1a;

• 可以很明显发现两者解法的时间开销是指数增长的速度&＃xff0c;这印证了前文**低效&＃xff08;重复计算太多&＃xff09;**的观点
• 老师的写法更高雅&＃xff0c;可以学习&＃xff0c;但是for 循环一定程度上降低了速度
• 以求解63找零为例&＃xff0c;总的递归次数我计算出来是67716925次数

解法改进

这部分我觉得是让我升华了的地方&＃xff0c;前面的时间开销让我觉得递归算法是一个非常不靠谱的算法&＃xff0c;毕竟一个63的找零就需要花费30s&＃43;&＃xff0c;这种开销难以承受。但是&＃xff0c;在“空间换时间”思想的知道下&＃xff0c;这个算法瞬间可以求解。

在递归调用过程中已经得到的最优解被记录下来。在递归调用之前&＃xff0c;先查找表中是否已有部分找零的最优解。如果有&＃xff0c;直接返回最优解而不进行递归调用&＃xff1b;如果没有&＃xff0c;才进行递归调用。

在实现方面&＃xff0c;我的第一反应是使用词典进行保存&＃xff1a;

def OddChangeOp(valuelist, change,resultdic):if change in valuelist:resultdic[str(change)] &＃61; 1return 1elif str(change) in resultdic:return resultdic[str(change)]elif change >&＃61; 25:resultdic[str(change)] &＃61; min(1 &＃43; OddChangeOp(valuelist, change - 1,resultdic), 1 &＃43; OddChangeOp(valuelist, change - 5,resultdic),1 &＃43; OddChangeOp(valuelist, change - 10,resultdic), 1 &＃43; OddChangeOp(valuelist, change - 25,resultdic))return resultdic[str(change)]elif change >&＃61; 10:resultdic[str(change)] &＃61; min(1 &＃43; OddChangeOp(valuelist, change - 1,resultdic), 1 &＃43; OddChangeOp(valuelist, change - 5,resultdic),1 &＃43; OddChangeOp(valuelist, change - 10,resultdic))return resultdic[str(change)]elif change >&＃61; 5:resultdic[str(change)] &＃61; min(1 &＃43; OddChangeOp(valuelist, change - 1,resultdic), 1 &＃43; OddChangeOp(valuelist, change - 5,resultdic))return resultdic[str(change)]else:resultdic[str(change)] &＃61; 1 &＃43; OddChangeOp(valuelist, change - 1,resultdic)return resultdic[str(change)]


但是&＃xff0c;老师的解法更加有趣&＃xff0c;直接使用列表完成了同样的工作&＃xff0c;我使用词典的目的是希望构建映射关系&＃xff0c;但其实列表本身也是有映射关系的&＃xff0c;那就是列表的下标和列表的值

def recDC(coinValuelist, change, knowResults):minCoins &＃61; change# 递归基本结束条件&＃xff0c;记录最优解if change in coinValuelist:knowResults[change] &＃61; 1return 1# 查表成功&＃xff0c;直接使用最优解elif knowResults[change] > 0:return knowResults[change]else:for i in [c for c in coinValuelist if c <&＃61; change]:numCoins &＃61; 1 &＃43; recDC(coinValuelist, change - i, knowResults)if numCoins

对比时间开销&＃xff0c;可以发现&＃xff0c;解法几乎是瞬间完成的&＃xff0c;下图展示的是调用10000次显示的耗时&＃xff0c;而且老师直接使用列表构造映射存储最优解的方案耗时比我的解法少的多。

同时&＃xff0c;算法近似成为线性的时间的开销&＃xff0c;内存开销也不算特别高&＃xff0c;真正意义的可用算法&＃xff0c;真的是非常神奇&＃xff01;&＃xff01;

递归次数的计算

最后&＃xff0c;分享一个有趣的事情&＃xff0c;就是求解递归算法的迭代次数&＃xff0c;这个在实现上有三种方法可以选择

• 全局变量

• 函数内置属性

• 装饰器

其中&＃xff0c;装饰器的方法简直太优雅了&＃xff0c;这当然也是因为我本人对于python高阶语法的欠缺

这里mark记录一下

class Counter(object) :def __init__(self, fun) :self._fun &＃61; funself.counter&＃61;0def __call__(self,*args, **kwargs) :self.counter &＃43;&＃61; 1return self._fun(*args, **kwargs)&＃64;Counter
def OddChange(valuelist, change):


写在最后&＃xff0c;迭代算法在引入了储存机制后&＃xff0c;我瞬间感觉简直无敌&＃xff01;算法的魅力无穷&＃xff0c;绝不是简单看别人轮子所能体会的。