5

相互再帰が問題の最も洗練された解決策であり、単一の再帰関数に簡単に縮小/インライン化できない、非人工的な例があるかどうかを知りたいです。

私はすでにこの例を知っています（ウィキペディアから）

function even?(number : Integer)
    if number == 0 then
        return true
    else
        return odd?(abs(number)-1)

function odd?(number : Integer)
    if number == 0 then
        return false
   else
        return even?(abs(number)-1)

しかし、真剣に、彼らの正しい心の誰もこの方法で数のパリティをチェックすることはありません。

このトピックに関する以前の回答をSOで確認しました-相互再帰の例はありますか？しかし、答えはどれも私が探しているものではありません。

私はそれが再帰的な構文解析に役立つことを知っています-おそらくそれを実装する唯一の論理的な方法ですが、よりクリーンでより具体的な例（できれば数学的な例）が必要です。

助けてくれてありがとう？

編集：

どうやら相互再帰関数のすべてのタプルを単一の関数に減らすことができるので、相互再帰関数の使用が最良/最も読みやすい方法である場合があるかどうかを知りたいと思います。

4

4 に答える 4

5

シェルピンスキー曲線（および他のいくつかの曲線）を描画するための相互再帰コードは、かなりエレガントに見えます。

于 2012-04-24T11:50:53.847 に答える
4

相互再帰は簡単に1つの関数にまとめることができると思います。

2つの関数f1とf2を考えてみましょう。

f1(p1, ..., pn) returns r1
f2(q1, ..., qm) returns r2

次のように統合できます。

f12(which, p1, ..., pn, q1, ..., qn) returns (r1, r2)
    if which == 1
        <code of f1>
    else
        <code of f2>

これは最悪のケースです。通常、一部のパラメーターまたは戻り値は同じである必要があります。

于 2012-04-24T10:14:54.470 に答える
2

「エレガント」と見なすのは、個人の感性次第です。しかし、これが私のショットです。

Adamは6日間の試験改訂をスケジュールしようとしています。毎日、彼は次のいずれかに行きます。

  1. 休憩（R）
  2. 数学を勉強する（M）
  3. スタディコンピューティング（C）

アダムは2日連続で2つの異なる主題を研究することはありません。アダムはどのように彼の改訂をスケジュールすることができますか？

解決：

表記法を使用しs1 = "RMCRMM"てスケジュールを表します。s1スケジュールのある時点でサブジェクト（M）の直後に別のサブジェクト（C）が続くため、は有効なスケジュールではありません。有効なスケジュールの例としては、次のようなものがあります：s2 = "MMRCCR"またはs3 = "MMRRRC"またはs4 = "RRRRRR"（幸運を祈りs4ます！）。各スケジュールでは、2つの異なる被験者の間に少なくとも1つの休憩日が必要です。

相互再帰を使用してタスクを解決できます。から始まる日数を列挙してみましょう1, 2, ..., 6。R(k)3つの相互再帰関数、、、M(k)を定義しましょうC(k)。各関数は、それぞれが長さの部分的なスケジュールの数を計算しますk。ここで、最後の日はそれぞれ「R」、「M」、および「C」です。ここに行きます（python）：

def R(k):
    if k == 1:
        return 1
    else:
        return R(k-1) + M(k-1) + C(k-1)

def M(k):
    if k == 1:
        return 1
    else:
        return R(k-1) + M(k-1)

def C(k):
    if k == 1:
        return 1
    else:
        return R(k-1) + C(k-1)

次に、評価することで問題を解決できますR(6) + M(6) + C(6)

これが機能する理由は、特定の方法で終了する可能性のある日数の（部分的な）スケジュールに到達するための可能な方法を数えているためです。kまた、到達方法の選択に影響を与える可能性がある唯一のことは、何が起こったかです。前日。このようにして、可能なすべてのスケジュールをカウントし、各スケジュールを1回だけカウントします。

たとえば、「C」、「XXC」で終了した3日目の場合、R(2) + C(2)スケジュール「XCC」または「XRC」から取得できた可能性があるため、このようなスケジュールに到達できる方法の数は正確です。 、ただし「XMC」ではありません。

明らかに、これをより効率的にしたい場合は、おそらくメモ化/動的計画法を使用することになりますが、それでも、相互再帰が問題をコード化するための最も読みやすく理解しやすい方法である可能性があります。

于 2018-02-14T09:41:07.117 に答える
0

適切な末尾呼び出しの最適化がある場合は、協調マルチタスクを実行できます。

f():
    do_something()
    g()

g():
    do_something_else()
    f()

たまたまSchemeでコーディングする場合、これは時々考慮すべきことです。

于 2012-04-24T11:14:48.967 に答える