1917

Lisp を学び始めているときに、末尾再帰という用語に出くわしました。正確にはどういう意味ですか？

4

30 に答える 30

1948

最初の N 個の自然数を加算する単純な関数を考えてみましょう。(例sum(5) = 0 + 1 + 2 + 3 + 4 + 5 = 15)。

以下は、再帰を使用する単純な JavaScript 実装です。

function recsum(x) {
    if (x === 0) {
        return 0;
    } else {
        return x + recsum(x - 1);
    }
}

を呼び出しrecsum(5)た場合、JavaScript インタープリターは次のように評価します。

recsum(5)
5 + recsum(4)
5 + (4 + recsum(3))
5 + (4 + (3 + recsum(2)))
5 + (4 + (3 + (2 + recsum(1))))
5 + (4 + (3 + (2 + (1 + recsum(0)))))
5 + (4 + (3 + (2 + (1 + 0))))
5 + (4 + (3 + (2 + 1)))
5 + (4 + (3 + 3))
5 + (4 + 6)
5 + 10
15

JavaScript インタープリターが合計を計算する作業を実際に開始する前に、すべての再帰呼び出しが完了する必要があることに注意してください。

同じ関数の末尾再帰バージョンを次に示します。

function tailrecsum(x, running_total = 0) {
    if (x === 0) {
        return running_total;
    } else {
        return tailrecsum(x - 1, running_total + x);
    }
}

, を呼び出した場合に発生する一連のイベントを次に示します(これは、既定の 2 番目の引数により、tailrecsum(5)実質的に になります)。tailrecsum(5, 0)

tailrecsum(5, 0)
tailrecsum(4, 5)
tailrecsum(3, 9)
tailrecsum(2, 12)
tailrecsum(1, 14)
tailrecsum(0, 15)
15

末尾再帰の場合、再帰呼び出しが評価されるたびにrunning_totalが更新されます。

注: 元の回答では、Python の例を使用していました。Python インタープリターは末尾呼び出しの最適化をサポートしていないため、これらは JavaScript に変更されました。ただし、テール コールの最適化はECMAScript 2015 仕様の一部ですが、ほとんどの JavaScript インタープリターはサポートしていません。

于 2008-08-31T18:21:13.897 に答える
791

従来の再帰では、最初に再帰呼び出しを実行し、次に再帰呼び出しの戻り値を取得して結果を計算するのが典型的なモデルです。このように、すべての再帰呼び出しから戻るまで、計算の結果は得られません。

末尾再帰では、最初に計算を実行し、次に再帰呼び出しを実行して、現在のステップの結果を次の再帰ステップに渡します。これにより、最後のステートメントが の形式になり(return (recursive-function params))ます。基本的に、特定の再帰ステップの戻り値は、次の再帰呼び出しの戻り値と同じです。

この結果、次の再帰ステップを実行する準備ができたら、現在のスタック フレームはもう必要ありません。これにより、ある程度の最適化が可能になります。実際、適切に作成されたコンパイラを使用すると、末尾再帰呼び出しでスタック オーバーフロースニッカーが発生することはありません。次の再帰ステップで現在のスタック フレームを再利用するだけです。Lispがこれを行うと確信しています。

于 2008-08-29T03:57:07.590 に答える
224

重要な点は、末尾再帰が基本的にループと同等であるということです。これはコンパイラの最適化だけの問題ではなく、表現力に関する基本的な事実です。これはどちらの方法にも当てはまります。フォームの任意のループを取ることができます

while(E) { S }; return Q

whereEとQは式で、Sは一連のステートメントであり、末尾再帰関数に変換します

f() = if E then { S; return f() } else { return Q }

もちろん、E、S、およびQは、いくつかの変数に対して興味深い値を計算するために定義する必要があります。たとえば、ループ機能

sum(n) {
  int i = 1, k = 0;
  while( i <= n ) {
    k += i;
    ++i;
  }
  return k;
}

末尾再帰関数と同等

sum_aux(n,i,k) {
  if( i <= n ) {
    return sum_aux(n,i+1,k+i);
  } else {
    return k;
  }
}

sum(n) {
  return sum_aux(n,1,0);
}

(末尾再帰関数をより少ないパラメーターを持つ関数で「ラッピング」することは、一般的な関数型イディオムです。)

于 2008-08-31T17:29:06.080 に答える
163

この書籍Programming in Luaからの抜粋は、適切な末尾再帰を作成する方法(Lua で、ただし Lisp にも適用する必要があります) と、なぜそれが優れているのかを示しています。

テールコール[テール再帰] は、コールに扮した goto の一種です。テール コールは、関数が最後のアクションとして別の関数を呼び出すときに発生するため、他に何もする必要がありません。たとえば、次のコードでは、への呼び出しgは末尾呼び出しです。

function f (x)
  return g(x)
end

f呼び出しの後g、他に何もすることはありません。このような状況では、呼び出された関数が終了したときに、プログラムは呼び出し元の関数に戻る必要はありません。したがって、末尾呼び出しの後、プログラムは呼び出し元の関数に関する情報をスタックに保持する必要はありません。...

適切なテール コールはスタック スペースを使用しないため、プログラムが実行できる「ネストされた」テール コールの数に制限はありません。たとえば、引数として任意の数を指定して次の関数を呼び出すことができます。スタックがオーバーフローすることはありません。

function foo (n)
  if n > 0 then return foo(n - 1) end
end

... 先ほども言いましたが、テールコールは goto の一種です。そのため、Lua での適切な末尾呼び出しの非常に便利なアプリケーションは、ステート マシンのプログラミングです。このようなアプリケーションは、関数によって各状態を表すことができます。状態を変更することは、特定の関数に移動する (または呼び出す) ことです。例として、単純な迷路ゲームを考えてみましょう。迷路にはいくつかの部屋があり、それぞれに最大 4 つのドア (北、南、東、西) があります。各ステップで、ユーザーは移動方向を入力します。その方向にドアがある場合、ユーザーは対応する部屋に行きます。それ以外の場合、プログラムは警告を出力します。目標は、最初の部屋から最後の部屋に移動することです。

このゲームは、現在の部屋が状態である典型的な状態マシンです。このような迷路は、部屋ごとに 1 つの関数で実装できます。テール コールを使用して、ある部屋から別の部屋に移動します。4 つの部屋がある小さな迷路は次のようになります。

function room1 ()
  local move = io.read()
  if move == "south" then return room3()
  elseif move == "east" then return room2()
  else print("invalid move")
       return room1()   -- stay in the same room
  end
end

function room2 ()
  local move = io.read()
  if move == "south" then return room4()
  elseif move == "west" then return room1()
  else print("invalid move")
       return room2()
  end
end

function room3 ()
  local move = io.read()
  if move == "north" then return room1()
  elseif move == "east" then return room4()
  else print("invalid move")
       return room3()
  end
end

function room4 ()
  print("congratulations!")
end

つまり、次のような再帰呼び出しを行うと、次のようになります。

function x(n)
  if n==0 then return 0
  n= n-2
  return x(n) + 1
end

これは末尾再帰ではありません。再帰呼び出しが行われた後も、その関数でやるべきこと (1 を追加) があるからです。非常に大きな数値を入力すると、スタック オーバーフローが発生する可能性があります。

于 2008-08-29T16:03:30.793 に答える
85

通常の再帰を使用すると、再帰呼び出しごとに別のエントリが呼び出しスタックにプッシュされます。再帰が完了すると、アプリは各エントリを一番下までポップする必要があります。

末尾再帰を使用すると、言語によっては、コンパイラがスタックを 1 つのエントリに折りたたむことができるため、スタック スペースを節約できます...大規模な再帰クエリは、実際にはスタック オーバーフローを引き起こす可能性があります。

基本的に、テール再帰は反復に最適化できます。

于 2008-08-29T03:55:30.120 に答える
78

専門用語ファイルには、末尾再帰の定義について次のように書かれています。

末尾再帰/n./

まだうんざりしていない場合は、末尾再帰を参照してください。

于 2008-08-29T07:21:31.390 に答える
73

言葉で説明する代わりに、ここに例を示します。これは階乗関数のスキーム バージョンです。 

(define (factorial x)
  (if (= x 0) 1
      (* x (factorial (- x 1)))))

これは、末尾再帰的な階乗のバージョンです。

(define factorial
  (letrec ((fact (lambda (x accum)
                   (if (= x 0) accum
                       (fact (- x 1) (* accum x))))))
    (lambda (x)
      (fact x 1))))

最初のバージョンでは、fact の再帰呼び出しが乗算式に入力されるため、再帰呼び出しを行うときに状態をスタックに保存する必要があることに気付くでしょう。末尾再帰バージョンでは、再帰呼び出しの値を待機する他の S 式はなく、それ以上行う作業がないため、状態をスタックに保存する必要はありません。原則として、Scheme の末尾再帰関数は一定のスタック スペースを使用します。

于 2008-08-29T03:57:08.667 に答える
53

末尾再帰とは、再帰アルゴリズムの最後の論理命令の最後にある再帰呼び出しを指します。

通常、再帰では、再帰呼び出しを停止し、呼び出しスタックのポップを開始する基本ケースがあります。古典的な例を使用すると、Lisp よりも C っぽいですが、階乗関数は末尾再帰を示しています。再帰呼び出しは、基本ケースの条件を確認した後に発生します。

factorial(x, fac=1) {
  if (x == 1)
     return fac;
   else
     return factorial(x-1, x*fac);
}

factorial の最初の呼び出しはfactorial(n)where fac=1(デフォルト値) で、n は factorial が計算される数です。

于 2008-08-29T03:57:05.170 に答える
29

つまり、スタック上の命令ポインターをプッシュする必要はなく、再帰関数の先頭にジャンプして実行を続行できます。これにより、関数はスタックをオーバーフローすることなく無期限に再帰できます。

このテーマに関するブログ投稿を書きました。このブログには、スタックフレームがどのように見えるかを示すグラフィカルな例があります。

于 2008-08-31T23:52:34.567 に答える
22

以下は、2 つの関数を比較する簡単なコード スニペットです。1 つ目は、与えられた数の階乗を見つけるための伝統的な再帰です。2 番目は末尾再帰を使用します。

非常にシンプルで直感的に理解できます。

再帰関数が末尾再帰かどうかを判断する簡単な方法は、基本ケースで具体的な値を返すかどうかです。1 や true などを返さないことを意味します。メソッドパラメータの1つのバリアントを返す可能性が高くなります。

もう1つの方法は、再帰呼び出しに追加、算術、変更などが含まれていないかどうかです...つまり、純粋な再帰呼び出しに他なりません。

public static int factorial(int mynumber) {
    if (mynumber == 1) {
        return 1;
    } else {            
        return mynumber * factorial(--mynumber);
    }
}

public static int tail_factorial(int mynumber, int sofar) {
    if (mynumber == 1) {
        return sofar;
    } else {
        return tail_factorial(--mynumber, sofar * mynumber);
    }
}
于 2010-12-19T15:52:45.020 に答える
21

私が理解する最善の方法は、最後の呼び出し(または末尾の呼び出し) が関数自体tail call recursionである再帰の特殊なケースです。

Python で提供されている例を比較します。

def recsum(x):
 if x == 1:
  return x
 else:
  return x + recsum(x - 1)

^再帰

def tailrecsum(x, running_total=0):
  if x == 0:
    return running_total
  else:
    return tailrecsum(x - 1, running_total + x)

^末尾再帰

一般的な再帰バージョンでわかるように、コード ブロックの最後の呼び出しはx + recsum(x - 1). したがって、recsumメソッドを呼び出した後、別の操作がありx + ..ます。

ただし、末尾再帰バージョンでは、コード ブロック内の最終呼び出し (または末尾呼び出し) はtailrecsum(x - 1, running_total + x)、最後の呼び出しがメソッド自体に対して行われ、その後は操作されないことを意味します。

この点は重要です。なぜなら、ここで見られる末尾再帰はメモリを増加させないためです。基盤となる VM が末尾位置 (関数で評価される最後の式) で自分自身を呼び出している関数を確認すると、現在のスタック フレームが削除されるためです。テールコール最適化 (TCO) として知られています。

編集

注意。上記の例は、ランタイムが TCO をサポートしていない Python で書かれていることに注意してください。これはポイントを説明するための単なる例です。TCO は、Scheme、Haskell などの言語でサポートされています

于 2015-12-21T11:47:11.337 に答える
13

Java では、フィボナッチ関数の可能な末尾再帰実装を次に示します。

public int tailRecursive(final int n) {
    if (n <= 2)
        return 1;
    return tailRecursiveAux(n, 1, 1);
}

private int tailRecursiveAux(int n, int iter, int acc) {
    if (iter == n)
        return acc;
    return tailRecursiveAux(n, ++iter, acc + iter);
}

これを標準の再帰的実装と比較してください。

public int recursive(final int n) {
    if (n <= 2)
        return 1;
    return recursive(n - 1) + recursive(n - 2);
}
于 2008-10-14T21:20:20.113 に答える
12

私は Lisp プログラマーではありませんが、これが役立つと思います。

基本的には、再帰呼び出しが最後になるようなプログラミング スタイルです。

于 2008-08-29T03:50:50.943 に答える
10

これは、末尾再帰を使用して階乗を行う Common Lisp の例です。スタックレスの性質により、非常に大きな階乗計算を実行できます...

(defun ! (n &optional (product 1))
    (if (zerop n) product
        (! (1- n) (* product n))))

そして、楽しみのためにあなたは試すことができます(format nil "~R" (! 25))

于 2012-03-11T06:07:08.933 に答える
9

つまり、末尾再帰では、関数の最後のステートメントとして再帰呼び出しが行われるため、再帰呼び出しを待つ必要がありません。

したがって、これは末尾再帰です。つまり、N(x - 1, p * x) は関数の最後のステートメントであり、コンパイラは for ループ (階乗) に最適化できることを賢く判断します。2 番目のパラメーター p は、中間積の値を保持します。

function N(x, p) {
   return x == 1 ? p : N(x - 1, p * x);
}

これは、上記の階乗関数を末尾再帰ではない方法で記述したものです (ただし、一部の C++ コンパイラでは最適化できる場合があります)。

function N(x) {
   return x == 1 ? 1 : x * N(x - 1);
}

しかし、これはそうではありません:

function F(x) {
  if (x == 1) return 0;
  if (x == 2) return 1;
  return F(x - 1) + F(x - 2);
}

「末尾再帰を理解する – Visual Studio C++ – アセンブリ ビュー」というタイトルの長い投稿を書きました。

ここに画像の説明を入力

于 2016-11-08T23:21:00.937 に答える
8

これは、末尾再帰に関するコンピューター プログラムの構造と解釈からの抜粋です。

反復と再帰を対比して、再帰プロセスの概念を再帰手順の概念と混同しないように注意する必要があります。手続きを再帰的であると説明するとき、手続き定義が (直接的または間接的に) 手続き自体を参照しているという構文上の事実を参照しています。しかし、プロセスを、たとえば線形再帰的なパターンに従っていると説明するときは、プロシージャがどのように記述されるかという構文についてではなく、プロセスがどのように進化するかについて話しているのです。fact-iter などの再帰的手続きを反復プロセスの生成と呼ぶのは、気がかりに思えるかもしれません。ただし、プロセスは実際には反復的です。その状態は 3 つの状態変数によって完全にキャプチャされ、インタープリターはプロセスを実行するために 3 つの変数のみを追跡する必要があります。

プロセスとプロシージャの区別がわかりにくい理由の 1 つは、一般的な言語 (Ada、Pascal、C を含む) のほとんどの実装が、再帰プロシージャの解釈でメモリ量が消費され、そのメモリ量が再帰プロシージャとともに増加するように設計されていることです。記述されたプロセスが原則として反復的である場合でも、プロシージャ コールの数。結果として、これらの言語は、do、repeat、until、for、while などの特別な目的の「ループ構造」に頼ることによってのみ、反復プロセスを記述できます。Scheme の実装には、この欠陥はありません。反復プロセスが再帰的な手順で記述されていても、定数空間で反復プロセスを実行します。このプロパティを持つ実装は、末尾再帰と呼ばれます。末尾再帰の実装では、通常のプロシージャ呼び出しメカニズムを使用して反復を表現できるため、特別な反復構造は構文糖衣としてのみ役立ちます。

于 2016-06-27T09:41:22.613 に答える
8

tailrecsumこれは、前述の関数の Perl 5 バージョンです。

sub tail_rec_sum($;$){
  my( $x,$running_total ) = (@_,0);

  return $running_total unless $x;

  @_ = ($x-1,$running_total+$x);
  goto &tail_rec_sum; # throw away current stack frame
}
于 2008-10-01T22:06:39.233 に答える
7

Tail Recursion は、通常の再帰に比べてかなり高速です。祖先呼び出しの出力が追跡のためにスタックに書き込まれないため、高速です。しかし、通常の再帰では、すべての先祖がスタックに書き込まれた出力を呼び出して追跡します。

于 2019-06-05T12:50:35.100 に答える
5

再帰とは、それ自体を呼び出す関数を意味します。例えば：

(define (un-ended name)
  (un-ended 'me)
  (print "How can I get here?"))

末尾再帰とは、関数を終了する再帰を意味します。

(define (un-ended name)
  (print "hello")
  (un-ended 'me))

ほら、終わりのない関数（Scheme専門用語の手順）が最後に行うことは、それ自体を呼び出すことです。別の（より便利な）例は次のとおりです。

(define (map lst op)
  (define (helper done left)
    (if (nil? left)
        done
        (helper (cons (op (car left))
                      done)
                (cdr left))))
  (reverse (helper '() lst)))

ヘルパー手順では、左がnilでない場合に最後に行うことは、自分自身を呼び出すことです（何かをconsし、cdrを実行した後）。これは基本的に、リストをマップする方法です。

末尾再帰には、インタプリタ（または言語とベンダーによってはコンパイラ）がそれを最適化し、whileループと同等のものに変換できるという大きな利点があります。実際のところ、Schemeの伝統では、ほとんどの「for」ループと「while」ループは末尾再帰方式で実行されます（私が知る限り、forとwhileはありません）。

于 2008-09-02T14:08:26.420 に答える