【递归】递归树与函数记忆化

原创 老姚 随笔 递归,俺跟你拼了 431阅读 2017-05-12 12:18:15 举报

递归操作是把问题逐渐缩小。
比如斐波那契数列,其递归公式是:
[quote]f(n) = f(n-1) + f(n-2)
f(0) = f(1) = 1[/quote]
如果我要计算f(5),我需要计算f(4)和f(3),
而计算f(4)时,我又需要计算f(3)和f(2)。
我们用递归树来表示计算过程,如图。

递归树
我们发现f(3)计算了2次,f(2)计算了3次。
这还只是计算f(5)的情形(用5来举例,只因图好画),
如果是要计算f(100)呢,其中f(2)不知会计算多少次。
也就是说递归时,把问题规模减小时,可能会出现很多重复的子问题。
我们希望减少无用功,此时可以使用缓存来做。
比如原先的递归函数
javascript 代码

可以改成:
javascript 代码

有了缓存确实方便,但不能每次为了缓存,都要这么写吧。
因此一个概念横空出世,函数记忆化。
javascript 代码

memoize是对参数func进行了包装,优先调用缓存。
缓存里没有时,运行func,并把结果缓存起来。缓存对象的键是参数以逗号相连接的字符串。
比如,3个参数时sum(1, 2, 3),key会变成"1,2,3"。可以如下测试:
javascript 代码

当然我们可以允许key的形式由用户定义:
javascript 代码

最后要说明,函数记忆化,是函数式编程中的概念。
函数记忆不一定只针对递归,但要求函数是纯的。
即输入确定,输出就确定,不能对程序状态搞下小动作。
因为内部利用了缓存,并不是每次都会运行函数。

上述代码改编于underscore.js的memoize方法。

本文完。

《递归系列目录》

看到此处我们该想到,陆游诗人对前端界做出的最大贡献:
纸上得来终觉浅,绝知此事要躬行。

评论 ( 2 )
最新评论
ai782041 2018-01-18 15:24:34 2F

这篇不太理解
,先收藏

ququ 2017-05-12 15:45:42 1F

满满的新思想