用函数式的方式思考——递归
点击关注“有赞coder”
获取更多技术干货哦～
团队：共享前端
function fact(n: number): number {
let result = 1;
for (let i = 0; i <= n; i += 1) {
result *= i;
}
return result;
}
代码是在操作数据，把一种形式的数据编程另一种形式。抽象的数据是一种数据，而显示在屏幕上的位图也是一种数据，当然必要的时候我们也可以把函数视作数据。我们可以得到一个数据到界面的映射关系，就像React提倡的那样：
Model -> View
或者用函数的形式
View = f(Model)
现在我们不讨论React，只讨论函数本身。我们可以把函数，特别是纯函数，看作是数据的映射关系的具体形式。
a[n]=a*a[n-1]
，我们可以很容易得到一个求幂的函数：
function exp(a: number, n: number) {
return a * exp(a, n - 1);
}
这个函数很简洁，但是会招来担忧。首先它做了 n次函数调用，会有大量函数调用的开销；其次，它还有爆栈的风险。
a*a[n-1]->a[n]
那么显然，幂的实现应该是这样一个函数，其中
prev
就是
a[n-1]
：
function expImpl(a: number, prev: number): number;
function expImpl(a: number, prev: number, i: number, n: number): number;
function expImpl(a: number, prev: number, i: number, n: number): number {
if (i >= n) {
return prev;
}
return expImpl(a, a * prev, i + 1, n);
}
function exp(a: number, n: number) {
return expImpl(a, 1, 0, n);
}
function expImpl(a: number, prev: number, i: number) {
if (i <= 0) {
return prev;
}
return expImpl(a, a * prev, i - 1);
}
function exp(a: number, n: number) {
return expImpl(a, 1, n);
}
expImpl
恰好是个递归函数，这就构成了一个尾递归。
现代的编译器都足够聪明，能够将其优化成等价的循环形式：
function exp(a: number, n: number) {
let i = n;
let ret = 1;
while (i > 0) {
ret = ret * a;
i--;
}
return ret;
}
于是，我们的递归版本可以视作空间复杂度为O(1)时间复杂度为O(n)。可惜的是，现代浏览器中只有Safari实现了这种优化。我们假定执行环境支持尾递归优化。根据数学上幂的定义，当n为偶数，我们有 (a^(n/2))^2=(a^2)^(n/2)。根据这个等式，我们可以得到计算幂递归的对数时间版本（当然，以及它等价的循环版本）：
function fastExpImpl(a: number, prev: number, i: number) {
if (i <= 0) {
return prev;
}
if (i % 2 === 0) {
return expImpl(a * a, prev, i / 2);
}
// 这里还可以做个小优化 expImpl(a * a, a * prev, (i - 1) / 2);
return expImpl(a, a * prev, i - 1);
}
function fastExp(a: number, n: number) {
return expImpl(a, 1, n);
}
用映射的思维，我们来讨论下老朋友，斐波那契数列。初学递归都能写出这样一个简单的递归版本：
function fib(n: number): number {
if (n <= 2) {
return 1;
}
return fib(n - 1) + fib(n - 2);
}
显然，这不是一个优秀的实现。这里做了大量的重复计算，同时有爆栈的风险。根据斐波那契数列的递推公式，我们可以得到这样一个关系：
a[n - 2] + a[n - 1] -> a[n]
a
代表
a[n-1]
，
b
代表
a[n-2]
：
function fibImpl(a: number, b: number): number;
function fibImpl(a: number, b: number, i: number, n: number): number;
当然，和计算幂的时候一样，我们可以优化掉一个参数，于是得到了一个简单的空间复杂度为O(1)，时间复杂度为O(n)的递归版本：
function fibImpl(a: number, b: number, i: number): number {
if (i <= 1) {
return a;
}
return fibImpl(a + b, a, i - 1);
}
function fib(n: number): number {
return fibImpl(1, 0, n);
}
以及等价的循环版本：
function fib(n: number): number {
let a = 1;
let b = 0;
let i = n;
while (i > 1) {
a = a + b;
b = a;
i--;
}
return a;
}
在这个版本中，我们有这样一组变换规则：
a <- a + b
b <- a
n
次将产生出一对数
Fib(n+1)
和
Fib(n)
。
换句话说，斐波那契数可以通过将
T(n)
（变换T的n次方）应用于对偶
(1,0)
而产生出来。
现在将T看作是变换族
T(p,q)
中
p=0
且
q=1
的特殊情况，其中
T(p,q)
是对于对偶
(a,b)
按照
a<-bq+aq+ap
和
b<-bp+aq
规则的变换。
请证明，如果我们应用变换
T(p,q)
两次，其效果等同于应用同样形式的一次变换
T(p', q')
，其中
p'
和
q'
可以由
p
和
q
计算出来。
这样，就像
fastExp
一样，我们可以得到一个空间复杂度为O(1)，时间复杂度为O(log n)的斐波那契数列函数。
这是《计算机程序的构造和解释》的练习1.19，你可以自行完成这个过程。
扩展阅读
Vol.235