这篇文章一个多月前以英文发表在我的个人博客,现在抽空翻译成中文,并补充一些没来得及写的内容。
昨天我发表的《如何在JS代码中消灭的循环》引起很多争议。为了避免没营养的讨论,我先声明一下。递归性能差是没争议的事实,如果你觉得为循环更好,没必要学递归,那看到这里你可以不用看了。这篇文章要展示的大部分代码,仅仅是学习目的,我不推荐在生产环境中用。但是如果你对函数式编程感兴趣,想深入理解一些核心概念,你应该读下去。
今年年初我开始学Haskell的时候,我被函数式代码的优雅和简洁俘获了。代码居然还能这样写!用指令式代码要写一堆的程序,用递归几行就解决了。这篇文章里,我会把我在Haskell里面看到的递归函数翻译成JS和Python,并尽量每一步解释。最后我会尝试解决递归爆栈(Stack Overflow)的问题。
我从Python代码开始,然后展示JS实现。
很多解释递归的教程是从解释斐波那契数列开始的,我觉得这样做是在用一个已经复杂的概念去解释另一个复杂的概念,没有必要。我们还是从简单的代码开始吧。
运行这段Python代码:
当然会报本市错# 128561;foo函数会一直调用自己。因为我没有告诉它何时停,它会一直执行下去,直到爆栈。那我们稍作修改再运行一下:
这段代码基本什么都没做,但是这次它不会报错了。我在foo函数定义初始就告诉它什么时候该停,然后我每次调用的时候都把参数改一下,直到参数满足判断条件,函数停止执行。
如果你理解了上面两段代码,你已经理解递归了。
从上面的代码我总结一下递归的核心构成:
-
<李>递归函数必须接受参数。
<李>在递归函数的定义初始,应该有一个判断条件,当参数满足这个条件的时候,函数停止执行,并返回值。
<李>每次递归函数执行自己的时候,都需要把当前参数做某种修改,然后传入下一次递归。当参数被累积修改到符合初始判断条件了,递归就停止了。
现在我们来用Python写个max函数,找出列表中的最大值。是的,我知道Python原生有马克斯函数,我重新发明个轮子只是为了学习和好玩。
max2函数接受一个列表作为参数,如果列表长度为1,函数停止执行并把列表第一个元素返回出去。注意,当递归停止时,它必须返回值。(但是如果你想用递归去执行副作用,而不是纯计算的话,可以不返回值)。如果初始判断条件不满足,把列表的头和尾取出来,接着,我们比较头部元素和尾部列表中最大值的大小(我们先不管尾部列表中最大值是哪个),并把比较结果中更大的那个值返回出去。那我们怎样知道尾部列表中的最大值?答案是我们不用知道。我们已经在max2函数中定义了比较两个值,并把大的值返回出去这个行为了。我们只需要把这同一个行为作用于尾部列表,程序会帮我们找到。
下面是JS的实现:
更多递归的例子
接下来我展示几个我从Haskell翻译过来的递归函数。刚刚已经用很大篇幅解释递归了,这些函数就不解释了。
<强>反向
:
JS版:
