递归和尾调用优化示例

Question

我正在尝试学习 Elixir 和函数编程，但在理解 Elixir in Action 一书中的这个例子时遇到了困难。

defmodule ListHelper do
  def sum([]), do: 0
  def sum([head | tail]) do
    head + sum(tail)
  end
end

ListHelper.sum([12,3,4])

这个的 return 值为 19，但我不明白这些值是如何累积的。

我以为 head 是不断更新的，然后当模式与 [] 匹配时，累积的 head 将被添加到 0 并且函数将退出，但在玩过之后我'我现在认为这不是正在发生的事情。有人可以为这个例子中发生的事情提供另一种解释吗？如果我需要解释更多，我可以尝试重新访问它。

Answer 1

sum([head | tail])是head + sum(tail)，所以sum([12,3,4])是12 + sum([3,4])，sum([3,4])是3 + sum([4])，sum([4])是4 + sum([])。 sum([]) 是 0，所以我们总共得到：

sum([12,3,4]) = 12 + sum([3,4])
              = 12 + 3 + sum([4])
              = 12 + 3 + 4 + sum([])
              = 12 + 3 + 4 + 0
              = 19

对sum的递归调用不是尾调用，所以这里不会发生尾调用优化。要使其成为 TCO，需要递归调用 sum 成为最后一个。

defmodule ListHelper do
  def sum([], acc), do: acc
  def sum([head | tail], acc),
    do: sum(tail, acc + head)
end

ListHelper.sum([12,3,4], 0)
#⇒ 19

Answer 2

I thought head was being continuously updated...

没有。每次调用 sum() 都会创建一个新的、单独的 head 变量。这是通过创建一个新的 堆栈框架 来实现的，其中一个框架包含函数调用创建的所有局部变量——包括参数变量，如 head.

如果你这样写：

x = 3 + func1()

elixir 必须评估 func1() 才能计算 x 变量的值。并且，func1() 的定义可能会创建自己的 x 变量，因此 elixir 会分配一个新的栈帧来计算 func1() 的 return 值。一旦 elixir 计算出 func1() 的 return 值，该值将被替换到上面的行中：

           42
            |
            V

x = 3 + func1()

x = 3 + 42
x = 45

...并且 elixir 可以计算 x 变量的值。

如果你这样写也会发生同样的事情：

4 + sum([5,6,7])

唯一不同的是elixir会在栈上分配很多栈帧来计算sum([5,6,7])的return值。通过递归函数调用，每个堆栈帧的 return 值将取决于另一个堆栈帧的 return 值。只有达到基本情况，并且 sum([]) returns 0 才能开始 elixir 开始在每个堆栈帧中填充所需的值以计算一个 return 值。

  4 + sum([5,6,7]) 
           |  
           |
     #1    V  sum([5,6,7])
   +--------------------+              
   | head = 5           |              
   | tail = [6,7]       |              
   |                    |             
   | return:            |            
   |   head + sum(tail) |                    
   |    5 +  sum([6,7]) |
   +-------------|------+
                 |
        #2       V  sum([6,7])
      +----------------------+   
      | head = 6             |    
      | tail = [7]           |   
      |                      |        
      | return:              |             
      |     head + sum(tail) |         
      |       6  + sum([7])  |
      +-----------------|----+
                        |        
            #3          V  sum([7])
          +----------------------+     
          | head = 7             |     
          | tail = []            |     
          |                      |     
          | return:              |     
          |     head + sum(tail) |     
          |       7  + sum([])   |     
          +----------------|-----+      
                           |
                #4         V   sum([])
             +-----------------------+
             |  return: 0            |
             +-----------------------+

请注意，同时存在三个独立的 head 变量。一旦底部堆栈帧 returns，将启动以下步骤：

 4 + sum([5,6,7]) 
           ^
           | 
           +---18-----------<----------+
   +--------------------+              |
   | head = 5           |              |
   | tail = [6,7]       |              |
   |                    |              ^
   | return:            |              |
   |   head + sum(tail) |              |      
   |    5 +  sum([6,7]) ---->---18-----+  #7
   +-------------^------+
                 |
                 +--13------<----------+
      +----------------------+         |
      | head = 6             |         |
      | tail = [7]           |         |
      |                      |         ^
      | return:              |         |     
      |     head + sum(tail) |         |
      |       6  + sum([7]) -|-->--13--+  #6
      +-----------------^----+
                        |        
                        +---7--<-------+
          +----------------------+     |
          | head = 7             |     ^
          | tail = []            |     |
          |                      |     |
          | return:              |     ^
          |     head + sum(tail) |     |
          |       7  + sum([]) --|>--7-+     
          +----------------^-----+      
                           |
                           +----0--<---+
               +-----------------+     |
               |  return: 0    --|>--0-+  #5
               +-----------------+

如果您在代码中添加一些打印语句，您可以看到这些步骤是如何执行的：

defmodule My do
  def sum([]) do
    IO.puts("Inside sum([]):\n\treturning 0")
    0
  end
  def sum([head | tail]) do
    IO.puts("Inside sum([head|tail]), head=#{head} tail=#{inspect(tail, charlists: :as_lists)}")
    val = head + sum(tail)
    IO.puts("Inside sum([head|tail]), head=#{head} tail=#{inspect(tail, charlists: :as_lists)}")
    IO.puts("\treturning #{val}")
    val
  end
end

My.sum([5,6,7])

在命令行：

~/elixir_programs$ elixir a.exs
Inside sum([head|tail]), head=5 tail=[6, 7]
Inside sum([head|tail]), head=6 tail=[7]
Inside sum([head|tail]), head=7 tail=[]
Inside sum([]):
    returning 0
Inside sum([head|tail]), head=7 tail=[]
    returning 7
Inside sum([head|tail]), head=6 tail=[7]
    returning 13
Inside sum([head|tail]), head=5 tail=[6, 7]
    returning 18

递归和尾调用优化示例

Recursion and Tail Call Optimization Example

functional-programming

elixir