递归优化

先来看下斐波那契数列的递推公式： f[0]=1, f[1]=1, f[n]=f[n-1] + f[n-2]（n>=2且n是整数）。
很容易写出下列代码：

const fabo = (n) => {
if (n === 0 || n === 1) return 1;
return fabo(n-2) + fabo(n-1);
}

稍微分析一下，就可以知道，这段代码存在大量的重复计算，比如计算f[5]，就要计算f[4]、f[3]、f[2]、f[1]、f[0]，计算f[4]就要计算f[3]、f[2]、f[1]、f[0]。

怎么消除重复计算呢？首先想到的是存储计算过的值，相当于备忘录：

	const fabo
= (() => {
const cache = [1, 1]; // 初始化第0和第1项的值
return func(n) => {
if (cache[n]) return cache[n];
cache[n] = func(n - 1) + func(n-2);
return cache[n];
}
})();

若不存储计算过的值，怎么才能减少重复计算呢？在erlang里提到过一种“尾递归”的方式，总的来说就是把上一步计算过的值通过参数传入下一步的计算。我们可以这样：

const fabo = (n) => {
let cur = 2;
let lastSec = 1;
let lastFirst = 1;
const func = () => {
if (n ===0 || n ===1) return 1;
if (n === cur) return lastSec + lastFirst;
cur++;
let tmp = lastSec;
lastSec = lastFirst;
lastFirst += tmp;
return func();
}
return func();
}

稍微改变了下计算顺序，从0 --> n计算，前面两步的计算结果直接传入到下一次的计算中，这样就不需要反复的计算。
于是，我们可以继续优化备忘录的方式：

const fabo
= (() => {
const cache = [1, 1]; // 初始化第0和第1项的值
let
cur = 2;
return function func(n){
if (cache[n]) return cache[n];
cache[cur] = cache[cur - 2] + cache[cur - 1];
if (n <= cur) return cache[n];
cur++;
return func(n);
}
})();

当然对于递归来说，可能会有更好的优化方式比如，上面的斐波那契数列，我们可以直接用它的通项公式计算：

const fabo = (n) => {
return Math.round(1/(5 ** 0.5) * (((1+5**0.5)* 0.5) ** n - ((1-5**0.5)* 0.5) ** n));
}

对于某些递归来说，可以很容易地改为非递归的形式，还是拿斐波那契数列来说：

const fabo = (n) => {
if (n === 0 || n===1)return 1;
let lastFirst = 1;
let lastSec = 1;
for (let i = 2; i<=n; i++ ) {
const tmp = lastFirst ;
lastFirst = lastFirst + lastSec;
lastSec = tmp;
}
return lastFirst ;
}

最后

以上就是粗暴音响为你收集整理的递归优化的全部内容，希望文章能够帮你解决递归优化所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。