这篇文章一个多月前以英文发表在我的个人博客，现在抽空翻译成中文，并补充一些没来得及写的内容。
昨天我发表的《如何在 JS 代码中消灭 for 循环》引起很多争议。为了避免没营养的讨论，我先声明一下。递归性能差是没争议的事实，如果你觉得 for 循环更好，没必要学递归，那看到这里你可以不用看了。这篇文章要展示的大部分代码，仅仅是学习目的，我不推荐在生产环境中用。但是如果你对函数式编程感兴趣，想深入理解一些核心概念，你应该读下去。
今年年初我开始学 Haskell 的时候，我被函数式代码的优雅和简洁俘获了。代码居然还能这样写！用指令式代码要写一堆的程序，用递归几行就解决了。这篇文章里，我会把我在 Haskell 里面看到的递归函数翻译成 JS 和 Python，并尽量每一步解释。最后我会尝试解决递归爆栈（Stack Overflow）的问题。
递归基础
我从 Python 代码开始，然后展示 JS 实现。
很多解释递归的教程是从解释斐波那契数列开始的，我觉得这样做是在用一个已经复杂的概念去解释另一个复杂的概念，没有必要。我们还是从简单的代码开始吧。
运行这段 Python 代码：
def foo(): foo() foo()
当然会报错。😱 foo 函数会一直调用自己。因为我没有告诉它何时停，它会一直执行下去，直到爆栈。那我们稍作修改再运行一下：
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) ? head : max(tail); };
更多递归的例子
接下来我展示几个我从 Haskell 翻译过来的递归函数。刚刚已经用很大篇幅解释递归了，这些函数就不解释了。
reverse
Python 版：
# 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