递归系列——递归树与函数记忆化

老翟笔记今日分享的是:递归系列——递归树与函数记忆化

     递归操作是把问题逐渐缩小。      比如斐波那契数列，其递归公式是： f(n) = f(n-1) + f(n-2) f(0) = f(1) = 1    也就是说递归时，把问题规模减小时，可能会出现很多重复的子问题。f(0)和f(1)会被重复计算多次。    我们希望减少无用功，此时可以使用缓存来做。 例如下面的demo： function f(n) {if (n < 2) return 1;return f(n - 1) + f(n - 2); } console.log(f(10)); 输出如下： console.log: 89； 可以使用缓存改成： function f(n) {var cache = f.cache = f.cache || {};if (n in cache) return cache[n];if (n < 2) return cache[n] = 1;return cache[n] = f(n - 1) + f(n - 2); } console.log(f(10)); console.log(f.cache); 输出如下： console.log: 89 console.log: {0: 11: 12: 23: 34: 55: 86: 137: 218: 349: 5510: 89 } 使用函数记忆化： 代码如下： function memorize(func){var fn = function(){var cache = fn.cache;var key = [].join.call(arguments);if (!(key in cache)) return cache[key] = func.apply(this, arguments);return cache[key];}fn.cache = {};return fn;}var fn = memorize(function(n){if (n < 2) return 1;return fn(n-1) + fn(n-2);});console.log(fn(10)); // 89console.log(fn.cache); //{0: 1, 1: 1, 2: 2, 3: 3, 4: 5, 5: 8, 6: 13, 7: 21, 8: 34, 9: 55, 10: 89} memoize是对参数func进行了包装，优先调用缓存。缓存里没有时，运行func，并把结果缓存起来。缓存对象的键是参数以逗号相连接的字符串。 比如，3个参数时sum(1, 2, 3)，key会变成"1,2,3"。可以如下测试： var sum = memorize(function(a,b,c){return a + b + c;})console.log(sum(1,2,3)); // 6console.log(sum.cache); // {1,2,3: 6} 函数记忆化，是函数式编程中的概念。函数记忆不一定只针对递归，但要求函数是纯的。即输入确定，输出就确定，不能对程序状态搞下小动作。因为内部利用了缓存，并不是每次都会运行函数。   转载于:https://www.cnblogs.com/xuzhudong/p/7463003.html

本文结束，感谢您的阅读和支持，希望以上内容能给你带来帮助。本文章来自网络，由老翟笔记小编团队整理发布。