递归如何在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 | span(3, 5) ]？为什么？

怎么知道,何时停止？它为什么工作？

请不要追逐要点 - 如果你不打算为功能程序员noob(OO程序员)做出明确的努力,请不要费心回答.

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

它如何跟踪头部？函数如何在每次迭代时创建新列表,保持前一个生成的值？

谢谢!

Answer 1

好吧,让我们试一试.

Erlang使用按值调用策略评估函数调用.来自链接的维基百科:

[call-by-value是一个]评估策略系列,其中函数的参数在传递给函数之前被计算.

这意味着当Elixir(或者更确切地说是Erlang)看到带有某些参数的函数调用时,它会在调用函数之前计算参数(显然也可以是表达式).

例如,让我们采取这个功能:

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

现在我们得到了call-by-value,让我们把|列表中的构造想象成一个函数.想想它是否会像这样使用:

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

(对不起,如果我使用这种|()语法,请记住我只是使用|函数而不是运算符).

没有任何东西跟踪头部,没有任何功能"保留前一个[迭代]中产生的值".第一个call(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].

好的,我写了很多,我不确定我是否更清楚了:) 请问任何不清楚的事情.肯定有很多资源可以学习递归; 只是为了找到我发现的第一批:

• "学习你的一些Erlang for Great Good "的"递归"章节,一本关于Erlang的好书
• 关于递归的强制性维基百科页面
• 我刚刚在汗学院网站上发现了一个很好的页面
• 为什么不,一些特定于Elixir的资源:Elixir网站上的"入门"指南,这篇博客文章,另一篇博客文章