スパイたちに告ぐ根性論:間違わなければ学べない

2016年07月25日

できるだけわかりやすく説明してみるという実験:再帰関数

プログラムにおける関数というものは、その関数の中でさらに他の関数を呼ぶことができる。

たとえばいくつかの円を描くプログラムがあり、ある関数が「◯番目の円を描く」というものであったとしよう。
この関数は、「◯番目」という番号だけを受け取るが、その番号の円が描かれる位置と半径が必要である。 

そこで、もうひとつ別の関数として、「◯番目という番号を受け取ったら、登録されている円を探しだし、その位置と半径を返す」というものを用意する。

以上を仮想プログラミング言語で書くと以下だ。

1:関数"円を描く"(n番目)[
2:   円=関数"円の情報を取得"(n番目)
3:   円を描く
4:]関数"円を描く"ここまで

5:関数"円の情報を取得" (n番目)[
6: n番目の円を取得
7:   円の情報を返す
8:]関数"円の情報を取得"ここまで 

ここでは1つめの関数"円を描く"がその内部でもうひとつの関数"円の情報を取得"を呼んでいる。
これにより"円の情報を取得"という関数は、他のところからも呼ぶことができるようになり、再利用できるものになる。

関数の中から別の関数が呼べる、ということだが、それは必ずしも"別の"関数でなければならないわけではなく、自分自身を呼ぶこともできる。
これを"再帰関数"と呼ぶ。 



「再帰関数によって自分自身を呼ぶ」というのはどういう時に必要になるのだろうか?
たとえばこのブログで度々出てくる、"GNU's Not Unix!"である。

「GNUは何の頭文字を取ったものか?」というものを展開する関数がある、とする。
この関数は、与えられた文字列に"GNU"というものが見つかれば、それを説明するために、カッコ()つきで"GNU's Not Unix!"という言葉に置き換える。
仮想プログラミング言語で書くと以下だ。

1: 関数"GNUを展開する"(文字列)[
2: もし文字列に"GNU"が含まれていたらその後ろに"(GNU's Not Unix!)"と付け加える
3:    その文字列を返す
4: ]関数"GNUを展開する"ここまで 

この関数に"GNU"という文字列を与えると、"GNU(GNU's Not Unix!)"と返ってくる。

このプログラムの3行目で文字列を返さずに、もう一度その新しい文字列で自分自身を呼ぶとどうなるだろうか? 

1: 関数"GNUを展開する"(文字列)[
2: もし文字列に"GNU"が含まれていたらその後ろに"(GNU's Not Unix!)"と付け加える
3:    関数"GNUを展開する"(文字列)を呼ぶ
4: ]関数"GNUを展開する"ここまで 

このままだと、関数が自分自身を呼んで、さらに自分を呼んで、、、を繰り返すので無限ループである。
なので、この関数にはカウントダウンする数字を渡すことにして、決められた回数で止まるようにする。

1: 関数"GNUを展開する"(文字列, 数字)[
2: もし文字列に"GNU"が含まれていたらその後ろに"(GNU's Not Unix!)"と付け加える
3:    もし数字が0ならば [
4:      文字列を返す
5:     ]
6:    そうでなければ [
7:      数字をひとつ減らす
8:      関数"GNUを展開する"(文字列, 数字)を呼ぶ
9:    ]
10: ]関数"GNUを展開する"ここまで
11: 文字列を返す

この関数("f0"と呼ぶ)を("GNU", 2)という文字列と数字で呼ぶと、
2行目で"GNU(GNU's Not Unix!)"に書き換えられる。
3行目で数字は2なので、6行目までとぶ。
7行目で数字が1になる。
8行目でふたたびこの関数が("GNU(GNU's Not Unix!)", 1)で呼ばれる。

呼ばれた先("f1"と呼ぶ)では、
2行目で"GNU(GNU's Not Unix!)(GNU(GNU's Not Unix!)'s Not Unix!)"に書き換えられる。
3行目で数字は1なので、6行目までとぶ。
7行目で数字が0になる。
8行目でふたたびこの関数が("GNU(GNU's Not Unix!)(GNU(GNU's Not Unix!)'s Not Unix!)", 0)で呼ばれる。

さらに呼ばれた先("f2"と呼ぶ)では、
2行目で"GNU(GNU's Not Unix!)(GNU(GNU's Not Unix!)'s Not Unix!)(GNU(GNU's Not Unix!)(GNU(GNU's Not Unix!)'s Not Unix!)'s Not Unix!)"に書き換えられる。
3行目で数字は0なので、この文字列"GNU(GNU's Not Unix!)(GNU(GNU's Not Unix!)'s Not Unix!)(GNU(GNU's Not Unix!)(GNU(GNU's Not Unix!)'s Not Unix!)'s Not Unix!)"を返す。つまりf1に戻る。

f1では、
10行目で関数が終わるので、f0に戻る("GNU(GNU's Not Unix!)(GNU(GNU's Not Unix!)'s Not Unix!)(GNU(GNU's Not Unix!)(GNU(GNU's Not Unix!)'s Not Unix!)'s Not Unix!)"を返す)。

f0では
10行目で関数が終わるので、
10行目で関数が終わるので、"GNU(GNU's Not Unix!)(GNU(GNU's Not Unix!)'s Not Unix!)(GNU(GNU's Not Unix!)(GNU(GNU's Not Unix!)'s Not Unix!)'s Not Unix!)"を返す。

再帰関数では以上のようなことが起こる。
ややこしい話だが、このようなややこしい問題を人間に代わってやってくれるのがコンピューターである。 

OLランキングで1位になりたい!賛同していただける方は下記をクリック!

コメントする

名前
 
  絵文字
 
 
スパイたちに告ぐ根性論:間違わなければ学べない