必用テクニック
再帰処理はプログラミング対象によっては、一生使用しないテクニックだ。特に基幹業務(会計とか顧客管理とか)では利用場面を想像するのさえ難しい。しかーし、それは突然やってくるのである！来るべきその日に備え、再帰処理をマスタ/確認をしよう。
再帰処理とは関数が自身を呼び出すことによって処理を行う方法だ。これじゃーさっぱりわからない。プログラムを見ていこう。
プログラム例
階乗を求める関数を作成する。普通に記述すれば、こんな感じになる。
右上三角をクリックして実行してください。
階乗テクニックを使うと、
右上三角をクリックして実行してください。
どうでしょうか？コードを読めるでしょうか？初めて階乗プログラムを見て、その動作がわかる人は天才です。私は30秒ほど 息を止めコードを眺め続けた記憶あります。そんなわけで、どのように動作しているか、じっくりと見ていく。
プログラムを分析
ポイントは5行目だ。returnは呼び出し元へ戻る命令だが、その前に右側が実行される。ここで自分自身(sum2)を呼び出している。
|
5 |
return num * sum2(num-1) |
自分自身の呼び出し前に「num *」、引数は「num-1」。わかりやすいように、numに入っている値で考えてみる。最初の7行目の呼び出しでは、引数を5としていた。
|
1 |
print(sum(5)) |
numには5が保存されているので書き換え考える。
|
5 |
return 5 * sum2(5 -1) |
階乗計算の「５×４」を実現しているように見える。しかし、自分自身を呼び出すとどうなるのだろう？図で表してみる。
自分自身を呼び出すというと混乱するが、別関数を呼び出していると考えればいい。1回目の呼び出しと違うのは、numから1減算され引数が4になるところだ。
これで二つ目のsum2も普通の関数のように実行される。コードを追っていくと、次の命令になる。
|
5 |
return num * sum2(num-1) |
当たり前だけど、一つ目と同じ命令だ。違うのはnumの値が4になっている。numを4に置き換えると、
|
5 |
return 4 * sum2(4 -1) |
階乗計算の４×３を実現しようしているように見えるが、また関数を呼び出すことになる。これを図式すると。
３つ目の関数を呼び出している。違いは引数が3というところだ。これを・・・。とっ、そろそろこのページを閉じる気配を感じるので、後は省略してみよう。でもこの呼出し連鎖はいつ終わるのか？プログラムを見ると、
|
2 3 |
if num == 1: return 1 |
これだ！numが1になった時にreturnする。これ以上自分自身の呼び出しは行われない。住宅ローン35年の自分にとっては、払っている多くが利息分と知った時の絶望感、それから解放された感じだ！。いやー終わった、終わった。
「えっつ、returnした後、どうなるの？喜んでいる場合なの？ちゃんとローン残高払いなさいよ」
うっ、、、ごもっとも、終わらずに続けます(払い続けますョ！)
面倒臭くなり、ごまかそうと考えたがここからが重要なのである！returnしたらどうなるか！呼び出しの連鎖が終了するまでを図で確認しよう
5回目の呼出しでnumが1になり、if文が実行される。ここでreturn命令だ。returnは呼出し元へ戻る命令だ。従って5回目を呼出している4回目へ戻る。その際に戻り値1を返している。これも図にしてみよう。
4回目の呼出し元へ戻ってくると残りの命令、「return num * 1」が実行される。
|
5 |
return num * sum2(num-1) |
4回目のnumには2が保存されているので、 「return 2 * 1」だ！。この2を戻り値として3回目の呼出し元へ戻る。
3回目の呼出し元へ戻ってくると残りの命令、「return num * 2」が実行される。3回目のnumには3が保存されているので、「return 3 * 2」だ！。この6を戻り値として2回目の呼出し元へ戻る。ここからは読んでる皆も面倒なはずだ。最後までを図にしてみる。
呼出し元へ戻りながら階乗の計算がされるというわけだ。どうだろうか理解は進んだだろうか？
「わかったような気がするけど、これって最初に紹介してたforを使えばいいのでは？」
エーー、、確かに階乗の場合はforで十分ですが、再帰処理の方がスッキリする場合があります。
利用場面
階乗計算の場合はループする回数が事前にわかるが、わからないことがある。例えば、ディレクトリ(フォルダー)操作などだ。
フォルダーの中はファイルだけではない。さらにフォルダーが入っていることがある。それはフォルダーを開かないとわからない。
プログラムでフォルダーの全てのファイル名を表示しようとすると、フォルダーの階層がどこまで続くかわからないので特定回数のループができない。
「whileを使えばできるでは？」
確かにwhileを使えばできそうな感じだが、ものすごーーーく難解なプログラムになるであろう。日本語でプログラムぽく考えてみると、
|
1 2 3 4 5 6 7 8 9 10 11 |
while(全てのファイルを探すまで): (1)フォルダー内のファイル/フォルダーを取得 (1)-1ファイルなら表示 (1)-2フォルダーなら (1)-2-1ファルダー内のファイル/フォルダーを取得 (1)-2-1-1ファイルなら表示 (1)-2-1-2フォルダーなら ・ ・ ・ } |
これではうまくいきそうにない。最初にフォルダー階層を走査する処理を行い、ループ回数を特定してから・・・うまくいくかもしれない。でもこれなら再帰処理の方がスッキリするだろう。
まとめ
- 再帰処理は一生使わないかもしれない
- でも再帰処理を使わないと処理が難解になることがある
- ブログが長くならないようにしないと、書いてる方も読んでる方も苦痛である
以上
