用函数式的方式思考——递归

见贤思齐

点击关注“有赞coder”获取更多技术干货哦～作者：金智鑫团队：共享前端在我们初学函数的时候，函数通常被描述为能独立完成一个功能的单元，并且通常以命令式的方式出现：function fact(n: number): number { let result = 1; for (let i = 0; i 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) { 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 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) { a = a + b; b = a; i--; } return a;}在这个版本中，我们有这样一组变换规则：a