48

そうでない場合、再帰的な対応物が存在しない反復アルゴリズムを示す良い反例はありますか?

すべての反復アルゴリズムを再帰的に表現できる場合、これを行うのがより難しいケースはありますか?

また、この中でプログラミング言語はどのような役割を果たしているのでしょうか? Scheme プログラマーは、Java のみのプログラマーとは反復 (= 末尾再帰) とスタックの使用法が異なると想像できます。

4

7 に答える 7

81

これには簡単なアドホック証明があります。厳密に反復構造を使用するチューリング完全言語と、再帰構造のみを使用するチューリング完全言語を構築できるため、この 2 つは等価です。

于 2010-01-19T13:20:02.253 に答える
21

すべての反復アルゴリズムは再帰的に表現できますか?

はい、しかし証明は面白くありません:

  1. すべての制御フローを含むプログラムを、1 つの case ステートメントを含む 1 つのループに変換します。このループでは、各分岐が、、、、、などbreakを含む直線的な制御フローreturnになります。case ステートメントが次に実行するブロックを決定するために使用する新しい変数 (「プログラム カウンター」と呼びます) を導入します。exitraise

    この構造は、人々がさまざまな制御フロー構造の相対的な表現力を議論していた 1960 年代の大きな「構造化プログラミング戦争」の間に発見されました。

  2. ループを再帰関数に置き換え、すべての変更可能なローカル変数をその関数のパラメーターに置き換えます。ほら！反復は再帰に置き換えられました。

この手順は、元の関数のインタープリターを作成することになります。ご想像のとおり、コードが読めなくなり、面白いことではありません。 ただし、一部の手法は、関数型言語でのプログラミングを初めて学習する命令型プログラミングのバックグラウンドを持つ人に役立ちます。

于 2010-01-19T21:08:20.727 に答える
8

あなたが言うように、すべての反復アプローチは「再帰的」アプローチに変えることができ、テールコールを使用すると、スタックも爆発しません。:-) 実際、Scheme がすべての一般的な形式のループを実装する方法です。スキームの例:

(define (fib n)
  (do ((x 0 y)
       (y 1 (+ x y))
       (i 1 (+ i 1)))
      ((> i n) x)))

xここでは、関数は反復的に見えますが、実際には、y、およびの3 つのパラメーターを受け取る内部ラムダで再帰し、i各反復で新しい値で自分自身を呼び出します。

関数をマクロ展開する方法の 1 つを次に示します。

(define (fib n)
  (letrec ((inner (lambda (x y i)
                    (if (> i n) x
                        (inner y (+ x y) (+ i 1))))))
    (inner 0 1 1)))

このようにして、再帰的な性質がより視覚的に明らかになります。

于 2010-01-19T13:22:08.087 に答える
7

反復を次のように定義します。

function q(vars):
  while X:
    do Y

次のように翻訳できます。

 function q(vars):
    if X:
      do Y
      call q(vars)

ほとんどの場合、Y には、X によってテストされるカウンターのインクリメントが含まれます。この変数は、再帰ルートに進むときに何らかの方法で「vars」に渡される必要があります。

于 2010-01-19T13:23:19.063 に答える
1

彼らの答えで plinth が指摘したように、再帰と反復がどのように同等であり、同じ問題を解決するために両方を使用できるかを示す証明を構築できます。ただし、2 つが同等であることはわかっていても、一方を他方よりも優先して使用することには欠点があります。

再帰に最適化されていない言語では、反復を使用するアルゴリズムが再帰的なアルゴリズムよりも高速に実行されることがわかります。同様に、最適化された言語であっても、別の言語で記述された反復を使用するアルゴリズムが再帰的なアルゴリズムよりも高速に実行されることがあります。さらに、再帰対反復、およびその逆を使用して、特定のアルゴリズムを作成する明確な方法がない場合があります。これにより、コードが読みにくくなり、保守性の問題が発生する可能性があります。

于 2010-01-19T13:46:10.760 に答える
-2

Prologは再帰のみの言語であり、その中でほとんどすべてを行うことができます（お勧めしませんが、できます:)）

于 2010-01-19T13:24:01.483 に答える