再帰呼び出し

再帰呼び出しとは、プログラムにおける制禦構造のひとつ。リカーシブ・コールあるいは落語の演目のひとつである『あたま山』（上方落語では『さくらんぼ』）から「頭山的呼び出し」とも呼ばれる。

概要

賛否あり、「ループによるコードよりも簡潔になる」「ネットワーク型のデータ構造に適用しやすい」反面、「メモリの使用量が読みづらい」「確実に歯止めをかけないと不具合の原因になり、しかも不具合の切出しが困難である」という難点も指摘される。

使い方

大きく分けて三種類ほどある。

木探索

単純な木構造を、末端から根本に辿ってゆくものと、逆に根本から末端に辿ってゆくものの二種類がある。前者はいわゆる「ユークリッドの互除法」が代表で、後者はディレクトリー・ツリーの中の特定の名前のファイルを探す（ツリー・リトリーブとかWalkSubTreeとか云われる言われる）のに使われる。

束構造の探索

日本語処理における、いわゆる「かな漢字変換」の接続関係の中から最尤候補を取りだすなど。途中で合流する点があると、自分の出したい候補がなかなか出てこないなどの困難があるが、この場合は「先頭から何文字め、文法属性はこれこれ」という距離空間があるので克服は難しくないが、「高速化したい」「コードの可読性を上げたい」といった欲が出てくると、中間言語を使ったりといった話になる。ellispはこのタイプの中間言語である。

有向ネットワーク構造データの探索

最短経路を探すような場合。このとき、「以前通ったことのある節点（分岐点）かどうか」をチェックするための「地図」が必要となる（というか、地図を作りながら処理を進めることが多い）。「有向」であるから一方通行とは限らず、反対方向からも来られる場合は、上りルートと下りルートを別扱いするなどの工夫が要る。検索エンジンのクローラも問題構造は同じである。
ダンジョン探索においては基本的な技法であり、横溝正史『八つ墓村』では金田一耕助が村の地下にある大洞窟の探索にこの方法を用いている。協調コンピューティングを利用するとかなり簡単になる。

関連作品

• 横溝正史の小説『八つ墓村』
• 映画『八つ墓村』。市川崑監督によって、二度映画化されている。