プログラム構造の「再帰的」について

再帰的の説明に
「再帰的とは、あるプログラムがその内部から自分自身を呼び出して使用できる性質である。」「したがって再帰的であれば、必然的に再入可能でもある。」とありました。

ここで、「したがって再帰的であれば、必然的に再入可能でもある。」とは、つまり、プログラムＡの中に再帰したプログラムＡ’が既に再入している状態にある、ということを表しているという理解かな？と思っているのですが、宜しいのでしょうか？

より良い理解のために、補足説明などいただけたら、と思います。よろしくお願いいたします。

No.1 ベストアンサー 回答者： Aruku-20030515 回答日時： 2004/09/27 14:20

言葉の問題になっちゃうんですが

再帰関数は、Ａと言う関数があるとすれば
Ａ関数の実行途中にＡ関数を呼び出す記述があり
自分自身を呼びだす事になります。

一般的によくやるのが、ディレクトリーの処理ですね。

No.4 回答者： ranx 回答日時： 2004/09/27 16:09

「再帰的であれば、必然的に再入可能でもある」

これは必ずしも正しくないんじゃないかという気がするんですけどねえ。

「再入可能」というのは、同一のプログラムを複数同時並行的に実行できることですよね。
再帰的なプログラムは、確かに呼び出す側と呼び出される側とで複数のプログラムを同時に
実行しているように見えます。しかし、「再入可能」という語を使う場合、通常は複数の
実行が非同期的になされることを前提としていると思うのです。No.3さんの回答にある
「オート変数のみ」という条件は、そのために必要なものです。しかし、再帰的なプログラム
の場合、自分自身の呼び出しは一般的に同期をとって行われます。ですので、メモリーの
固定領域を参照していたとしても、動作に全く問題のない再帰的プログラムは可能です。
こうしたものを「再入可能」と呼んでよいのか、個人的には抵抗があります。

No.3 回答者： tttt23 回答日時： 2004/09/27 14:58

> 「したがって再帰的であれば、必然的に再入可能でもある。

」

この意味は、その関数が再入可能であるという性質を持っている必要があるということです。簡単に言えばオート変数だけ使って作られている必要があるということです。

再入可能でなければ再帰呼び出しはできません。従って再帰呼び出しをしているということは再入可能です。

ちなみに、A が B を呼び出し、B が A を呼び出すときも再帰呼び出しといいますので、必ずしも自分自身を (直接) 呼び出すわけではありません。

No.2 回答者： gookuma 回答日時： 2004/09/27 14:56

特定の領域のメモリやI/Oポートを使用したプログラム・ルーチンは、マルチタスク環境や割り込みが発生する環境では正しく動作しません。

そこで、このような環境でも正常に動作するように作ったプログラム・ルーチンは再入可能であると言います。

再帰プログラム・ルーチンは、その内部で自分自身を呼び出しますが、これはプログラム・ルーチンの実行中に再度そのプログラム・ルーチンが呼び出されることなので、したがって再帰呼び出し可能なプログラム・ルーチンは再入可能なプログラム・ルーチンであるということが言えます。