前言
这篇文章一个多月前以英文发表在我的个人博客，现在抽空翻译成中文，并补充一些没来得及写的内容。
昨天我发表的《如何在 JS 代码中消灭 for 循环》引起很多争议。为了避免没营养的讨论，我先声明一下。递归性能差是没争议的事实，如果你觉得 for 循环更好，没必要学递归，那看到这里你可以不用看了。这篇文章要展示的大部分代码，仅仅是学习目的，我不推荐在生产环境中用。但是如果你对函数式编程感兴趣，想深入理解一些核心概念，你应该读下去。
今年年初我开始学 Haskell 的时候，我被函数式代码的优雅和简洁俘获了。代码居然还能这样写！用指令式代码要写一堆的程序，用递归几行就解决了。这篇文章里，我会把我在 Haskell 里面看到的递归函数翻译成 JS 和 Python，并尽量每一步解释。最后我会尝试解决递归爆栈（Stack Overflow）的问题。
递归基础
我从 Python 代码开始，然后展示 JS 实现。
很多解释递归的教程是从解释斐波那契数列开始的，我觉得这样做是在用一个已经复杂的概念去解释另一个复杂的概念，没有必要。我们还是从简单的代码开始吧。
运行这段 Python 代码：
def foo(): foo() foo()
当然会报错。"htmlcode">
def foo(n): if n <= 1: return foo(n-1) foo(10)
这段代码基本什么都没做，但是这次它不会报错了。我在 foo 函数定义初始就告诉它什么时候该停，然后我每次调用的时候都把参数改一下，直到参数满足判断条件，函数停止执行。
如果你理解了上面两段代码，你已经理解递归了。
从上面的代码我总结一下递归的核心构成：
- 递归函数必须接受参数。
- 在递归函数的定义初始，应该有一个判断条件，当参数满足这个条件的时候，函数停止执行，并返回值。
- 每次递归函数执行自己的时候，都需要把当前参数做某种修改，然后传入下一次递归。当参数被累积修改到符合初始判断条件了，递归就停止了。
现在我们来用 Python 写个 max 函数，找出列表中的最大值。是的，我知道 Python 原生有 max 函数，我重新发明个轮子只是为了学习和好玩。
# 不要用这个函数，还是用原生的 max 吧。 def max2(list): if len(list) == 1: return list[0] head, tail = list[0], list[1:] return head if head > max2(tail) else max2(tail) print max2([3,98,345]) # 345
max2函数接受一个列表作为参数，如果列表长度为 1，函数停止执行并把列表第一个元素返回出去。注意，当递归停止时，它必须返回值。（但是如果你想用递归去执行副作用，而不是纯计算的话，可以不返回值。）如果初始判断条件不满足，把列表的头和尾取出来。接着，我们比较头部元素和尾部列表中最大值的大小（我们先不管尾部列表中最大值是哪个），并把比较结果中更大的那个值返回出去。那我们怎样知道尾部列表中的最大值？答案是我们不用知道。我们已经在 max2 函数中定义了比较两个值，并把大的值返回出去这个行为了。我们只需要把这同一个行为作用于尾部列表，程序会帮我们找到。
下面是 JS 的实现：
const max = xs => {
if (xs.length === 1) return xs[0];
const [head, ...tail] = xs;
return head > max(tail) "htmlcode">
# Python 内置有 reverse 函数
def reverse2(list):
if len(list) == 1:
return list
head, tail = list[0], list[1:]
return reverse2(tail) + [x]
print reverse2([1,2,3,4,5,6])
# [6,5,4,3,2,1]
JS 版：
const reverse = xs => {
if (xs.length === 1) return xs;
const [head, ...tail] = xs;
return reverse(tail).concat(head);
};
map
Python 版：
# Python 内置有 map 函数
def map2(f, list):
if len(list) == 0:
return []
head, tail = list[0], list[1:]
return [f(head)] + map2(f, tail)
print map2(lambda x : x + 1, [2,2,2,2])
# [3,3,3,3]
JS 版：
const map = f => xs => {
if (xs.length === 0) return [];
const [head, ...tail] = xs;
return [f(head), ...map(f)(tail)];
};
zipWith
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 "color: #ff0000">解决递归爆栈问题
由于我对 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 "_blank" href="http://递归函数">这章内容。我不能保证比他讲的更清楚，就不讲了。
屠龙之技
虽然我将要讲的这个概念在 JS 中根本都用不到，但是我觉得很好玩，就加进来了。有些编程语言是不支持递归的（我本科不是学的计算机，不知道是哪些语言），那这时候如果我知道用递归可以解决某个问题，该怎么办？用 Y-combinator.
JS 实现：
function y(le) {
return (function(f) {
return f(f);
})(function(f) {
return le(function(x) {
return f(f)(x);
});
});
}
const factorial = y(function(fac) {
return function(n) {
return n <= 2 "color: #ff0000">总结
以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值，如果有疑问大家可以留言交流，谢谢大家对的支持。
DDR爱好者之家 Design By 杰米
免责声明：本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除！
稳了！魔兽国服回归的3条重磅消息！官宣时间再确认！
昨天有一位朋友在大神群里分享，自己亚服账号被封号之后居然弹出了国服的封号信息对话框。
这里面让他访问的是一个国服的战网网址，com.cn和后面的zh都非常明白地表明这就是国服战网。
而他在复制这个网址并且进行登录之后，确实是网易的网址，也就是我们熟悉的停服之后国服发布的暴雪游戏产品运营到期开放退款的说明。这是一件比较奇怪的事情，因为以前都没有出现这样的情况，现在突然提示跳转到国服战网的网址，是不是说明了简体中文客户端已经开始进行更新了呢？
更新日志
- 凤飞飞《我们的主题曲》飞跃制作[正版原抓WAV+CUE]
- 刘嘉亮《亮情歌2》[WAV+CUE][1G]
- 红馆40·谭咏麟《歌者恋歌浓情30年演唱会》3CD[低速原抓WAV+CUE][1.8G]
- 刘纬武《睡眠宝宝竖琴童谣 吉卜力工作室 白噪音安抚》[320K/MP3][193.25MB]
- 【轻音乐】曼托凡尼乐团《精选辑》2CD.1998[FLAC+CUE整轨]
- 邝美云《心中有爱》1989年香港DMIJP版1MTO东芝首版[WAV+CUE]
- 群星《情叹-发烧女声DSD》天籁女声发烧碟[WAV+CUE]
- 刘纬武《睡眠宝宝竖琴童谣 吉卜力工作室 白噪音安抚》[FLAC/分轨][748.03MB]
- 理想混蛋《Origin Sessions》[320K/MP3][37.47MB]
- 公馆青少年《我其实一点都不酷》[320K/MP3][78.78MB]
- 群星《情叹-发烧男声DSD》最值得珍藏的完美男声[WAV+CUE]
- 群星《国韵飘香·贵妃醉酒HQCD黑胶王》2CD[WAV]
- 卫兰《DAUGHTER》【低速原抓WAV+CUE】
- 公馆青少年《我其实一点都不酷》[FLAC/分轨][398.22MB]
- ZWEI《迟暮的花 (Explicit)》[320K/MP3][57.16MB]