迭代与递归是函数进阶的第一个门槛。迭代就是对已知变量反复赋值变换；递归就是函数体内调用自身。
迭代
一个迭代是就是一个循环，根据迭代式对变量反复赋值。
求近似根（切线法）；
迭代描述：
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
参考链接
您阅读本篇文章共花了： 大家都在找：
javascript：javascript 菜鸟教程
开发语言：开发语言最新排名
ecmascript：ecmascript6
学习：学习的励志短句
发表评论