Elixir入門 09: 再帰
Tags: elixir, webdev, tutorial, programming
Published: 2018-11-13 01:24:25

---
title: Elixir入門 09: 再帰
published: true
description: Elixir公式サイトの許諾を得て「Recursion」の解説にもとづき、加筆補正を加えてElixirにおける関数の再帰呼び出しについてご説明します。
tags: #elixir, #webdev, #tutorial, #programming
---

本稿はElixir公式サイトの許諾を得て「[Recursion](https://elixir-lang.org/getting-started/recursion.html)」の解説にもとづき、加筆補正を加えてElixirにおける関数の再帰呼び出しについてご説明します。

# 再帰によるループ
Elixirはデータがイミュータブルなので、他の関数型プログラミング言語と同じく、ループ処理の書き方は命令型プログラミング言語と異なります。たとえば、C#のような命令型言語では、配列要素の取り出しをつぎのように処理するでしょう。

```c#
for (i = 0; i < sizeof(array); i++) {
  array[i] = array[i] * 2;
}
```

上の例では配列とカウンタ変数のデータが書き替えられます。Elixirはイミュータブルですのでデータは変えられません。そこで、関数型言語では再帰を使うのです。関数がみずからを再帰的に呼び出してループさせるのです。呼び出ししない条件に達したとき、再帰が終わります。このやり方であれば、データが変わりません。

以下の関数はリストの要素数を数えて返します。関数はふたつの句を備え、引数でパターンマッチングされます。リストが空なら、ひとつ目の関数とマッチするので、0が返され再帰呼び出しはしません。これが終了条件になります。

リストに要素があれば、テイルを渡して再帰呼び出しし、その戻り値に1を加えます。つまり、再帰呼び出しされるたびに1ずつカウントアップされ、空になったとき再帰は止まって合計値が返されるのです。

```elixir
defmodule Length do
  def of([]), do: 0
  def of([_ | tail]), do: 1 + of(tail)
end
```

```elixir
iex> Length.of []
0
iex> Length.of [1, 2, 3]
3
```

なお、ふたつ目の関数でヘッドの変数は処理に使われません。使われない変数の頭にはアンダースコア`_`を添えるのがElixirの[命名規則](https://hexdocs.pm/elixir/naming-conventions.html#underscore-_foo)です。`_`で始まる変数に納めた値を取り出そうとすると警告が示されます。さらに、`_`のみを変数にしたとき、値の取り出しはコンパイルエラーになります。

```elixir
iex> _x = 0
0
iex> _x
warning: the underscored variable "_x" is used after being set. A leading underscore indic
ates that the value of the variable should be ignored. If this is intended please rename t
he variable to remove the underscore

0
iex> _ = 1
1
iex> _
** (CompileError) iex:n: invalid use of _. "_" represents a value to be ignored in a patte
rn and cannot be used in expressions
```


# reduceとmapのアルゴリズム
まず、前掲のリストの要素数が返される関数を手直しして、要素の数値を合計してみましょう。関数に数値の第2引数を加え、ヘッダでデフォルト値0を与えました。加算される合計値を引数で受け渡せば、イミュータブルは破りません。

ひとつ目の関数は、リストが空になったら引数の合計値を返して、再帰呼び出しは終わります。空でなかったらふたつ目の関数が、テイルと合計値を引数に再帰呼び出しして、ヘッドの値を加えます。つまり、つまり再帰のたびにヘッドの値を合計値に加えていくことになるのです。

```elixir
defmodule Sum do
  def up(list, accumulator \\ 0)
  def up([], accumulator), do: accumulator
  def up([head | tail], accumulator),
    do: up(tail, head + accumulator)
end
```

```elixir
iex> Sum.up([1, 2, 3])
6
iex> Sum.up([4, 5], 6)
15
```

リストから要素を順に取り出して、ひとつの値にまとめる処理はreduceアルゴリズムと呼ばれ、関数型プログラミングの重要な考え方のひとつです。

つぎは、リスト要素に処理を加えて、新たなリストにつくりかえます。つぎの関数はリスト要素の数値を2乗して、それらが要素に納められた新たなリストとして返します。なお、`|`はふたつのリストをひとつにつなげる演算子にもなるのです(「[Elixir入門 04: パターンマッチング](https://dev.to/gumi/elixir-04--1346)」「演算子によるパターンマッチング」参照)。このようにリスト要素を取り出して、新たなリスト要素に納めて返す処理はmapアルゴリズムと呼ばれます。

```elixir
defmodule Sum do
  def square([]), do: []
  def square([head | tail]), do:
    [head * head | square(tail)]
end
```

```elixir
iex> Sum.square([1, 2, 3])
[1, 4, 9]
```

再帰と末尾呼び出しの最適化はElixirの重要なポイントで、ループ処理をするときにも活用されます([末尾再帰](https://ja.wikipedia.org/wiki/%E6%9C%AB%E5%B0%BE%E5%86%8D%E5%B8%B0)参照)。もっとも、Elixirのプログラミングでは、リストの操作に再帰を用いることはほとんどないでしょう。

[`Enum`モジュール](https://hexdocs.pm/elixir/Enum.html)に、リストで使える便利な機能がすでに用意されているからです。たとえば、関数[`Enum.reduce/3`](https://hexdocs.pm/elixir/Enum.html#reduce/3)や[`Enum.map/2`](https://hexdocs.pm/elixir/Enum.html#map/2)はつぎのように用います。

```elixir
iex> Enum.reduce([1, 2, 3], 0, fn(x, acc) -> x + acc end)
6
iex> Enum.map([1, 2, 3], fn(x) -> x * x end)
[1, 4, 9]
```

さらに、キャプチャ構文でもっと短くも書けます。

```elixir
iex> Enum.reduce([1, 2, 3], 0, &+/2)
6
iex> Enum.map([1, 2, 3], &(&1 * &1))
[1, 4, 9]
```

#### Elixir入門もくじ
- [Elixir入門 01: コードを書いて試してみる](https://dev.to/gumi/elixir-01--2585)
- [Elixir入門 02: 型の基本](https://dev.to/gumi/elixir-02--30n1)
- [Elixir入門 03: 演算子の基本](https://dev.to/gumi/elixir-03--33im)
- [Elixir入門 04: パターンマッチング](https://dev.to/gumi/elixir-04--1346)
- [Elixir入門 05: 条件 - case/cond/if](https://dev.to/gumi/elixir-05----casecondif-60o)
- [Elixir入門 06: バイナリと文字列および文字リスト](https://dev.to/gumi/elixir-06--35na)
- [Elixir入門 07: キーワードリストとマップ](https://dev.to/gumi/elixir-07--39hi)
- [Elixir入門 08: モジュールと関数](https://dev.to/gumi/elixir-08--1c4c)
- Elixir入門 09: 再帰
- [Elixir入門 10: EnumとStream](https://dev.to/gumi/elixir-10-enumstream-4fpb)
- [Elixir入門 11: プロセス](https://dev.to/gumi/elixir-11--2mia)
- [Elixir入門 12: 入出力とファイルシステム](https://dev.to/gumi/elixir-12--4og6)
- [Elixir入門 13: aliasとrequireおよびimport](https://dev.to/gumi/elixir-13-aliasrequireimport-55c1)
- [Elixir入門 14: モジュールの属性](https://dev.to/gumi/elixir-14--3511)
- [Elixir入門 15: 構造体](https://dev.to/gumi/elixir-15--4f43)
- [Elixir入門 16: プロトコル](https://dev.to/gumi/elixir-16--lif)
- [Elixir入門 17: 内包表記](https://dev.to/gumi/elixir-17--5gci)
- [Elixir入門 18: シギル](https://dev.to/gumi/elixir-18--5791)
- [Elixir入門 19: tryとcatchおよびrescue](https://dev.to/gumi/elixir-19-trycatchrescue-50i8)
- [Elixir入門 20: 型の仕様とビヘイビア](https://dev.to/gumi/elixir-20--j50)
- [Elixir入門 21: デバッグ](https://dev.to/gumi/elixir-21--21a1)
- [Elixir入門 22: Erlangライブラリ](https://dev.to/gumi/elixir-22-erlang-2492)
- [Elixir入門 23: つぎのステップ](https://dev.to/gumi/elixir-23--50ik)

##### 番外
- [Elixir入門: Plugを使うには](https://dev.to/gumi/elixir-plug-40lb)