31.12 繰り返しその2

一般に，「変数 “i” が “1” から “n” まで動きながら各々順番に処理を行う」という繰り返し処理は，hwb31.9 繰り返しで見た通り，

for(int i = 1; i <= n; i++) {
  i番目の処理
}

と書くのですが，次のようにして再帰関数でも書くことができます．

public static void iter(int i) {
  if(i <= n) {
    i番目の処理
    iter(i + 1);
  }
}

iter(1);

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

繰り返しと再帰関数

hwb31.9 繰り返しの例，「1 から 100 までの和」を書き直してみましょう．
“for” にあたる部分を再帰メソッドにするため，その中で使われる変数 “n” と “s” はメソッドと同列にして次のように書きます．

// Program.java : 整数の和 class Program { public static int n; public static int s; public static void sum_iter(int i) { if(i <= n) { s = s + i; sum_iter(i + 1); } } public static int sum(int n) { Program.n = n; s = 0; sum_iter(1); return s; } public static void main(String[] args) { System.out.println(sum(10)); System.out.println(sum(100)); } }

55 5050

なお，メソッド “sum” で “Program.n” と書いているのは変数 “n” が “Program” に属するものと引数の 2 種類あるためです．単純に “n” と書くと引数が参照されて，“Program” に属する（“static” をつけた）変数・メソッドは “Program.” と前につけることで確実に参照することができます．
こうして繰り返しは機械的な変換で再帰関数に書き換えられるのですが，ソースコードを複雑にするだけなので普通は “for” などを使うとよいでしょう．もしくは再帰関数の特性を活かした書き方にします．今回の例では次のようにして考えます．
今回の “1 から 100 までの和” ですが，これは “1から99までの和” に “100” を足したものになっています．さらに “1 から 99 までの和” というのは，“1 から 98 までの和” に “99” を足したものです．
つまり，この和を求める計算は次のように考えることができます．

  • “1 から 100 までの和” は “1 から 99 までの和” と “100” を足したもの．
  • “1 から 99 までの和” は “1 から 98 までの和” と “99” を足したもの．
  • “1 から 98 までの和” は “1 から 97 までの和” と “98” を足したもの．
  • …
  • “1 から 2 までの和”は  “1 から 1 までの和” と “2” を足したもの．
  • “1 から 1 までの和” は…“1” に決まっている！

よく見ると，最後を除けば同じ形をしていますね．ですから，この考え方は次のように書くこともできます．

  • “1 から n までの和”は “1 から (n-1) までの和” と “n” を足したもの．
  • “1 から 1 までの和”は…“1” に決まっている！

なので再帰関数を使って次のように “sum(n)” を計算することができます．

// Program.java: 再帰的な整数の和の計算 class Program { public static int sum(int n) { if(n == 1) { return 1; } else { return sum(n - 1) + n; } } public static void main(String[] args) { System.out.println(sum(10)); System.out.println(sum(100)); } }

55 5050

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

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

hwb31.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 番目のフィボナッチ数になります．
つまり，

public static int fibonacci(int n) {
  int a_i = 0;
  int a_i_1 = 1;
  for(int i = 1; i <= n; i++) {
    int c = a_i;
    a_i = a_i_1;
    a_i_1 = c + a_i_1;
  }
  return a_i;
}

によってメソッド “fibonacci” を書き換えることができます．ただし，途中で “int c = a_i;” としているのは，次の行で “a_i” が変わるがその次の “a_i_1” の計算ではもとの値を使いたいため，いったん変数 “c” に “a_i” の値を記録しています．

// Program.java: 繰り返し的なフィボナッチ数の計算 class Program { public static int fibonacci(int n) { int a_i = 0; int a_i_1 = 1; for(int i = 1; i <= n; i++) { int c = a_i; a_i = a_i_1; a_i_1 = c + a_i_1; } return a_i; } public static void main(String[] args) { System.out.println(fibonacci(3)); System.out.println(fibonacci(8)); } }

2 21

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

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

以上見てきたように，繰り返しと再帰関数は相互に書き換えられたりするのですが，その特徴には違いがあります．
一方の再帰関数は，繰り返しに比べて，うまく書くことでプログラムの記述量が少なくすることができます．それに計算の法則性をうまく表していると思います．例えば，hwb31.11 再帰関数の定義でのメソッド “fibonacci” はフィボナッチ数の定義をそのまま書いた感じですが，繰り返しにすると何を計算しているのか一目ではわからないと思います．
他方の繰り返しの利点はなんでしょうか？当たり前といえば当たり前ですが，“for” を使った繰り返しは回数が決まっています．そのため “fibonacci(n)” の計算は “n” に比例する量で済みます．その一方でhwb31.11 再帰関数の定義での呼び出しを見ると，“fibonacci(1)” が 2 回計算されていることがわかります．つまり，計算に無駄があるのです．さらに “n” が大きくなると計算量が爆発的に増大していきます（フィボナッチ数の値だけメソッドが呼び出されるので指数関数的に増大します）．
このように，手短かに定義した再帰関数は人間にとってはわかりやすいですが，コンピュータにとってはどう書いても同じでむしろ計算が増えてしまいます．そこで人間が繰り返しに変換することで，効率よく計算できるプログラムにすることができるのです．