还不懂递归？读完这篇文章保证你会懂还不懂递归？读完这篇文章保证你会懂
前言前言
这篇文章一个多月前以英文发表在我的个人博客，现在抽空翻译成中文，并补充一些没来得及写的内容。
昨天我发表的《如何在 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 的实现：
资源评论
