递归在Elixir中如何工作 [英] How does recursion work in Elixir

问题描述

Elixir中的简单函数，从 到返回数字：

Simple function in Elixir, returning a list of numbers 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

我没有丝毫线索，为什么这样做有效并返回数字列表。

I have no slightest clue, why this works and return a list of numbers.

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

我只是无法解决这个问题：

I just can't get my head around this:

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

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

Ok, first loop, I assume, would return the following:

[ 1 | span(2, 5) ]

下一步是什么？ [1，2 | span（3，5）] ？为什么？

What is next? [ 1, 2 | span(3, 5) ] ? Why?

它怎么知道，何时停止？为什么它甚至还能起作用？

How does it know, when to stop? Why is it even working?

请不要追逐要点-如果您不努力使事情变得清晰，请不要打扰回答（ ），适用于功能性程序员noob（OO程序员）。

Please, do not chase the points - don't bother answering, if you are not going to make an effort to make things clear(er) for functional programmer noob (OO programmer).

作为答案的奖励，您可以为我提供有关如何开始递归思考的提示？有灵丹妙药吗？

As a bonus to the answer you could provide me with a tips on how to start think recursively? Is there any panacea?

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

How does it keep track of the head? How does the function creates new list on each iteration keeping the values produced in the previous?

谢谢！

推荐答案

好吧，让我们试一下。

Erlang使用按值致电策略。从链接的维基百科中：

Erlang evaluates function calls with a call-by-value strategy. From the linked wikipedia:

[按值调用是]一种评估策略系列，其中函数的参数在传递前先经过评估

[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）看到带有某些参数的函数调用时，它将对参数（显然也可以是表达式）在调用该函数之前 。

What this means is that when Elixir (or rather Erlang) sees a function call with some arguments, it evaluates the arguments (which can obviously be expressions as well) before calling the function.

例如，让我们使用此函数：

For example, let's take this function:

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

如果我使用两个表达式作为参数来调用它们，则在将结果相加之前将对这些表达式求值：

If I call it with two expressions as arguments, those expressions will be evaluated before the the results are added up:

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

现在我们得到按值，让我们考虑将list中的 | 构造作为am的函数ment。可以像这样使用它来考虑它：

Now that we get call-by-value, let's think of the | construct in list as a function for a moment. Think of it like if it would be used like this:

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

所有功能， | 在执行工作之前先评估其参数（这将创建一个新列表，其中第一个参数为第一个元素，第二个参数为列表的其余部分）。

As all functions, | evaluates its arguments before doing its work (which is creating a new list with the first argument as the first element and the second argument as the rest of the list).

调用 span（1，5）时，它会扩展（例如，它扩展）为：

When you call span(1, 5), it kind of expands (let's say it expands) to:

|(1, span(2, 5))

现在，由于必须先评估 | 的所有参数，然后才能将 1 实际添加到 span（2，5），我们必须评估 span（2，5）。
这会持续一段时间：

Now, since all arguments to | have to be evaluated before being able to actually prepend 1 to span(2, 5), we have to evaluate span(2, 5). This goes on for a while:

|(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]

（对不起，如果我使用的是 |（）语法，请记住我只是在使用 | 作为函数而不是运算符。）

(sorry if I'm using this |() syntax, remember I'm just using | as a function instead of an operator).

没有东西跟踪头部，没有函数保留上一个[iteration]中产生的值。第一个调用（ span（1，5））刚刚扩展为 [1 | span（2，5）] 。现在，为了返回 span（1，5）调用，它需要评估 [1 | span（2，5）] ：递归！它将需要首先评估 span（2，5），依此类推。

Nothing keeps track of the head and no function "keeps the values produced in the previous [iteration]". The first call (span(1, 5)) just expands to [1|span(2, 5)]. Now, in order for the span(1, 5) call to return, it needs to evaluate [1|span(2, 5)]: there you have it, recursion! It will need to evaluate span(2, 5) first and so on.

从技术上讲，值被保存在某个地方，它在堆栈上：每个函数调用都放在堆栈上，只有在能够返回时才会弹出。因此堆栈看起来就像我上面显示的一系列调用：

Technically, the values are kept somewhere, and it's on the stack: each function call is placed on the stack and popped off only when it's able to return. So the stack will look something like the series of calls I showed above:

# 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] 。

This goes on until it goes back to span(1, 5) (which is now span(1, [2, 3, 4, 5])) and finally to [1, 2, 3, 4, 5].

好吧，我写了很多书，但我不确定我对你说的更清楚了:)。请问任何不清楚的问题。当然，这里有很多资源来学习递归。仅举我发现的第一批名字为例：

Ok I wrote a lot and I'm not sure I made anything clearer to you :). Please, ask anything that's not clear. There are surely a lot of resources to learn recursion out there; just to name the first bunch I found:

• 递归一章，这是一本关于Erlang的好书


• 必填有关递归的维基百科页面


• 我刚刚在可汗学院网站


• 为什么不是，而是一些Elixir的特定资源： Elixir网站上的入门指南，此博客文章，其他博客帖子

• The "Recursion" chapter of Learn You Some Erlang for Great Good, a great book on Erlang
• Obligatory Wikipedia page on recursion
• A nice page I just found about recursion on the khan academy website
• Why not, a couple of Elixir-specific resources: the "Getting started" guide on Elixir's website, this blog post, this other blog post

这篇关于递归在Elixir中如何工作的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！