再帰のイメージ

苦手な再帰をもう一度基本的なところから考えてみたい。 (+_+)

何でもイメージを浮かべないと考えることができない性質なので、「再帰的」に問題を解決できそうな雰囲気を感じたら、最近では心にあるイメージを浮べることにしている。再帰という抽象概念を `もの’ として手に触れることができる位置に置き、感触を確かめることによりやっと目の前の霧が少しずつ晴れていく。そんな契機になるように。

 

例

抽象的なイメージを考える前に、最初に次のような簡単な例を考える。

「1 から n までの自然数の合計を求めたい。」

 

考え方

このとき再帰的に関数を定義するなら、自分の場合、次のような手順で考える。

まずは、関数名を適当に `sum1to n’ と名付ける。

そして、 sum1to n を、とりあえず「1 から n までの自然数の合計」であると見なす。 (@_@) じぃ～。ただし、今はそれをどうやって定義すればいいのかわからない。

次に sum1to n なるものがあるとして、そこから見て小さい方へ目を向ける。例えば、sum1to n より一つだけ小さいものは 、

sum1to (n-1)

これは「1 から n-1 までの合計」を表わす。しかし、相変わらず sum1to n の定義はわからないし、当然ながら sum1to (n-1) もどうやって求めるのかわからない。 (+_+) ん～～

しかし、ここで上図を見ると、以下の二つが等しいことがわかる。 (@_@) おっ！

• sum1to n
• sum1to (n-1) に n を足したもの

別の言い方をするなら、sum1to (n-1) に n を足すと、sum1to n になるということ。

sum1to n = sum1to (n-1) + n

 

さて、これで求める定義はできたのだろうか？例えば「1 から 999 までの自然数の合計を求めたい」とする。このとき、上記の定義に当てはめれば、

sum1to 999 = sum1to (999-1) + 999

「sum1to 998 に 999 を足したものが sum1to 999」ということに。言い換えれば「1 ~ 998 の合計に 999 を足したもの」。では、「1 ~ 998 までの合計は？」と言ったら、1 ~ 997 までの合計に 998 を加えたもの。 「1 ~ 997 は？」 … といつまでたってもキリがない。つまり値が定まらない。

 

ところで、求めたいのは「1 から n までの自然数の合計」だった。例えば n が 1 のときはどうだろう？

「1 から 1 までの自然数の合計を求める」

これは考えるまでもなく明らかに 1 。なぜなら、一つのものを合計するのにそれ以上何か操作する必要がないため。そのものの値が求める答えに一致する。ということは、上記で定義した sum1to n = sum1to (n-1) + n を必要とすることなく、次のように定義することができる。

sum1to 1 = 1

これにより、例えば「1 から 2 までの自然数の合計を求める」場合の値が定まる。

sum1to 2 = sum (2-1) + 2
sum1to 2 = sum 1 + 2
sum1to 2 = 1 + 2
sum1to 2 = 3

この操作を 1 から順に繰り返していくことによって 999 まで辿り着けば、「1 から 999 までの自然数の合計」が求まる。

 

「基本コンポーネント」と「拡張する操作」

sum1to n の定義に戻る。

sum1to n = sum1to (n-1) + n

先ほどは、sum1to n が「何から構成されているか」という視点から定義を考えた。これを例えば、次のように書けるとしたら、(もちろん Haskell において文法エラーだけれど)

(sum1to n) - (sum1to (n-1)) =  + n

+ n の意味がより明確になる。つまり、これは sum1to n と sum1to (n-1) の違いが何に由来しているかを示している。上の例の場合、n を足すことにより両者の違いが生じる。また、それは n の値がどのように変化しても、その一つ前の n–1 の状態から、どのように変化すれば n の状態になれるのかを表現している。

ところで、n = 1 のときは上記の式を必要とせず、それのみで存立できる。たとえるなら、`1’ が核となり、それに衣を被せるようにして sum1to n は n ずつ大きく拡張されていく。つまり、sum (n-1) + n は sum1to が一回り大きくなる方法がについて書かれていると見なせる。

 

ここから再帰のイメージとして次のようなものが思い浮かんだ。

先ほどの例で言えば、「基本コンポーネント」に当たるのが `1’ で、これがある操作によってどんどんと拡張していくという構図。基本コンポーネントの周りにある線が拡張する様を表現。ある操作というのは、上の例の場合では n-1 の状態から n へと変化するための方法を表わし、具体的には一つ前の状態に n を加えることに相当する。

このように、中心に「基本コンポーネント」となるものがあり、それを「変化・拡張する操作」という二つのことを考えることによって、再帰的な構造をとらえることができる。

 

関数を定義をするときのポイント

とは言っても、相変わらず上手く関数を定義することができないのだけれど (+_+) 、現時点で重要だと思うポイントは 2 点ある。

1. 定義しようとする関数の意味を予めはっきりとさせておく。
2. 定義しようとしている途中でも、既に定義されていると仮定して、関数の適用をしてしまう。

(1) は、なんとなくぼんやりと関数を定義していると、それが何を表わしているかわからないため、再帰的な適用を考えることができなくなる。定義をする前に「これを適用すると、こういう結果になる」とはっきりとしたイメージを持っておくこと。ただし、定義の内容まで踏み込んで考えておく必要はない。

(2) は (1) が前提とされるが、関数を定義する際、「まだこの関数の定義は終ってないけれど、既に定義されたものと考えて、適用したらこういう結果になるはずだから…」というように、未完のものを既に完成されものと見なして関数を定義していくということ。