前回、関数(手続き)の定義と呼び出し方を整理しました。今回は、その応用でもある「再帰処理」の考え方を整理します。
再帰処理とは
再帰処理とは、関数が、自分自身をもう一度呼び出す処理のことです。「関数の中で、同じ関数を呼ぶ」と聞くと、最初は少し不思議に感じますが、階乗の計算のような、同じ手順を繰り返す処理を、簡潔に表現するときによく使われます。
階乗を例に考える
再帰処理の代表例として、階乗(１から順にその数までを掛け合わせる計算)を考えます。
○整数型:階乗(整数型:n) if(n = ０)then return １ else return n × 階乗(n − １) endif
この関数は、「nが０なら、そのまま１を返す」「nが０でなければ、nと、nより１小さい値の階乗を掛けたものを返す」という定義になっています。この「n−１の階乗」を求める部分で、関数が自分自身を呼び出しています。
図解して考える(積み木のイメージ)
再帰処理を頭の中だけで追おうとすると、途中で混乱しやすいので、自分は積み木を積んでいくイメージで捉えるようにしています。
階乗(３)を呼び出すと、その中で階乗(２)を呼び出し、さらにその中で階乗(１)を呼び出し、最後に階乗(０)を呼び出します。ここでようやく「０なら１を返す」という土台にたどり着き、そこから積み木を１段ずつ下から上に組み立てるように、計算結果が返っていきます。
- 階乗(０) → １を返す
- 階乗(１) → １×１ = １を返す
- 階乗(２) → ２×１ = ２を返す
- 階乗(３) → ３×２ = ６を返す
このように、「呼び出しがどんどん深くなっていく部分」と、「土台に着いてから、値を持ち上げながら戻ってくる部分」の２段階に分けて考えると、流れがつかみやすくなります。
再帰処理で気をつけたいこと
再帰処理には、必ず「終わりの条件」が必要です。先ほどの例でいえば、「nが０なら１を返す」という部分が、それにあたります。この終わりの条件がないと、呼び出しが終わらず、無限に続いてしまいます。
トレース問題を読むときは、まずこの終わりの条件を見つけてから、そこに向かって呼び出しがどう深くなっていくかを追うようにしています。
学習してみた感想
再帰処理は、これまでで一番「頭がこんがらがりやすい」と感じた単元でした。ただ、積み木を積んで、また下から順に持ち上げていくイメージに置き換えたことで、格段に理解しやすくなりました。文章だけで理解しようとせず、図や矢印を実際に書いてみることの大切さを、改めて感じています。
次回は、①に戻り、メモリ階層とキャッシュメモリの仕組みを整理します。
