2

私は、各再帰呼び出し/演算の結果を保持する静的変数の使用を含む多くの再帰関数（主に階乗、数値の桁の合計などのいくつかの数学演算の計算に使用されます）を見てきました。後続の呼び出しに使用します。

そのため、再帰関数は非賃貸であり、スレッドセーフではありません。

静的変数を必要としない再帰関数の他のユースケースはありますか？

4

7 に答える 7

11

2つは異なる概念です。一方が他方を意味することはなく、その逆も同様です。

たとえば、これは再帰関数（仮説言語）ですか？

global sum = 0

proc accumulate(treeNode)
    sum += treeNode.Value
    if treeNode.Left then accumulate(treeNode.Left)
    if treeNode.Right then accumulate(treeNode.Right)
end

明らかに再帰関数ですが、グローバル変数を使用しているため、再入可能ではありません。ここでの「グローバル」とは、少なくとも「関数に対してローカルではない」という意味です。

ただし、これは悪い例です。合計を返すだけで、グローバル変数にまったく依存しないようにするのは非常に簡単だからです。

func accumulate(treeNode)
    sum = treeNode.Value
    if treeNode.Left then sum += accumulate(treeNode.Left)
    if treeNode.Right then sum += accumulate(treeNode.Right)
    return sum
end

再帰関数の概念に固有のものはなく、スレッドセーフではない、またはリエントラントになる、あるいはその逆です。それはすべて、問題の関数に実際に何を書き込んだかによって異なります。

于 2010-01-31T11:36:59.003 に答える
5

静的変数を必要としない再帰関数の他のユースケースはありますか？

もちろん。実際、再帰関数の静的変数は例外であり、規則ではありません。

私は、各再帰呼び出し/演算の結果を保持する静的変数の使用を含む多くの再帰関数（主に階乗、数値の桁の合計などのいくつかの数学演算の計算に使用されます）を見てきました。後続の呼び出しに使用します。

それらは率直に言って悪い実装でした。ここでは静的変数は絶対に必要ありません。それらはおそらくアキュムレータとして機能しました。これは、アキュムレータを追加の引数として渡すことで、より適切に実行できます。

于 2010-01-31T11:39:11.750 に答える
1

状態が参照または上位のデータ構造を介して引数として渡される再帰関数は、リエントラントです。

于 2010-01-31T11:36:42.330 に答える
1

私の見解では、あなたが見た例には欠陥があります。再帰関数を記述する標準的な手段は、結果を格納するための静的変数を使用または必要としません。代わりに、引数や戻り値を使用する必要があります。統計を使用すると、実際にそれらは非賃貸人になりますが、そのようにコーディングするべきではありません。

戻り値の使用例（JavaScript）：

function deepCollectChildText(node) {
    var text, child;

    text = "";
    for (child = node.firstChild; child; child = child.nextSibling) {
        switch (child.nodeType) {
            case 1: // element node, may contain child nodes
                text += deepCollectChildText(child);
                break;
            case 3: // text node
                text += child.value;
                break;
        }
    }
    return text;
}

スタティックの必要はありません。1つを使用してコーディングされている可能性があるため、再入可能ではありませんが、再入可能である理由はありません。

于 2010-01-31T11:37:01.190 に答える
0

IMHO、静的変数またはグローバル変数が関数で使用されている場合、スレッドセーフではない可能性があります。それ以外の場合は、スレッドセーフです。

于 2010-01-31T11:40:41.127 に答える
0

再帰関数は、通常の関数と同じ程度にスレッドセーフです。すべての言語アーキテクチャで、再帰がサポートされていることを認識しています。各トレッドには独自のスタックがあり、再帰関数が変数を格納してアドレスを返すために使用するスタックです。

于 2010-01-31T11:36:24.160 に答える
0

過去の慣習を思い出して、再帰関数に静的変数を使用することを検討または実践したことはありません。定数を除いて。

  • 再入可能関数は、静的変数または共有リソースを変更せず、静的非定数または変更可能な共有リソースを読み取りません。
  • したがって、再入可能=>スレッドセーフですが、その逆はありません。
  • 静的変数を変更する再帰関数は再入可能ではありません。

したがって、リエントラント再帰関数はスレッドセーフです。一方、非再入可能な再帰関数は、共有/静的リソースへのアクセスが同期境界によって効果的に制限されている場合を除いて、スレッドセーフではありません。

次に、次の質問に答えてもらいます。関数がデータベースレコードを変更した場合、それによって再入可能ではなくなりますか？

エントリーごとに外部リソースがインスタンス化されている限り、機能はリエントラントだと思います。たとえば、一意のID実行キーを持つデータベースレコード。エントリごとに、新しい実行キーを持つ新しいレコードが生成されます。

しかし、それは実際には静的変数をスレッドセーフにするようなものですか？これは、参加者ごとに一意のキーと値のペアを生成するスレッドセーフな静的ハッシュテーブルのようなものであるため、参加者間でキーと値のペアが共有されることはありません。

したがって、データベースレコードまたは静的リソースが、エントリごとにそのリソースの一意のインスタンスをディスペンスする場合、関数は効果的に再入可能ですが、外部共有リソースのスレッドセーフ保護に依存しているため、学者はそれがスレッドであると言うかもしれません-安全ですが、再入可能ではありません。

そのような議論のために、私は違うように頼むでしょう。たとえば、架空のプログラミング言語の場合、その仕様は、変数を格納するために共有データベースまたはグローバルハッシュを使用することからその実装を制限しません。そのため、プログラマーは、言語の実装の下でスレッドセーフに管理されたリソースが使用されていることに気づいていません。それで、プログラマーは出て行って「リエントラント」関数を書きます、またはそう彼/彼女は考えます。それで、彼/彼女の「再入可能機能」は非再入可能になりますか？

したがって、私の結論は、静的/共有リソースが参加ごとに一意のインスタンスをディスペンスする限り、関数は再入可能です。

より良い言葉を知るための知識が不足しているため、参加/再参加という用語を作り出してしまったことをお詫びします。

于 2010-01-31T12:56:07.990 に答える