zipWith 接受一个回调函数和两个列表为参数。他会并行遍历两个列表，并把单遍历到的元素一一对应，传进回调函数，把每一步遍历的计算结果存在新的列表里，最终返回这个心列表。
Python 版：
def zipWith(f, listA, listB): if len(listA) == 0 or len(listB) == 0: return [] headA, tailA = listA[0], listA[1:] headB, tailB = listB[0], listB[1:] return [f(headA, headB)] + zipWith(f, tailA, tailB) print zipWith(lambda x, y : x + y, [2,2,2,2], [3,3,3,3,3]) # [5,5,5,5] # 结果列表长度由参数中两个列表更短的那个决定
JS 版：
const zipWith = f => xs => ys => { if (xs.length === 0 || ys.length === 0) return []; const [headX, ...tailX] = xs; const [headY, ...tailY] = ys; return [f(headX)(headY), ...zipWith(f)(tailX)(tailY)]; };
replicate
Python 版：
def replicate(n,x): if n <= 0: return [] return [x] + replicate(n-1,x) print replicate(4, 'hello') # ['hello', 'hello', 'hello', 'hello']
JS 版：
const replicate = (n, x) => { if (n <= 0) return []; return [x, ...replicate(n - 1, x)]; };
reduce
Python 不鼓励用 reduce，我就不写了。
JS 版：
const reduce = (f, acc, arr) => { if (arr.length === 0) return acc; const [head, ...tail] = arr; return reduce(f, f(head, acc), tail); };
quickSort
用递归来实现排序算法肯定不是最优的，但是如果处理数据量小的话，也不是不能用。
Python 版：
def quickSort(xs): if len(xs) <= 1: return xs pivot, rest = xs[0], xs[1:] smaller, bigger = [], [] for x in rest: smaller.append(x) if x < pivot else bigger.append(x) return quickSort(smaller) + [pivot] + quickSort(bigger) print quickSort([44,14,65,34]) # [14, 34, 44, 65]
JS 版：
const quickSort = list => { if (list.length === 0) return list; const [pivot, ...rest] = list; const smaller = []; const bigger = []; rest.forEach(x => x < pivot ? smaller.push(x) : bigger.push(x); ); return [...quickSort(smaller), pivot, ...quickSort(bigger)] };
解决递归爆栈问题
由于我对 Python 还不是特别熟，这个问题只讲 JS 场景了，抱歉。
每次递归时，JS 引擎都会生成新的 frame 分配给当前执行函数，当递归层次太深时，可能会栈不够用，导致爆栈。ES6引入了尾部优化（TCO），即当递归处于尾部调用时，JS 引擎会把每次递归的函数放在同一个 frame 里面，不新增 frame，这样就解决了爆栈问题。
然而，V8 引擎在短暂支持 TCO 之后，放弃支持了。那为了避免爆栈，我们只能在程序层面解决问题了。 为了解决这个问题，大神们发明出了 trampoline 这个函数。来看代码：
const trampoline = fn => (...args) => { let result = fn(...args); while (typeof result === "function") { result = result(); } return result; };
给trampoline传个递归函数，它会把递归函数的每次递归计算结果保存下来，然后只要递归没结束，它就不停执行每次递归返回的函数。这样做相当于把多次的函数调用放到一次函数调用里了，不会新增 frame，当然也不会爆栈。
先别高兴太早。仔细看 trampoline 函数的话，你会发现它也要求传入的递归函数符合尾部调用的情况。那不符合尾部调用的递归函数怎么办呢？（ 比如我刚刚写的 JS 版 quickSort，最后 return 的结果里，把两个递归调用放在了一个结果里。这种情况叫 binary recursion，暂译二元递归，翻译错了勿怪 ）
这个问题我也纠结了很久了，然后直接去 Stack Overflow 问了，然后真有大神回答了。要解决把二元递归转换成尾部调用，需要用到一种叫 Continuous Passing Style (CPS) 的技巧。来看怎么把 quickSort 转成尾部调用:
const identity = x => x; const quickSort = (list, cont = identity) => { if (list.length === 0) return cont(list); const [pivot, ...rest] = list; const smaller = []; const bigger = []; rest.forEach(x => (x < pivot ? smaller.push(x) : bigger.push(x))); return quickSort(smaller, a => quickSort(bigger, b => cont([...a, pivot, ...b])), ); }; tramploline(quickSort)([5, 1, 4, 3, 2]) // -> [1, 2, 3, 4, 5]
如果上面的写法难以理解，推荐去看 Kyle Simpson 的这章内容。我不能保证比他讲的更清楚，就不讲了。
屠龙之技
虽然我将要讲的这个概念在 JS 中根本都用不到，但是我觉得很好玩，就加进来了。有些编程语言是不支持递归的（我本科不是学的计算机，不知道是哪些语言），那这时候如果我知道用递归可以解决某个问题，该怎么办？用 Y-combinator.
JS 实现：