Elixir 简明笔记（十七） --- 控制结构之递归与迭代

计算机顾名思义，执行计算功能。然而通常计算机是通过重复计算得出结果。例如计算从1到100的求和，就是一个个数进行累加。这样的重复性工作，人类显然不太擅长，所以人发明了算法。高斯小朋友就实现了一个等差数列的求和算法。

既然计算机通过快速的重复计算得出结果。那么对数据源进行循环处理就是一种基本的控制结构。经典的循环控制都是通过while，for语句实现。很可惜，elixr中并没有这样的语句。不过不用担心，elixir提供了优雅而强大的递归来进行循环迭代处理。

递归

在函数内调用函数自身即为递归。正常情况下，打印一些一些自然数可以这么写：

# python
In [1]: for i in range(1, 6):
   ...:     print i
   ...:
1
2
3
4
5

In [4]: n = 1

In [5]: while n <= 5:
   ...:     print n
   ...:     n += 1
   ...:
1
2
3
4
5

Elixir 中使用递归则为：

defmodule Nums do

    def print(1), do: IO.puts 1

    def print(n) do
     print(n - 1)
     IO.puts n
    end

end

iex(1)> Nums.print(5)
1
2
3
4
5
:ok

列表递归

Lisp拥有很高的声誉，它本身就是指列表进行计算。前面我们提及，List的实现是链表结构，因此读取列表第一个元素将会很快。elixir还提供了|操作符。下面就使用列表来完成加和计算：

defmodule Math do
    
    def sum([]) do
        0
    end 

    def sum([head|tail]) do
        head + sum(tail)
    end

end


IO.puts Math.sum([1, 2, 3, 4, 5])

尾递归

使用递归来做循环控制是函数式语言的一大特点。别的语言通常在处理递归的时候存在着一个最大递归深度。而elixir对递归在编译上做了优化。当然并不是针对所有递归，而是专门指尾递归（tail recursion）。至于尾递归和递归的差别，可以阅读递归和尾递归。其形式大概就是自己调用自己的时候，并不是作为表达式，大概形式如下：

def original_fun(...) do
    ...
    another_fun(...)    # Tail call 
end

上述加和操作用尾递归重写如下：

defmodule Math do
    
    def sum(list) do
        _sum(list, 0)
    end

    defp _sum([], accumulator) do
        accumulator
    end

    defp _sum([head|tail], accumulator) do
        _sum(tail, head + accumulator)
    end

end


IO.puts Math.sum([1, 2, 3, 4, 5])

更多递归

上述递归的控制基于函数参数的模式匹配，关于条件的控制，还有case和cond宏，下面结合这些控制结构来重写上述的求和计算。

Lisp中常用cond结构，下面情况cond的结果：

defmodule Math do
    
    def sum(list) do
        _sum(list, 0)
    end

    def _sum(list, accumulator) do
        
        cond do
            list == [] -> 
                accumulator
            
            [head|tail] = list -> 
                _sum(tail, head+accumulator)
        end

    end

end


IO.puts Math.sum([1, 2, 3, 4, 5])

再看case的结果：

defmodule Math do
    
    def sum(list) do
        _sum(list, 0)
    end

    def _sum(list, accumulator) do
        
        case list do
            [] -> accumulator
            [head|tail] -> _sum(tail, head + accumulator)
        end
    end
end


IO.puts Math.sum([1, 2, 3, 4, 5])

由此可见，使用递归实现循环控制，遇到条件判断的时候，即可以使用函数参数的模式匹配，也可以使用cond和case方式进行判断。其中cond和case内部逻辑分支也是基于模式匹配。

列表解析

todo

总而言之，使用elixir的递归实现迭代功能，尽量使用尾递归。尾递归经过编译器优化，不会因为调用栈出现问题，也不会引起额外的内存开销。普通递归则会出现最大递归栈的问题。实际上，函数式语言的特点就是函数。在实现循环的功能，Elixir提供了一些高阶函数用来处理，通过这些高阶函数的抽象，隐藏了递归调用的细节。开发者掌握这些高阶函数，更有利于实现功能需求。Enum和Stream提供了大部分所需要的函数，下一节继续探索高阶函数。