递归函数的优化

悠悠 2022-05-17 09:39 202阅读 0赞

#### 为什么要优化递归 ####

先看个例子：

// 递归裴波那切数列
    function fibonacci(n) { 
        if (n>2) {
            return fibonacci(n-1) + fibonacci(n-2);
        } else {
            return 1
        }
    }
    
    function t(n) { 
        console.time('a');
        console.log(fibonacci(n));
        console.timeEnd('a')
    }
    t(35);
    t(40);
    t(42);
    
    打印结果如下： 
    9227465
    a: 57.330ms
    102334155
    a: 589.497ms
    267914296
    a: 1550.535ms

正常的递归函数，算到42就已经花费1.5s了，更不用说再往后算了

优化方法一：

var fibArr = [ undefined, 1, 1 ];
    function fibonacci( n ){ 
        var nFib = fibArr[ n ];
        return nFib
             ? nFib
             : ( fibArr[ n ] = fibonacci( n-1 ) + fibonacci( n-2 ) );
    }
    function t(n) { 
        console.time('a');
        console.log(fibonacci(n));
        console.timeEnd('a')
    }
    t(35);
    t(40);
    t(42);
    
    打印结果如下：
    9227465
    a: 0.284ms
    102334155
    a: 0.088ms
    267914296
    a: 0.080ms

优化方式二：

function fibonacci(n) { 
        var x = 1, y = 1, i = 2, t;
        while (i<n) { t = y; y = x + y; x = t; i++; }
        return y;
    }
    
    function t(n) { 
        console.time('a');
        console.log(fibonacci(n));
        console.timeEnd('a')
    }
    打印结果如下：
    9227465
    a: 0.416ms
    102334155
    a: 0.400ms
    267914296
    a: 0.170ms

发表评论取消回复

表情：

评论列表（有 0 条评论，202人围观）

还没有评论，来说两句吧...

相关阅读

相关函数的递归

函数的递归一.递归的定义二.递归的条件三.递归的限制四.更深的理解 ![在这里插入图片描述][d85e57ed0bbb41018b

心已赠人/ 2024年04月01日 14:17/ 0 赞/ 92 阅读

相关递归——递归函数的详细过程

函数递归什么是递归？递归的两个必要条件例子斐波那契数的递归求解 n的阶乘递归求解什么是递归？程序调

港控/mmm°/ 2022年12月26日 09:26/ 0 赞/ 250 阅读

相关递归的函数

[Submit][] [Statistic][] Problem Description 给定一个函数 f(a, b, c)：如果 a ≤ 0 或 b ≤ 0 或

た入场券/ 2022年07月14日 15:22/ 0 赞/ 237 阅读

相关递归函数调用递归函数

题目如下：问下列代码的打印结果为0吗？ \[cpp\] [view plain][] [copy][view plain] 1. \include <stdlib.h>

柔光的暖阳◎/ 2022年06月13日 10:07/ 0 赞/ 351 阅读

相关递归的函数

递归的函数 Time Limit: 1000MS Memory Limit: 65536KB [Submit][] [Statistic][] Problem De

待我称王封你为后i/ 2022年06月09日 01:26/ 0 赞/ 303 阅读

相关利用默认参数优化递归函数

实际上，尾调用的优化发生在引擎背后，除非你尝试优化一个函数，否则无需思考此类问题。递归函数是其主要的应用场景，此时尾调用优化的效果很显著。请看下面这个阶乘函数

小鱼儿/ 2022年05月29日 08:10/ 0 赞/ 164 阅读

相关递归函数

在函数内部，可以调用其他函数。如果一个函数在内部调用自身本身，这个函数就是递归函数。举个例子，我们来计算阶乘`n! = 1 x 2 x 3 x ... x n`，用函数`f

骑猪看日落/ 2022年05月18日 04:17/ 0 赞/ 305 阅读

相关递归函数的优化

为什么要优化递归先看个例子： // 递归裴波那切数列 function fibonacci(n) { if (n>2) {

悠悠/ 2022年05月17日 09:39/ 0 赞/ 203 阅读

相关函数递归

函数递归函数递归：函数重复地调用自己，这叫递归。 <table> <tbody> <tr> <td>

你的名字/ 2022年01月07日 15:53/ 0 赞/ 312 阅读

相关【转】递归与优化：尾递归

了解尾递归之前，先了解一下尾调用。 > 在计算机科学里，尾调用是指一个函数里的最后一个动作是一个函数调用的情形：即这个调用的返回值直接被当前函数返回的情形。这种情形下该调用位

落日映苍穹つ/ 2021年12月05日 22:05/ 0 赞/ 311 阅读