迭代与递归是函数进阶的第一个门槛。迭代就是对已知变量反复赋值变换;递归就是函数体内调用自身。

迭代

一个迭代是就是一个循环,根据迭代式对变量反复赋值。

求近似根(切线法);

迭代描述:

x

0

x_0

x0​,初始估计

x

1

=

x

0

f

(

x

0

)

f

(

x

0

)

x_1 = x_0 - \frac{f(x_0)}{f^{'}(x_0)}

x1​=x0​−f′(x0​)f(x0​)​

x

2

=

x

1

f

(

x

1

)

f

(

x

1

)

x_2 = x_1 - \frac{f(x_1)}{f^{'}(x_1)}

x2​=x1​−f′(x1​)f(x1​)​ ……

x

n

=

x

n

1

f

(

x

n

1

)

f

(

x

n

1

)

x_n = x_{n-1} - \frac{f(x_{n-1})}{f^{'}(x_{n-1})}

xn​=xn−1​−f′(xn−1​)f(xn−1​)​ ……直到满足一定精度要求。

下面是一个求一元二次方程的根的例子。

/* 求一元二次方程的根

* a, b, c 是方程系数; x0 是初始估计

*/

function root2([a, b, c], x0) {

let fx0, dfdx0;

while (1) {

fx0 = a*x0*x0 + b*x0 + c;

if (Math.abs(fx0) < 1e-6) break;

dfdx0 = 2*a*x0 + b;

x0 = x0 - fx0 / dfdx0;

}

return x0;

}

let eq = [2, 3, 1], x0 = 0;

root2(eq, x0) // -0.499999

斐波那契数列

f

0

=

0

,

f

1

=

1

f0 = 0, f1 = 1

f0=0,f1=1

f

2

=

f

1

+

f

0

f2 = f1 + f0

f2=f1+f0

f

3

=

f

2

+

f

1

f3 = f2 + f1 ……

f3=f2+f1……

function fib(n) {

n = +n;

let i = 0;

let f0 = 0, f1 = 1;

while (i < n) {

[f0, f1] = [f1, f0 + f1];

i++;

}

return f0;

}

fib(0) // 0

fib(1) // 1

fib(2) // 1

fib(3) // 2

fib(8) // 21

递归

递归就是在函数体内调用自身。在函数体中调用自身至少有以下三种方式:

函数名;arguments.callee;作用域内一个指向该函数的变量名;

function fac(n) {

if (n <= 1) return 1;

else return n * fac(n - 1);

}

function fac(n) {

if (n <= 1) return 1;

else return n * arguments.callee(n - 1);

}

let factorial = function fac(n) {

if (n <= 1) return 1;

else return n * factorial(n - 1);

}

factorial(5) // 120

基本要素

递归出口:达到边界条件、停止递推、开始归返;递推公式:非边界条件、向更深处递推。

递归过程

递推;归返。

#mermaid-svg-r0brLGfu8BRdE2oB {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-r0brLGfu8BRdE2oB .error-icon{fill:#552222;}#mermaid-svg-r0brLGfu8BRdE2oB .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-r0brLGfu8BRdE2oB .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-r0brLGfu8BRdE2oB .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-r0brLGfu8BRdE2oB .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-r0brLGfu8BRdE2oB .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-r0brLGfu8BRdE2oB .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-r0brLGfu8BRdE2oB .marker{fill:#333333;stroke:#333333;}#mermaid-svg-r0brLGfu8BRdE2oB .marker.cross{stroke:#333333;}#mermaid-svg-r0brLGfu8BRdE2oB svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-r0brLGfu8BRdE2oB .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-r0brLGfu8BRdE2oB .cluster-label text{fill:#333;}#mermaid-svg-r0brLGfu8BRdE2oB .cluster-label span{color:#333;}#mermaid-svg-r0brLGfu8BRdE2oB .label text,#mermaid-svg-r0brLGfu8BRdE2oB span{fill:#333;color:#333;}#mermaid-svg-r0brLGfu8BRdE2oB .node rect,#mermaid-svg-r0brLGfu8BRdE2oB .node circle,#mermaid-svg-r0brLGfu8BRdE2oB .node ellipse,#mermaid-svg-r0brLGfu8BRdE2oB .node polygon,#mermaid-svg-r0brLGfu8BRdE2oB .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-r0brLGfu8BRdE2oB .node .label{text-align:center;}#mermaid-svg-r0brLGfu8BRdE2oB .node.clickable{cursor:pointer;}#mermaid-svg-r0brLGfu8BRdE2oB .arrowheadPath{fill:#333333;}#mermaid-svg-r0brLGfu8BRdE2oB .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-r0brLGfu8BRdE2oB .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-r0brLGfu8BRdE2oB .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-r0brLGfu8BRdE2oB .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-r0brLGfu8BRdE2oB .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-r0brLGfu8BRdE2oB .cluster text{fill:#333;}#mermaid-svg-r0brLGfu8BRdE2oB .cluster span{color:#333;}#mermaid-svg-r0brLGfu8BRdE2oB div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-r0brLGfu8BRdE2oB :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;}

4!=4*3!

3!=3*2!

2!=2*1!

return 1

return 2*fac(1)

return 3*fac(2)

return 4*fac(3)

1!

fac(1)

2!

fac(2)

3!

fac(3)

4!

fac(4)

result

优点缺点

优点:

实现简单;可读性高。 缺点:

空间利用率低;递归太深,栈溢出。

简单例子

阶乘

function fac(n) {

if (n == 0) return 1; // 递归出口

else return n * fac(n - 1); // 递推公式

}

fac(4) // 24

fac(170) // 7.257415615307994e+306

fac(171) // Infinity

斐波那契数列

function fib(n) {

if (n <= 1) return 1;

else return fib(n - 1) + fib(n - 2);

}

fib(0) // 0

fib(1) // 1

fib(2) // 1

fib(3) // 2

fib(8) // 21

参考链接

评论可见,请评论后查看内容,谢谢!!!
 您阅读本篇文章共花了: