recursion - 再入可能性と再帰

Question

すべての再帰関数は再入可能である必要があると言うのは本当でしょうか?

Answer 1

再入可能とは、前の関数が終了する前に関数へのさらなる呼び出しが開始される可能性があることを意味する場合、そうです、再帰はその意味で再入を意味するため、すべての再帰関数はたまたま再入可能です。

ただし、「再入可能」は「スレッドセーフ」の同義語として使用されることがあります。これは、他の多くの要件を導入するものであり、その意味では、答えはノーです。シングルスレッド再帰では、関数の「インスタンス」が一度に 1 つしか実行されないという特殊なケースがあります。これは、スタック上の「アイドル」インスタンスがそれぞれ「子」インスタンスが戻るのを待っているためです。

Answer 2

いいえ、静的 (グローバル) 変数で機能する階乗関数を思い出します。静的 (グローバル) 変数を持つことは再入可能であることに反し、それでも関数は再帰的です。

global i;

    factorial()
    { if i == 0 return 1;
      else { i = i -1; return i*factorial();

    }

この関数は再帰的であり、再入不可です。

Answer 3

全くない。

たとえば、再帰関数が静的データを持つことができないのはなぜですか? クリティカル セクションをロックできないようにする必要がありますか?

検討：

sem_t mutex;
int calls = 0;

int fib(int n)
{
    down(mutex); // lock for critical section - not reentrant per def.
    calls++; // global varible - not reentrant per def.
    up(mutex);

    if (n==1 || n==0)
        return 1;
    else
        return fib(n-1) + fib(n-2);
}

これは、再帰的でリエントラントな関数を書くのが簡単であるとか、それが一般的なパターンであるとか、何らかの方法で推奨されるということではありません。しかし、それは可能です。

Answer 4

「再入可能」とは、通常、2 つの異なるスレッドが同時に複数回関数に入ることができることを意味します。

再入可能にするには、静的状態へのアクセスを保護/ロックするなどのことを行う必要があります。

一方、再帰関数は、一度に 1 つのステートメントしか実行しないため、静的状態へのアクセスを保護/ロックする必要はありません。

だから：いいえ。