迭代与递归是函数进阶的第一个门槛。迭代就是对已知变量反复赋值变换；递归就是函数体内调用自身。
迭代
一个迭代是就是一个循环，根据迭代式对变量反复赋值。
- 求近似根（切线法）；
迭代描述：
- 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
基本要素
- 递归出口：达到边界条件、停止递推、开始归返；
- 递推公式：非边界条件、向更深处递推。
递归过程
- 递推；
- 归返。
优点缺点
- 优点：
- 实现简单；
- 可读性高。
- 缺点：
- 空间利用率低；
- 递归太深，栈溢出。
简单例子
- 阶乘
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
