recursion - Elixir 中的递归是如何工作的

Question

Elixir 中的简单函数，返回from to 的数字列表:

defmodule MyList do

  def span(_), do: raise "Should be 2 args"
  def span(from, to) when from > to,  do: [ to | span(to + 1, from) ]
  def span(from, to) when from < to,  do: [ from | span(from + 1, to) ]
  def span(from, to) when from == to, do: [ from ]
end

我完全不知道为什么它会起作用并返回一个数字列表。

MyList.span(1,5)
#=> [1,2,3,4,5]

我就是无法理解这个问题:

[ from | span(from + 1, to) ]

好吧，我认为第一个循环将返回以下内容:

[ 1 | span(2, 5) ]

下一步是什么？ [ 1, 2 |跨度(3, 5)]？为什么？

它如何知道何时停止？为什么它还能工作？

请不要追逐要点 - 如果您不打算努力为函数式程序员菜鸟(OO 程序员)弄清楚事情(呃)，请不要费心回答。

作为答案的奖励，您可以为我提供有关如何开始递归思考的提示吗？有什么 Elixir 吗？

它如何跟踪头部？该函数如何在每次迭代中创建新列表并保留前一次生成的值？

谢谢!

Answer 1

好吧，让我们试一下。

Erlang 使用 call-by-value 来评估函数调用战略。来自链接的维基百科:

[call-by-value is a] family of evaluation strategies in which a function's argument is evaluated before being passed to the function.

这意味着当 Elixir(或者更确切地说 Erlang)看到带有一些参数的函数调用时，它会在调用函数之前评估这些参数(显然也可以是表达式)。 p>

例如，我们以这个函数为例:

def add(a, b), do: a + b

如果我用两个表达式作为参数调用它，这些表达式将在结果相加之前进行计算:

add(10 * 2, 5 - 3)
# becomes:
add(20, 2)
# kind of becomes:
20 + 2
# which results in:
22

现在我们已经实现了按值调用，让我们暂时将 list 中的 | 构造视为一个函数。想象一下它是否会像这样使用:

|(1, [])         #=> [1]
|(29, [1, 2, 3]) #=> [29, 1, 2, 3]

与所有函数一样，| 在执行工作之前评估其参数(即创建一个新列表，其中第一个参数作为第一个元素，第二个参数作为列表的其余部分)。

当您调用 span(1, 5) 时，它会扩展(假设它扩展)为:

|(1, span(2, 5))

现在，由于 | 的所有参数都必须先求值，然后才能实际将 1 前置到 span(2, 5)，我们必须评估 span(2, 5)。 这种情况持续了一段时间:

|(1, |(2, span(3, 5)))
|(1, |(2, |(3, span(4, 5))))
|(1, |(2, |(3, |(4, span(5, 5)))))
|(1, |(2, |(3, |(4, [5]))))))
# now, it starts to "unwind" back:
|(1, |(2, |(3, [4, 5])))
|(1, |(2, [3, 4, 5]))
|(1, [2, 3, 4, 5])
[1, 2, 3, 4, 5]

(抱歉，如果我使用此 |() 语法，请记住我只是使用 | 作为函数而不是运算符)。

没有任何东西可以跟踪头部，也没有函数“保留前一个[迭代]中产生的值”。第一个调用 (span(1, 5)) 仅扩展为 [1|span(2, 5)]。现在，为了让 span(1, 5) 调用返回，它需要计算 [1|span(2, 5)]:现在你已经知道了，递归!它需要首先评估 span(2, 5) 等等。

从技术上讲，这些值被保存在某个地方，并且位于堆栈上:每个函数调用都被放置在堆栈上，并且仅在能够返回时才弹出。因此，堆栈将类似于我上面显示的一系列调用:

# First call is pushed on the stack
span(1, 5)
# Second call is pushed on top of that
span(1, 5), span(2, 5)
# ...
span(1, 5), span(2, 5), ..., span(5, 5)
# hey! span(5, 5) is not recursive, we can return [5]. Let's pop span(5, 5) from the stack then
span(1, 5), ..., span(4, 5)
# Now span(4, 5) can return because we know the value of span(5, 5) (remember, span(4, 5) is expanded to [4|span(5, 5)]

这种情况一直持续到返回到 span(1, 5) (现在是 span(1, [2, 3, 4, 5]))最后到[1,2,3,4,5]。

好吧，我写了很多，但我不确定我是否让你更清楚了:)。有什么不清楚的地方请追问。肯定有很多资源可以学习递归；只是为了命名我发现的第一批:

• "Recursion" chapter Learn You Some Erlang for Great Good，一本关于 Erlang 的好书
• 必填 Wikipedia page关于递归
• 我刚刚在 khan academy website 上发现了一个关于递归的好页面。
• 为什么不呢，一些 Elixir 特定的资源:the "Getting started" guide on Elixir's website , this博客文章，this other博客文章