日記（日記とは言っていない）

https://zenn.dev/23prime に移行しました。

末尾再帰の最適化に関する勘違いについて

末尾再帰とその最適化はメジャーな話題ですが，メジャーなだけにおかしなことを言っている記事も少なくありません．

某 Qiita 等にテキトーなことを書いて，コメントで指摘が入るというのを30000回ほど見てきました．

今回は，その辺の概念整理を行いたいと思います．

インターネット上の情報を鵜呑みにしてはいけません．
それは，本記事も同じことです．

そもそも末尾再帰ってなに？

末尾再帰とその最適化について，概観します．

はじめに，リファレンスとしてこちらを上げておきます．

http://www.cs.tsukuba.ac.jp/~kam/lecture/fp2017/8.pdf

亀山先生は筑波大学システム情報系の教授で，関数型プログラミング言語，型理論，計算と論理が専門とのことです（公式 HP より）．

このように，それらしいリファレンスを書いておくと，あたかも信憑性のある記事かのように見せられる場合があります．

末尾再帰とは

Wikipedia では，次のように述べられています．

末尾再帰（まつびさいき）とは、再帰的な関数やプロシージャにおいて、自身の再帰呼び出しが、その計算における最後のステップになっているような再帰のパターンのことである。

亀山先生のレジュメには，次のようにあります．

末尾位置における関数呼び出しとは、直観的には、「その関数呼び出しをした後に、もう計算すべきものがない」ということであり、関数呼び出しをした結果が、そのまま、現在の関数の答えになる場合である。

だいたい同じことを言っているのがおわかりかと思います．

末尾再帰の実装例

例として，亀山先生のレジュメの sum 関数を，Haskell で書いてみます．

  • 末尾再帰でない直感的な実装
sumRec :: Integer -> Integer
sumRec 0 = 0
sumRec x = x + sumRec (x - 1)

sumRec' :: Integer -> Integer
sumRec' x = sumAux x 0
  where
    sumAux :: Integer -> Integer -> Integer
    sumAux 0 s = s
    sumAux x s = sumAux (x - 1) (s + x)

上述の末尾再帰の説明に対し，1つ目の実装は合致せず，2つ目の実装は合致していることが直ちにわかるかと思います．

「1つ目の実装だって定義の一番最後に再帰呼出しがあるじゃん！」という方は，よく説明を読み直してください．

末尾再帰の最適化とは

通常，再帰呼出しを行うと，その度に新たなメモリ（通常は stack 領域） が使用されます．
結果，油断すると簡単に stack overflow します．

これを避けるため，一定の条件下において「最適化」を行うことが可能です．

末尾再帰の形というのは比較的容易に最適化を行えるため，現在多くの処理系において実装されています． Haskell のメジャーな処理系である GHC もその一つです．

この最適化の手法について詳しくは，先程のレジュメをリファレンスしてください．
ループでイメージするならば，上の sumAux の第1引数 x がループのカウンタ，第2引数 s がループごとに変更される変数に対応していると思うといいかもしれません．

実際，上の sumRec sumRec' に対し，次を実行してみます．

main :: IO ()
main = print $ sumRec 100000000

すると，手元の環境において sumRec では stack overflow しますが，sumRec' の方は数秒程度できちんと結果が返ってきます．

本題：よくある勘違いについて

本題に移ります．

末尾再帰の最適化の例として，「フィボナッチ数の計算」を見かけます．だいたい次のような実装になっています．

fib :: Integer -> Integer
fib 0 = 1
fib 1 = 1
fib n = fib (n - 1) + fib (n - 1)

fib' :: Integer -> Integer
fib' n = subFib n 1 1
  where
    subFib :: Integer -> Integer -> Integer -> Integer
    subFib 0 _ _ = 1
    subFib 1 x _ = x
    subFib n x y = subFib (n - 1) (x + y) x

事実と見落とし

次のことは概ね事実といって過言ではなく，かつ勘違い記事にも書いてあることが多い内容です．

  • fib の再帰は末尾再帰でなく， fib' の再帰は末尾再帰である．
  • fib は fib' に比べて大きな実行時間を要し，簡単に stack overflow する．
  • fib' では末尾再帰で書き直したことで，ローコストになった．
  • fib' では末尾再帰の最適化によって，ローコストになった．

しかしながら，これだけでは重大な見落としがあります．

  • fib よりも fib' の方が， アルゴリズムレベルで時間・空間ともにローコスト である．
  • 末尾再帰の最適化よりも，アルゴリズムの改変の方が実行コストに（遥かに）大きく寄与している．

というところです．

言い換えれば，仮に fib' において最適化を行わずとも， fib に比べれば（遥かに）ローコストだということです．

結局何が勘違いなのか

「最適化のおかげ（だけ）で圧倒的に早くなった！末尾再帰すげー！」というのが勘違いです．

つまり？

最適化はあくまで最適化であり，アルゴリズムレベルでのローコスト化とは本区別されるべきものです．
しかし，いずれも実コストに大きな影響を与える場合があるという点においては共通しており，このことが話をややこしくしているのかもしれません．

偏見

「実装経験はあるけどアルゴリズムについて勉強したことがない人」が陥りそう．

結論

ループで書こう．