再帰関数のトレースに時間がかかるのですが?

ご質問
 再帰関数のトレースに苦労しています(時間がものすごくかかる)。
 定規を使うとトレースしやすいことがわかったのですが、他に何か“テクニック”はありますか?

福嶋の回答
 再帰関数は、同じ関数がたくさんあると考えて、ぜひトレースしてほしいですね。時間がかかっても、最初から最後まで自分でトレースしてみると、どこから呼ばれて、どこに戻るのか、再帰関数の仕組みが、よく理解できます。最初の頃は、プログラムを何枚かコピーしておいて、呼び出したときに次の紙に行くようにすれば、戻るときにどこに戻るのかが明確になります。定規を置いて、どこに戻ってくるか分かるようにするのは、とってもよい方法です。

 さて、トレースの訓練をある程度積んだら、今度は量から質へ、学習のやり方を変えていきます。

 ふっくゼミのアルゴリズム補講でいえば、基本編は、徹底的にトレースをする、頭を使う前にまず手を動かせばいい、という感じです。最初から最後までトレースをして、アルゴリズムを理解できれば十分です。
 「受かる!」テキストも、第3章までは、自力でトレースすることに重点をおけばいいです。
 応用編やテキストの第4章以降になると、基本編のトレースの訓練で養った基礎力を育てて、応用力を伸ばしていく段階です。
 まず、流れ図や疑似言語プログラムの全体をながめて、塊(ブロック)ごとに、そこで何の処理をしているのかを考えるようにします。
 まったくトレースをしないということではなくて、簡単なトレースをして処理内容をつかむのですが、最初から最後までをトレースするようなことは減らしていきます。

 再帰関数は、時間をかけて、いくつかのアルゴリズム(再帰選択ソート、クイックソート、マージソート、再帰2分探索ぐらいでいいですよ)をトレースされていれば、再帰の仕組みは理解されています。
 もう、最初から最後まで、いちいちトレースする必要はありません。

 再帰選択ソートの回で話したと思いますが、再帰関数を用いた流れ図や疑似言語プログラムを読むときには、再帰関数の中で呼び出してる関数(自分自身)は、既に完成している関数だと考えてトレースすればいいのです。
 例えば、クイックソートなら、範囲を指定して呼び出したら、その範囲が整列(ソート)されて返ってくると考えればいいのです。最初の頃にトレースしたように、自分自身を繰り返し呼び出すところまで、毎回トレースする必要はありません。
 再帰を乗り越えれば、基本情報技術者試験で出題されるアルゴリズムの壁を越えたことになります。後は平たんな道です。上位試験に進むと、別の壁が立っていますけどね。

(2012/12/8)
(2021/5/13) 古くなっている部分などを一部修正。