20

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

 4 years ago
source link: https://tech.youzan.com/thinking-in-functional/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

在我们初学函数的时候,函数通常被描述为能独立完成一个功能的单元,并且通常以命令式的方式出现:

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

我们称之为T变换。通过观察可以发现,从1和0开始将T反复应用 n 次将产生出一对数 Fib(n+1)Fib(n) 。换句话说,斐波那契数可以通过将 T(n) (变换T的n次方)应用于对偶 (1, 0) 而产生出来。现在将T看作是变换族 T(p, q)p = 0q = 1 的特殊情况,其中 T(p, q) 是对于对偶 (a, b) 按照 a <- bq + aq + apb <- bp + aq 规则的变换。请证明,如果我们应用变换 T(p, q) 两次,其效果等同于应用同样形式的一次变换 T(p', q') ,其中 p'q' 可以由 pq 计算出来。这样,就像 fastExp 一样,我们可以得到一个空间复杂度为O(1),时间复杂度为O(log n)的斐波那契数列函数。这是《计算机程序的构造和解释》的练习1.19,你可以自行完成这个过程。

通过对老朋友斐波那契数列的思考,我们发现,通过函数式的方式思考可以有效的简化问题,从而得到一个简单的递归版本。当我们的执行环境不具备自动优化尾调用的时候,在必要的情况下,我们可以很容易的手动把它优化为一个等价的循环形式。这就是函数式思维带来的优势。

欢迎关注我们的公众号

bqyERrE.png!web

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK