もしかしたら末尾再帰って簡単なんじゃないか？という話 #Haskell

ここ数日悩み続けていた末尾再帰について, もしかしたら意外と簡単なんじゃないかという答えが出たのでまとめておきます.
Haskellによる末尾再帰の情報は思いの外少なく, かなり苦戦しました.
例によって書いてるのは初心者です. 間違い等あればご指摘頂けるとありがたいです. 

##末尾再帰とは何ぞや？という話

> 末尾再帰（まつびさいき）とは、再帰的な関数やプロシージャにおいて、自身の再帰呼び出しが、その計算における最後のステップになっているような再帰のパターンのことである。再帰にかかわらず一般に、そのような最後の呼び出しを末尾呼び出し （en:Tail call）という。呼び出しではなく、戻り先を保存しないジャンプに最適化できるという特徴がある。

出典:Wikipedia日本語版 [末尾再帰](https://ja.wikipedia.org/wiki/末尾再帰)

だそうです.

普通の再帰にするとスタックを馬鹿食いするので, 処理が重くなるらしい.
一方, 末尾再帰にすると使うスタックの量が減るので, 処理がとても軽いとのこと.
実際, 体感で重いなと感じる程には差が出ていました. 

##再帰の例

###階乗

再帰の例によく用いられる階乗を作っていきたいと思います.

```hs:fact.hs
fact :: Int -> Int
fact 0 = 1
fact n = n * (fact $ n - 1)
```

これに例えば4を引数に渡すと, 

```hs:実行過程
fact 4
↓
4 * (fact 3)
↓
4 * (3 * (fact 2))
↓
4 * (3 * (2 * (fact 1)))
↓
4 * (3 * (2 * (1 * (fact 0))))
↓
4 * (3 * (2 * (1 * (1))))
↓
4 * (3 * (2 * (1)))
↓
4 * (3 * (2))
↓
4 * (6)
↓
24
```

このような演算過程を経て, 階乗の結果を得られる事ができます.
一通り広げ晒してから演算を行うため, 処理は重くなります.

次に末尾再帰版です. 

```hs:fact_TailCall.hs
fact :: Int -> Int
fact n = fact' n 1
    where
        fact' 0 y = y
        fact' x y = fact' (x - 1) (x * y)
```

こちらにも同様に4を渡してみます. 

```hs:実行過程
fact 4
↓
fact' 4 1
↓
fact' 3 4
↓
fact' 2 12
↓
fact' 1 24
↓
fact' 0 24
↓
24
```

こうなります. 
処理数も少なく, 一度出てきた演算はその時に終わらせているので非常に軽いです.

##末尾再帰の考え方

僕の中で出た結論は, **手続き型の時同様に考える**でした. 
手続き型言語でwhile文やfor文を使って計算する, あの時と同じ感覚です. 

具体的に説明していきます. 

```cpp:fact.c
int fact(int num) {
    int result = 1;
    while (num) {
        result = result * num; //再帰のように見せるため, あえて*=は使用せずこちらの書き方にしています
        num--;
    }
    return result;
}
```

手続き型的に書くとこうなりますね.
これとほぼ同じ考え方で行けるんです.

この手続き型のプログラムの中には

- カウンタ
- 演算に必要な値
- 計算結果

の3つがあります.
今回の場合は, 

- カウンタ →`num`
- 演算に必要な値 → `num`
- 計算結果 → `result`

となっています.
今回は階乗なので演算に必要な値とカウンタは同一の変数です.
やってる内容としては,

1. 計算結果入力用の変数`result`を単位元で初期化
2. 計算結果入力用の変数`result`と演算に必要な値`num`を掛け合わせ, 結果を計算結果入力用の変数`result`に代入
3. カウンタ`num`を1減らす

これをカウンタが０になるまで繰り返してるだけですね.
じゃあこれを, 引数の中でやればいいんです.
もう一度末尾再帰版をお見せします. 

```hs:fact_TailCall.hs
fact :: Int -> Int
fact n = fact' n 1
    where
        fact' 0 y = y
        fact' x y = fact' (x - 1) (x * y)
```

1. まずは演算に必要な値であり, カウンタでもある定数`n`を`fact`の引数から受け取り, ローカル関数`fact'`の第1引数`x`に渡し, `fact'`の第2引数である計算結果入力用の引数`y`を単位元で初期化する
2. 自分自身を再帰呼び出しし, カウンタ`n`を`1`減らした値を第1引数`x`に, 演算に必要な値`x`と計算結果入力用の引数`y`を掛け合わせた結果を第2引数に渡す

これを繰り返し, カウンタ`n`が`０`になれば第2引数`y`を計算結果として返しているだけです.

どうですか？
この考え方, かなり手続き型ちっくな気がしませんか？

##他の例

###累乗

次は累乗を求める関数`pow`です.

```hs:pow_TailCall.hs
pow :: Int -> Int -> Int
pow a b = pow' a b 1
    where
        pow' a 0 c = c
        pow' a b c = pow' a (b - 1) (a * c)
```

`pow`の場合は演算に必要な値とカウンタがそれぞれ違うため, 引数がもう1つ増えます.
ですが, 引数が増えただけでやっている事は基本的に同じです.

1. まずは演算に必要な値`a`を`pow`の第1引数から受け取り, ローカル関数`pow'`の第1引数に渡し, カウンタである定数`b`を`pow`の第2引数から受け取り, ローカル関数`pow'`の第2引数`x`に渡す. `pow'`の第3引数である計算結果入力用の引数`y`は単位元で初期化する
2. 自分自身を再帰呼び出しし, 演算に必要な値`a`は不変なのでそのまま第引数に渡し, カウンタ`b`を`1`減らした値を第2引数`x`に, 演算に必要な値`a`と計算結果入力用の引数`c`を掛け合わせた結果を第3引数に渡す


これを繰り返し, カウンタ`b`が`０`になれば第1引数`a`を計算結果として返します.
実行過程は以下の通りです.

```hs:実行過程
pow 2 4
↓
pow' 2 4 1
↓
pow' 2 3 2
↓
pow' 2 3 4
↓
pow' 2 1 8
↓
pow' 2 0 16
↓
16
```


###フィボナッチ数列

最後にフィボナッチ数列です.
きっと僕はこれを記事の中に書かないと落ち着かないんです.

ここまで来るともうきっと読めるはずですし, 見る前にも書けるんじゃないでしょうか？

```hs:fib_TailCall.hs
fib n = fib' n 1 1
    where
        fib' n x y
            | n == 0 = 1
            | n == 1 = x
            | otherwise = fib' (n - 1) (x + y) (x)

```

実行過程は以下の通りです.

```hs:実行過程
fib 5
↓
fib' 5 1 1
↓
fib' 4 2 1
↓
fib' 3 3 2
↓
fib' 2 5 3
↓
fib' 1 8 5
↓
8
```

どうでしたか？
思っていたより簡単だったんじゃないでしょうか？

実際にはこれよりもっと速い実装もあるらしいのですが, 今の僕にはまだ分かりません.
ここはこうした方が良い, 等の意見がありましたら是非コメントで教えて頂けるとありがたいです.