函数式编程之递归的几种方式

函数式编程提倡使用递归，而不是循环。递归在某些场合下更优雅、更简洁。

但是使用递归有时候会遇到一些问题，比如说栈溢出。

这里总结了几种解决栈溢出问题的几种解决方案，比如最有效的尾递归（tail call），以及不使用尾递归的其它两种方式。

首先，要解决问题就得先有问题；这里使用例子来分析递归的几种方法：

• 判断一句话中有几个元音字母
  • 这里给出判断是否元音字母的函数

const isVowel = letter => {
    const vowel = new Set(['a','e','i','o','u','A','E','I','O','U']);
    return vowel.has(letter)
}
1
2
3
4

普通递归

首先想到的应该是循环的方法（至少我是），循环更简单易懂，也好写：

// loop
function loopCountVowel(sentence) {
    let ans = 0;
    for (let i = 0;i<sentence.length;i++){
        if(isVowel(sentence[i]))
            ans++;
    }
    return ans;
}
loopCountVowel(
    "Create and share beautiful images of your source code."
)//22
1
2
3
4
5
6
7
8
9
10
11
12

接着，我们来写普通的递归方法，这个也很容易想到：

// recursion
function recursionCountVowel(sentence) {
    let first = isVowel(sentence[0]) ? 1 : 0;
    if(sentence.length <= 1) return first;
    return first + recursionCountVowel( sentence.slice(1) )
}
recursionCountVowel(
    "Create and share beautiful images of your source code."
)// 22
1
2
3
4
5
6
7
8
9

这种递归的方式似乎很好，但是当数据量大的时候，或者更复杂的时候，会引起栈溢出(stack overflow)。造成栈溢出的原因是由于函数运行时，上面的递归会把一个个的函数都一股脑地塞进栈（stack）里，等到递归遇到限定条件停止时，才会一次把所有存在栈里的函数拿出来运算。栈或者说内存大小是有限的，如果递归过深就会把栈撑满，撑爆，溢出；解决栈溢出的方法就是尾递归，如下：

尾递归(PTC)

proper tail calls,PTC，即正确的尾递归。

普通的递归导致溢出的根本原因是，一股脑地把所有的函数都存在栈里，等到最后才拿出来运算。函数保存在栈里的根本原因是函数没有运算结束，上一个函数需要依靠下一个函数的结果。所以，只要解决这个问题即可。

尾递归就是避免把不必要的函数一直保存在栈里，在函数尾部避免使用两个或以上的自身递归调用和其它和下一个函数绑定的数据。只在尾部调用自己，使本函数返回后是完成状态，这样才会使其及时脱离栈。

即把计算结果当作参数而不是返回值。

需要注意的是，在ES6标准里，js才能支持尾递归，且必须在严格模式下才行！

"use strict";
// tail calls
function PTCCountVowel(count, sentence) {
    count += isVowel(sentence[0]) ? 1 : 0;
    if(sentence.length < 2) return count;
    return PTCCountVowel(count, sentence.slice(1))
}
console.log(PTCCountVowel(
    0,
     "Create and share beautiful images of your source code."
)//22
1
2
3
4
5
6
7
8
9
10
11

由于第一个参数count 在每次调用时都应该是0，所以可以使用柯里化省去这一参数：

"use strict";
function PTC(count) {
    return function inner(sentence) {
        count += isVowel(sentence[0]) ? 1 : 0;
        if(sentence.length < 2) return count;
        return inner(sentence.slice(1))
    }
}

const PTCCountVowel = PTC(0);

PTCCountVowel(
    "Create and share beautiful images of your source code."
)//22
1
2
3
4
5
6
7
8
9
10
11
12
13
14

CPS

如果不依赖尾调用，那么还有其它方式避免栈溢出，这里介绍两种方式。

其一就是CPS（Continuation-Passing Style），这种方法比较难理解，也难写，效率也不高，并且可能会有堆内存存储问题。并不建议使用此方法。

代码例子：

"use strict";
function CPS(sentence, count = v => v) {
    let first = isVowel(sentence[0]) ? 1 : 0;
    if(sentence.length < 2) return count(first);
    return CPS(sentence.slice(1), function f(v) {
        return count(first + v);
    })
}

CPS(
    "Create and share beautiful images of your source code."
)//22
1
2
3
4
5
6
7
8
9
10
11
12

Trampolines

第二种方法是Trampolines，单词的意思是蹦床，描述为栈里的函数像是蹦床一样进去一个，出来一个，一上一下，避免都堆在栈里。

function trampoline(fn) {
    return function trampolined(...args) {
        let result = fn(...args);
        while (typeof result == "function") {
            result = result();
        }
        return result;
    }
}
const countVowel = trampoline(function f(count, sentence){
    count += isVowel(sentence[0]) ? 1 : 0;
    if(sentence.length < 2) return count;
    return function fn() {
        return f(count, sentence.slice(1))
    }
})

countVowel(
    0,
    "Create and share beautiful images of your source code."
)//22
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21