32.13 繰り返しその2

一般に，「変数“i”が“1”から“n”まで動きながら各々順番に処理を行う」という繰り返し処理は，次のようにして再帰関数で書くことができます．

let rec iter(i) =
  if i <= n then
    i番目の処理
    iter(i + 1)
  else 結果;;
iter(1);;

再帰関数“iter”に引数“1”を入れて実行すると，“1番目の処理”の処理が行われて，“iter(2)”に進みます．そこでは“2番目の処理”の処理が行われて，“iter(3)”が呼び出されます．このようにして繰り返しが進み，“n番目の処理”が終わると，次は“iter(n + 1)”ですが条件分岐により繰り返しが終わります．
つまり，繰り返しは必ず再帰関数を使うことで書き表すことができるのです．そこでここでは，この考え方に基づいた繰り返し処理の実現を考えたいと思います．

繰り返しと再帰関数

32.12 繰り返しの例，「1から100までの和」を書き直してみましょう．
前回は再帰関数のように説明しましたが，“1+2+…+99+100”という計算は「“1”に“2”から“100”を順番に足している」と考えるのが普通だと思います．以下では面倒事を減らすために「“0”に“1”から“100”を順番に足している」としますが，いずれにせよこの計算は本質的には繰り返しと言えます．
では，“i番目の処理”に相当するのはどのようなことでしょうか？i番目の足し算は，“1+…+(i-1)”に“i”を足すことです．つまり，“i番目の処理”はひとつ前の結果を受け取って，さらに“i”を足して，その結果を次の処理に渡すということになります．そこで“iter”は順番の“i”だけでなく，ひとつ前の結果を表す“s”も引数に加えて，

let rec iter(i, s) =
  if i <= n then
    iter(i + 1, s + i)
  else s;;
iter(1, 0);;

のように書けばよいことになります．
さらに上では繰り返しの回数“n”をあらかじめ固定しているように考えていますが，「1からnまでの和」を計算する関数“sum”のように後で決められるようにこれも引数にすることで，

let rec sum_iter(i, s, n) =
  if i <= n then
    sum_iter(i + 1, s + i, n)
  else s;;
let sum(n) = sum_iter(1, 0, n);;

によって関数“sum”を書き換えることができます．

こちらでも正しく計算されています．

再帰関数の繰り返し処理化

32.11 再帰関数の定義のフィボナッチ数の計算は再帰関数の典型的な例ですが，これは繰り返しによっても計算することができます．
最初に“0”, “1”があって，そこから次のフィボナッチ数を計算することを繰り返し，後ろ2項に注目するのです．そこでこの後ろ2項を“a_i”と`a_i_1”とおきます（i回目の「次のフィボナッチ数」の計算が終わった時のi番目のフィボナッチ数と(i+1)番目のフィボナッチ数を表しています）．この状態から「次のフィボナッチ数」を計算して後ろ2項を取り直すと，“a_i_1”と“a_i + a_i_1”になっているはずです．そして「次のフィボナッチ数」の計算がn回終わったところで“a_i”を見ると，これがn番目のフィボナッチ数になります．
つまり，

let rec fibonacci_iter(i, a_i, a_i_1, n) =
  if i <= n then
    fibonacci_iter(i + 1, a_i_1, a_i + a_i_1, n)
  else a_i;;
let fibonacci(n) = fibonacci_iter(1, 0, 1, n);;

によって関数“fibonacci”を書き換えることができます．

他にも再帰関数を繰り返しに置き換えられないか考えてみてください．

繰り返しと再帰関数の比較

以上見てきたように，OCamlでは繰り返しを再帰関数によって実現するのですが，その書き方は大きく分けて2つあります．
一方の32.11 再帰関数の定義や32.12 繰り返しでの定義は，今回紹介した方法に比べて，関数の定義が1つで済み，引数を増やす必要はありませんし，プログラムの記述量が少ないです．それに計算の法則性をうまく表していると思います．例えば，32.11 再帰関数の定義での関数“fibonacci”はフィボナッチ数の定義をそのまま書いた感じですが，繰り返しにすると何を計算しているのか一目ではわからないと思います．
他方の繰り返しの利点はなんでしょうか？今回の関数“fibonacci”の関数呼び出しをトレースしてみましょう．

当たり前といえば当たり前ですが，呼び出しは順番に行われて引数“i”の値は1ずつ増加しています．そのため“fibonacci(n)”の計算は“n”に比例する量で済みます．
その一方で32.11 再帰関数の定義でのトレース結果を見ると，“fibonacci(1)”が2回計算されていることがわかります．つまり，計算に無駄があるのです．さらに“n”が大きくなると計算量が爆発的に増大していきます（フィボナッチ数の値だけ関数が呼び出されるので指数関数的に増大します）．
このように，手短かに定義した再帰関数は人間にとってはわかりやすいですが，コンピュータにとってはどう書いても同じでむしろ計算が増えてしまいます．そこで人間が繰り返しに変換することで，効率よく計算できるプログラムにすることができるのです．
以下に整数の和の計算とフィボナッチ数を計算する関数をまとめます．ただし，2つの定義法を区別するために番号をつけているので，コピーして利用するときは注意してください．

(* iteration.ml: 整数の和とフィボナッチ数 *)
(* 再帰的な整数の和の計算 *)
let rec sum1(n) =
  if n = 1 then 1 else sum1(n - 1) + n
(* 繰り返し的な整数の和の計算 *)
let rec sum_iter(i, s, n) =
  if i <= n then
    sum_iter(i + 1, s + i, n)
  else s
let sum2(n) = sum_iter(1, 0, n)
(* 再帰的なフィボナッチ数の計算 *)
let rec fibonacci1(n) =
  if n = 0 then 0 else if n = 1 then 1 else fibonacci1(n - 1) + fibonacci1(n - 2)
(* 繰り返し的なフィボナッチ数の計算 *)
let rec fibonacci_iter(i, a_i, a_i_1, n) =
  if i <= n then
    fibonacci_iter(i + 1, a_i_1, a_i + a_i_1, n)
  else a_i
let fibonacci2(n) = fibonacci_iter(1, 0, 1, n)