再帰再入門

Scala

【この記事はScala Advent Calendar jp 2010 : ATNDの3日目の記事です。】


再帰の話をします。

何やら難しいと思われがちな再帰ですが、
ポイント(というか鉄則を)押さえてしまえばとっても簡単です。

再帰のポイントは2つです。

  • 一段階簡単な問題を考える。
  • 終わりを考える。


たったこれだけ。
「難しい問題を少しずつ簡単にしていくのが再帰」です。
本来、再帰は難しい問題を解くための簡単な手段なのです。

具体的に

1から10までの足し算を再帰でときます。

1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 = ?


まずは再帰のポイントの一つめ

  • 一段階簡単な問題を考える。

に従ってみましょう。

1 から 10 までの足し算よりちょっと簡単な問題は。。。

1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = ?

1 から 9 までの足し算です。


1 から 10 までの和を求めたければ、
1 から 9 までの和を求めて、 それに10を足してやればいいのです。


式にしてみると

sum(10) = sum(9) + 10

ですね。


これを一般化すると

sum(n) = sum(n - 1) + n


scalaのコードにすると

  def sum(n: Int): Int = sum(n - 1) + n

となります。

ヒント

  • 長ーい算数の問題はひとつ短くして考えましょう
  • ScalaのList, List(1, 2, 3, 4, 5) なら、先頭の1を取り出して List(2, 3, 4, 5) について考えてみたり
  • Cの配列だったら、ポインタをひとつずらしてみたり

全部考えなくても良い。

再帰のすばらしいところは1から10まで考える必要がないことです。
n番目とn+1番目の関係を見い出すだけで問題が解けてしまうのです。


ところで、中学校くらいで「数学的帰納法による証明」を習いましたよね。

  • N=0のときに正しいことを示す。
  • N=Mのときに正しければN=M+1にも正しいことを示す。

これも問題の再帰的な性質を利用して、全体は考えずに
N番目とN+1番目に着目して命題を証明する、というものでした。

具体例に話を戻して、

ポイントの2つ目

  • 終わりを考える。

この問題の場合、はnが1になったら和が1、自動的に終わりですね。
その条件を加えてみます。

  def sum(n: Int): Int = {
    if (n = 1)
      1
    else
      sum(n-1) + n
  }

これで、再帰関数完成です。

めでたしめでたし。
と、ここでこのブログエントリをしめくくってしまいたい気持ちはあるのですが、

ちょっとまった。

この関数はnが小さいときはいいのですが、
「計算の途中の式」、が大量にできてしまうため、
nが大きくなるとそのうちスタックを食い潰してしまいます。
試しにやってみましょう。nをばかでかくするとStackOverflowErrorとなります。

末尾再帰

その対策として、scalaでは再帰を「末尾再帰」という形にすることが推奨されます。
「末尾再帰」とは簡単に言うと、
「再帰関数の最後が自分の呼びだしのみになっている」
という状態です。


なぜ末尾再帰にすると良いのでしょうか。
それは末尾再帰はループに書きなおすことができるからです。
末尾再帰の関数を書くと、処理系が内部で勝手にループにしてくれるらしいです。
ループならスタックがあふれることはないですよね。
これを末尾再帰の最適化、と言います。


ちなみに、例えばEmacsLispは、末尾再帰の最適化をしてくれません。
自分はEmacsLispをよく触っているので、末尾再帰？なにそれ？って感じでした。
でもScalaは末尾再帰最適化をしてくれます。

状態変数

ともあれ、末尾再帰にする方法です。
再帰関数の引数に「状態変数」とか「累積変数」とか呼ばれるものを付け足します。

  import scala.annotation.tailrec

  @tailrec
  def sum(n: Int, result: Int = 0): Int = {
    if (n == 1)
      result
    else
      sum(n-1, n + result)
  }


ここではresultが状態変数です。
このresultに計算の途中結果を格納して回します。
こうすれば、再帰的な呼びだしを行なった結果がそのまま結果になります。


これが末尾再帰関数です。
なんかこれが再帰って、変な感じというか、テクいというか。
個人的にはこれあんまり美しくないなあ、さっきのほうがきれいだなあって思うんですが。まあしかたない。


@tailrecは末尾再帰を強制するアノテーションらしいです。
@kirisさんに教えてもらいました。
これをつけると、末尾再帰になっていないとエラーになります。

まとめ

まとめると、scalaで再帰関数を書く場合は、

上述の再帰のポイントに従って再帰関数を書き、末尾再帰にできる場合は末尾再帰に最適化する、

のが定石、ということです。

最後に


再帰関数を書くのは楽しいのですが、
1から10までの和を求めるのに再帰を使うとか、そういうことはやめましょう。


(1 + 10) * 10 / 2 = 5050
1 to 10 sum


適切なアルゴリズムを選ぶのが大事です。