ループと末尾再帰

再帰から末尾再帰への書き換えは構造が変わるためやや飛躍があるように感じます。それに対してループから末尾再帰への書き換えは形式的に行えることを、順を追って説明します。

シリーズの記事です。

1. ループと末尾再帰 ← この記事
2. CPS 変換による末尾再帰化
3. CPS 変換から継続モナドへ

この記事のコードをまとめました。

概要

末尾再帰でループを書くことの基本的な発想は以下の 2 点です。

• for や while などのループは関数の再帰呼び出しで代用できる。
• 変数の書き換えは引数に渡すことで代用できる。

これについて階乗とフィボナッチ数列を例に説明します。

【注意】JavaScript で敢えてループを末尾再帰で書く必要性は特にありません。この記事は考え方を説明するのが目的です。

階乗

階乗は 1 から指定した数までの積です。

5!=1×2×3×4×5

ループ

ループで階乗を求めます。

function fact_for(n) {
  let a = 1;
  for (let i = 2; i <= n; i++) {
    a *= i;
  }
  return a;
}

使用例

> fact_for(5)
120

※ a の値を書き換えながら求める結果を作っていることを意識しておいてください。

while

for を while で書き換えます。

function fact_while(n) {
  let a = 1;
  let i = 2;
  while (i <= n) {
    a *= i;
    i++;
  }
  return a;
}

※ 使用例は同じなので省略します。

変数への代入をまとめて行うように書き換えます。処理内容は同じです。

function fact_while(n) {
  let [a, i] = [1, 2];
  while (i <= n) {
    [a, i] = [a * i, i + 1];
  }
  return a;
}

末尾再帰

末尾再帰に書き換えます。

function fact_tailrec(n) {
  return loop(1, 2);
  function loop(a, i) {
    return i <= n ? loop(a * i, i + 1) : a;
  }
}

while と比較すれば、変数への代入は行わずに引数として渡していることが分かります。計算の中間結果を保持する引数 a はアキュムレーターと呼ばれますが、ループの段階で既に使っていることに注意してください。

再帰が字面上の末尾にあるかどうかは本質ではなく、再帰から戻った後に値をそのまま返すかどうかが重要です。

※ 末尾に置いた方が座りが良いので、そうしたければ条件を反転させて書き換えます。（本質ではないのに注意）

  function loop(a, i) {
    return i > n ? a : loop(a * i, i + 1);
  }

非末尾再帰

再帰の例として階乗はよく取り上げられます。

function fact(n) {
  return n <= 1 ? 1 : fact(n - 1) * n;
}

fact(n - 1) * n は再帰呼び出しから戻った後に n を掛けています。再帰の過程で n が 1 へと減少していきますが、実際の計算は再帰から戻るときに行われるため 1 から順番に掛けています。

再帰を往路と復路に分けて考えると、fact(1) が中間地点となります。往路で n が 1 に向かって減少し、1 で折り返して、復路で計算が行われます。復路は n が 1 から増加していく過程なので、実際の計算は 1 から始めるループと同じ順序で行われます。

往路	fact(5) → fact(4) * 5 → (fact(3) * 4) * 5 → ((fact(2) * 3) * 4) * 5 → (((fact(1) * 2) * 3) * 4) * 5
復路	→ (((1 * 2) * 3) * 4) * 5 → ((2 * 3) * 4) * 5 → (6 * 4) * 5 → 24 * 5 → 120

末尾再帰は復路がない特別な再帰だと言えます。

往路	fact_tailrec(5) → loop(1, 2) → loop(1 * 2, 3) → loop(2 * 3, 4) → loop(6 * 4, 5) → loop(24 * 5, 6) → 120

※ 非末尾再帰で往路と復路に別れた処理が、末尾再帰では往路だけで行われています。

ループから末尾再帰への書き換えは機械的に行えましたが、非末尾再帰は構造が異なるため別枠で考えた方が良いでしょう。

※ 非末尾再帰は数学での漸化式をコードで表現するのに対して、末尾再帰はループと同様に手続きを記述していると言えます。

一般的に非末尾再帰の方が抽象度が高くてコードが簡潔にはなりますが、何の工夫もしないと計算量的には不利になる傾向があります。

読み方のコツ

再帰を読むときに頭の中でトレースすると混乱するので、正しい結果が返って来ると仮定して、再帰を追わない方が無難です。

たとえば fact(n - 1) * n は、n = 5 の場合に fact(4) * 5 となりますが、fact(4) は正しい結果が返って来ると考えて、それ以上追わないということです。

注意事項

再帰が字面上の末尾にあるかどうかは本質ではないと書きました。

もし再帰を以下のように書いたとしても、末尾再帰ではありません。

function fact(n) {
  return n <= 1 ? 1 : n * fact(n - 1);
}

再帰から戻った後に n を掛けるという処理が残っています。

※ 復路があると言えます。

フィボナッチ数列

最初の 2 つの数字を 1, 1 と決めて、3 番目以降は直前の 2 つの数字を足して生成する数列です。

1,  1,  2,  3,  5,  8,  13, ...
-------------------------------
1 + 1 = 2
    1 + 2 = 3
        2 + 3 = 5
            3 + 5 = 8
                5 + 8 = 13

ループ

最初から順番に計算します。

function fib_for(n) {
  let a = 1;
  let b = 1;
  for (let i = 3; i <= n; i++) {
    const tmp = a + b;
    a = b;
    b = tmp;
  }
  return b;
}

使用例

> fib_for(3)
2
> fib_for(4)
3
> fib_for(5)
5
> fib_for(6)
8

代入をまとめると一時変数 tmp が不要になります。

function fib_for(n) {
  let [a, b] = [1, 1];
  for (let i = 3; i <= n; i++) {
    [a, b] = [b, a + b];
  }
  return b;
}

※ アキュムレーターは a と b の 2 つだと考えられます。

while

function fib_while(n) {
  let [a, b, i] = [1, 1, 3];
  while (i <= n) {
    [a, b, i] = [b, a + b, i + 1];
  }
  return b;
}

末尾再帰

function fib_tailrec(n) {
  return loop(1, 1, 3);
  function loop(a, b, i) {
    return i <= n ? loop(b, a + b, i + 1) : b;
  }
}

慣れれば形式的な書き換えです。

非末尾再帰

再帰の例としてフィボナッチ数列もよく取り上げられます。

function fib(n) {
  return n <= 2 ? 1 : fib(n - 2) + fib(n - 1);
}

ループとは単に書き方が異なるという以上の違いがあり、処理効率が大きく異なります。再帰が分岐しているため、同じ計算を何度も繰り返すことになって計算量が爆発します。

階乗のように一本道ではありませんが、便宜上、往路と復路に分けて示します。

往路	fib(5) → fib(3) + fib(4) → fib(3) + (fib(2) + fib(3)) → (fib(1) + fib(2)) + (fib(2) + (fib(1) + fib(2)))
復路	→ (1 + 1) + (1 + (1 + 1)) → 2 + (1 + 2) → 2 + 3 → 5

fib(3) が 2 個所で現れるため、そこから先の計算が繰り返されます。元の引数が大きくなれば計算量が爆発します。

最適化にはメモ化など動的計画法が利用されます。詳細は以下を参照してください。

分岐しない版

※ 実用的な意味はありませんが、参考までに掲載します。

階乗と同じように再帰が分岐しない一本道で書くことはできます。

function fib2(n) {
  return g(n)[1];
  function f([a, b]) { return [b, a + b]; }
  function g(n) { return n <= 2 ? [1, 1] : f(g(n - 1)); }
}

中間過程で値を 2 つ返して、最後に絞ります。

往路	fib2(5) → g(5)[1] → f(g(4))[1] → f(f(g(3)))[1] → f(f(f(g(2))))[1]
復路	→ f(f(f([1, 1])))[1] → f(f([1, 2]))[1] → f([2, 3])[1] → [3, 5][1] → 5

実用的には末尾再帰にすれば良いのですが、こういった書き換えも練習には面白いと思ったので紹介しました。