末尾再帰とは何ですか?

https://stackoverflow.com/questions/33923

09-06-2019
|

質問

Lisp を学び始めたときに、この用語に出会いました。 末尾再帰的. 。正確にはどういう意味ですか?

解決

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

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

function recsum(x) {
    if (x===1) {
        return x;
    } 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)))
15

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

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

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

を呼び出した場合に発生する一連のイベントは次のとおりです。 tailrecsum(5), (これは実質的には tailrecsum(5, 0), デフォルトの 2 番目の引数のため)。

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

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

注記：元の回答では、Python の例が使用されていました。最新の JavaScript インタープリターがサポートされるため、これらは JavaScript に変更されました。テールコールの最適化しかし、Python インタプリタはそうではありません。

他のヒント

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

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

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

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

while(E) { S }; return Q

どこ E そして 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);
}

(末尾再帰関数をパラメーターの少ない関数で「ラップ」することは、一般的な関数のイディオムです。)

この本からの抜粋 Lua でのプログラミング ショー適切な末尾再帰を行う方法 (Lua ですが、Lisp にも適用する必要があります) とそれが優れている理由。

あ テールコール 尾の再帰]は、呼びかけにdressした一種のgotoです。テールコールは、関数が別のアクションとして別のものを呼び出すと発生するため、他に何もすることはありません。たとえば、次のコードでは、 g は末尾呼び出しです:
function f (x)
  return g(x)
end
後 f 電話をかける g, 、他に何もすることはありません。このような状況では、プログラムは、呼び出された関数が終了したときに呼び出し関数に戻る必要はありません。したがって、テールコールの後、プログラムはスタック内の呼び出し関数に関する情報を保持する必要はありません。...

適切なテールコールではスタックスペースが使用されないため、プログラムが作成できる「ネストされた」テールコールの数に制限はありません。たとえば、任意の数値を引数として次の関数を呼び出すことができます。スタックにオーバーフローすることはありません。
function foo (n)
  if n > 0 then return foo(n - 1) end
end
...先ほど言ったように、テールコールは一種のゴットです。そのため、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 を追加) がまだあるため、これは末尾再帰ではありません。非常に大きな数値を入力すると、スタックオーバーフローが発生する可能性があります。

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

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

基本的に、末尾再帰は反復に最適化できます。

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

(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 末尾再帰関数は一定のスタック領域を使用します。

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

末尾再帰 /n./

まだ飽きていない場合は、末尾再帰を参照してください。

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

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

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

階乗への最初の呼び出しは次のようになります。 factorial(n) どこ fac=1 (デフォルト値)、n は階乗を計算する数値です。

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

私は、ブログこの件名に投稿してください。スタックフレームがどのようなものかを示すグラフィカルな例が含まれています。

以下は 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);
    }
}

私にとって理解するための最良の方法 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)として知られています。

編集

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

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);
}

以下は、末尾再帰を使用して階乗を行う Common Lisp の例です。スタックレスの性質により、非常に大規模な階乗計算を実行する可能性があります。

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

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

私は Lisp プログラマーではありませんが、次のように思います。これ役立ちます。

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

つまり、末尾再帰には再帰呼び出しが含まれます。最後ステートメントを関数内に追加することで、再帰呼び出しを待つ必要がなくなります。

つまり、これは末尾再帰です。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++ – アセンブリビュー"

これは Perl 5 バージョンです。 tailrecsum 前述した機能。

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
}

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

対照的な反復と再帰では、再帰プロセスの概念を再帰的手順の概念と混同しないように注意する必要があります。手順を再帰的であると説明する場合、手順定義が手順自体を（直接的または間接的に）参照するという構文的な事実に言及しています。しかし、プロセスを、たとえば直線的に再帰的なパターンに従うと説明する場合、プロセスがどのように進化するかについてではなく、プロセスがどのように進化するかについて話しています。ファクトアイテムなどの再帰的手順を反復プロセスの生成と呼んでいるのは気がかりなことかもしれません。ただし、このプロセスは実際には反復的です。その状態は3つの状態変数によって完全にキャプチャされ、インタープリターはプロセスを実行するために3つの変数のみを追跡する必要があります。

プロセスと手順の区別が混乱している可能性のある理由の1つは、一般的な言語（ADA、Pascal、Cを含む）のほとんどの実装が、再帰手順の解釈が成長するメモリを消費するように設計されていることです。説明されているプロセスが原則として反復的であっても、手順呼び出しの数。結果として、これらの言語は、do、繰り返し、繰り返し、for、for、whileなどの特別な目的の「ループ構造」に頼ることによってのみ、反復プロセスを記述できます。スキームの実装は、この欠陥を共有しません。反復プロセスが再帰手順によって記述されている場合でも、一定の空間で反復プロセスを実行します。このプロパティを使用した実装は、Tail-Recursiveと呼ばれます。テール再転用の実装により、通常の手順コールメカニズムを使用して反復を表現でき、特別な反復構造は構文糖としてのみ役立ちます。

末尾再帰はあなたが今生きている人生です。「以前の」フレームに戻る理由も手段もないため、同じスタックフレームを常に何度もリサイクルします。過去は終わって終わったので、捨てても大丈夫です。プロセスが必然的に停止するまで、永遠に未来に進む 1 つのフレームを取得します。

_{一部のプロセスが追加のフレームを使用する可能性があるものの、スタックが無限に増大しない場合には末尾再帰的であるとみなされることを考慮すると、この類似性は崩れます。}

尾の再帰は、関数が再帰コールの返された後に計算が行われない関数の最後に（「テール」）関数が呼び出される再帰関数です。多くのコンパイラが最適化して、再帰コールをテールの再帰または反復コールに変更します。

数値の階乗を計算する問題を考えてみましょう。

簡単なアプローチは次のようになります。

  factorial(n):

    if n==0 then 1

    else n*factorial(n-1)

Factorial(4) を呼び出すとします。再帰ツリーは次のようになります。

       factorial(4)
       /        \
      4      factorial(3)
     /             \
    3          factorial(2)
   /                  \
  2                factorial(1)
 /                       \
1                       factorial(0)
                            \
                             1

上記の場合の最大再帰深さは O(n) です。

ただし、次の例を考えてみましょう。

factAux(m,n):
if n==0  then m;
else     factAux(m*n,n-1);

factTail(n):
   return factAux(1,n);

ACTTail(4) の再帰ツリーは次のようになります。

factTail(4)
   |
factAux(1,4)
   |
factAux(4,3)
   |
factAux(12,2)
   |
factAux(24,1)
   |
factAux(24,0)
   |
  24

ここでも、最大再帰深さは O(n) ですが、どの呼び出しもスタックに余分な変数を追加しません。したがって、コンパイラはスタックを廃止できます。

末尾呼び出し再帰と非末尾呼び出し再帰の間の主要な違いのいくつかを理解するには、これらの手法の .NET 実装を調べることができます。

C#、F#、および C++\CLI の例をいくつか示した記事を次に示します。 C#、F#、および C++\CLI での末尾再帰の冒険.

C# は末尾呼び出し再帰を最適化しませんが、F# は最適化します。

原理の違いには、ループとループが関係します。ラムダ計算。C# はループを念頭に置いて設計されているのに対し、F# はラムダ計算の原理に基づいて構築されています。ラムダ計算の原理に関する非常に優れた (そして無料の) 本については、以下を参照してください。コンピュータープログラムの構造と解釈、Abelson、Sussman、および Sussman 著.

F# の末尾呼び出しについては、非常に優れた入門記事を参照してください。 F# の末尾呼び出しの詳細な紹介. 。最後に、非末尾再帰と末尾呼び出し再帰 (F# の場合) の違いについて説明した記事を以下に示します。末尾再帰 vs.F シャープの非末尾再帰.

C# と F# の間の末尾呼び出し再帰の設計の違いについて知りたい場合は、次を参照してください。 C# および F# での末尾呼び出しオペコードの生成.

C# コンパイラーによる末尾呼び出しの最適化の実行を妨げる条件を知りたい場合は、この記事を参照してください。 JIT CLR テールコール条件.

再帰には 2 つの基本的な種類があります。 ヘッド再帰 そして 末尾再帰。

で ヘッド再帰, 、関数は再帰的な呼び出しを行い、たとえば再帰コールの結果を使用して、さらに計算を実行します。

で 末尾再帰的 関数、すべての計算が最初に行われ、再帰呼び出しが最後に起こることです。

から引用これ超素晴らしい投稿。ぜひ読んでみてください。

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

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

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

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

終了していない関数 (スキーム用語ではプロシージャ) が行う最後のことは、それ自体を呼び出すことです。別の (より便利な) 例は次のとおりです。

(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 something と cdr something の後)。これは基本的にリストをマップする方法です。

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

この質問には素晴らしい答えがたくさんあります...しかし、「尾の再帰」を定義する方法、または少なくとも「適切な尾の再帰」を定義する方法についての代替のテイクで、私はチャイムを鳴らさざるを得ません。すなわち：これをプログラム内の特定の式のプロパティとして見るべきでしょうか?それとも、それをあるものの特性として見るべきでしょうか。 プログラミング言語の実装?

後者の見方について詳しくは、古典的なものがあります。紙 Will Clinger 著「適切な末尾再帰と空間効率」(PLDI 1998) では、プログラミング言語実装のプロパティとして「適切な末尾再帰」を定義しました。この定義は、実装の詳細 (呼び出しスタックが実際にランタイムスタックを介して表現されるか、ヒープに割り当てられたフレームのリンクリストを介して表現されるかなど) を無視できるように構築されています。

これを達成するために、漸近分析を使用します。通常見られるようなプログラムの実行時間ではなく、むしろプログラムです スペースの使用量. 。このようにして、ヒープ割り当てリンクリストとランタイムコールスタックのスペース使用量は漸近的に同等になります。そのため、プログラミング言語の実装の詳細 (実際には確かにかなり重要な詳細ですが、特定の実装が「プロパティ末尾再帰的」であるという要件を満たしているかどうかを判断しようとすると、かなり混乱する可能性があります) を無視することになります。 )

この論文は、次のような理由から注意深く研究する価値があります。

それは帰納的に定義します。 テール式 そして テールコール プログラムの。(そのような定義、およびそのような呼び出しがなぜ重要であるかは、ここで与えられた他の回答のほとんどの主題であるようです。)

本文の雰囲気を示すために、これらの定義を以下に示します。
定義 1 の テール式 Core Schemeで書かれたプログラムは帰納的に次のように定義されます。
1. ラムダ式の本体は末尾式です
2. もし (if E0 E1 E2) が末尾式の場合は両方 E1 そして E2 尾の表現です。
3. これ以外に末尾式はありません。
定義 2 あ テールコール はプロシージャ呼び出しである末尾式です。

(末尾再帰呼び出し、または論文に記載されているように「自己末尾呼び出し」は、プロシージャ自体が呼び出される末尾呼び出しの特殊なケースです。)

これは、コアスキームを評価するための 6 つの異なる「マシン」の正式な定義を提供します。各マシンは同じ観察可能な動作を持ちます。 を除外する のために 漸近的 それぞれが属する空間複雑度クラス。

たとえば、それぞれのマシンの定義を与えた後、1.スタックベースのメモリ管理、2.ガベージコレクションは行われるが末尾呼び出しは行われない、3.ガベージコレクションとテールコールに加えて、この論文ではさらに高度なストレージ管理戦略 (4.「evlis 末尾再帰」。末尾呼び出しの最後の部分式引数の評価全体にわたって環境を保持する必要がありません。 5.閉鎖環境を減少させるただそのクロージャの自由変数、および 6.いわゆる「セーフ・フォー・スペース」セマンティクスは次のように定義されます。アペルとシャオ.
マシンが実際に 6 つの異なる空間複雑さのクラスに属していることを証明するために、この論文では、比較対象のマシンのペアごとに、一方のマシンでは漸近的な空間爆発を明らかにし、もう一方のマシンでは空間爆発を明らかにしないプログラムの具体例を示しています。

(今自分の回答を読んでいると、実際に重要なポイントをうまく理解できているかどうかわかりません。クリンガー紙. 。しかし、残念ながら、今はこの答えを作成することにこれ以上の時間を費やすことができません。)

再帰関数は次のような関数です。 自ら呼び出します

これにより、プログラマーは、 最小限のコード量.

欠点は、次のことができることです。 無限ループを引き起こす およびその他の予期しない結果が発生した場合 正しく書かれていない.

両方説明します 単純再帰関数と末尾再帰関数

を書くには 単純な再帰関数

考慮すべき最初のポイントは、IFループであるループから出てくることをいつ決める必要があるかです
2つ目は、独自の関数の場合にどのような処理を行うかです。

与えられた例から:

public static int fact(int n){
  if(n <=1)
     return 1;
  else 
     return n * fact(n-1);
}

上記の例から

if(n <=1)
     return 1;

ループをいつ終了するかが決定要因となる

else 
     return n * fact(n-1);

実際に行うべき処理は何か

理解しやすいように、タスクを 1 つずつ分解してみましょう。

実行すると内部で何が起こるか見てみましょう fact(4)

n=4を代入

public static int fact(4){
  if(4 <=1)
     return 1;
  else 
     return 4 * fact(4-1);
}

If ループが失敗するので次へ進みます else ループして戻ります 4 * fact(3)

スタックメモリには、 4 * fact(3)

n=3を代入

public static int fact(3){
  if(3 <=1)
     return 1;
  else 
     return 3 * fact(3-1);
}

If ループが失敗するので次へ進みます else ループ

それで戻ります 3 * fact(2)

```4 * fat(3)`` を呼び出したことを思い出してください。

の出力 fact(3) = 3 * fact(2)

これまでのスタックには 4 * fact(3) = 4 * 3 * fact(2)

スタックメモリには、 4 * 3 * fact(2)

n=2を代入

public static int fact(2){
  if(2 <=1)
     return 1;
  else 
     return 2 * fact(2-1);
}

If ループが失敗するので次へ進みます else ループ

それで戻ります 2 * fact(1)

私たちが電話したことを覚えておいてください 4 * 3 * fact(2)

の出力 fact(2) = 2 * fact(1)

これまでのスタックには 4 * 3 * fact(2) = 4 * 3 * 2 * fact(1)

スタックメモリには、 4 * 3 * 2 * fact(1)

n=1を代入

public static int fact(1){
  if(1 <=1)
     return 1;
  else 
     return 1 * fact(1-1);
}

If ループは真です

それで戻ります 1

私たちが電話したことを覚えておいてください 4 * 3 * 2 * fact(1)

の出力 fact(1) = 1

これまでのスタックには 4 * 3 * 2 * fact(1) = 4 * 3 * 2 * 1

最後に、結果は、 事実(4) = 4 * 3 * 2 * 1 = 24

の 末尾再帰 だろう

public static int fact(x, running_total=1) {
    if (x==1) {
        return running_total;
    } else {
        return fact(x-1, running_total*x);
    }
}

n=4を代入

public static int fact(4, running_total=1) {
    if (x==1) {
        return running_total;
    } else {
        return fact(4-1, running_total*4);
    }
}

If ループが失敗するので次へ進みます else ループして戻ります fact(3, 4)

スタックメモリには、 fact(3, 4)

n=3を代入

public static int fact(3, running_total=4) {
    if (x==1) {
        return running_total;
    } else {
        return fact(3-1, 4*3);
    }
}

If ループが失敗するので次へ進みます else ループ

それで戻ります fact(2, 12)

スタックメモリには、 fact(2, 12)

n=2を代入

public static int fact(2, running_total=12) {
    if (x==1) {
        return running_total;
    } else {
        return fact(2-1, 12*2);
    }
}

If ループが失敗するので次へ進みます else ループ

それで戻ります fact(1, 24)

スタックメモリには、 fact(1, 24)

n=1を代入

public static int fact(1, running_total=24) {
    if (x==1) {
        return running_total;
    } else {
        return fact(1-1, 24*1);
    }
}

If ループは真です

それで戻ります running_total

の出力 running_total = 24

最後に、結果は、 ファクト(4,1) = 24

再帰についてはすでに多くの人がここで説明しています。Riccardo Terrell 著『Concurrency in .NET, Modern Patterns of Concurrent andParallel Programming』という本から、再帰がもたらすいくつかの利点についての考えをいくつか引用したいと思います。

「機能的再帰は、状態の突然変異を避けるため、FPで反復する自然な方法です。各反復中に、新しい値がループコンストラクターに渡され、代わりに更新されます（変異）。さらに、再帰関数を構成することができ、プログラムをよりモジュール化し、並列化を活用する機会を導入することができます。」

同じ本の末尾再帰に関する興味深いメモもいくつか紹介します。

Tail-Call Recursionは、通常の再帰関数をリスクや副作用なしに大きな入力を処理できる最適化されたバージョンに変換する手法です。

最適化としてテールコールの主な理由は、データの局所性、メモリの使用量、キャッシュの使用を改善することです。テールコールを行うことにより、Calleeは発信者と同じスタックスペースを使用します。これにより、メモリ圧力が低下します。同じメモリが後続の発信者のために再利用され、古いキャッシュラインを追い出して新しいキャッシュラインのスペースを作るのではなく、キャッシュにとどまることができるため、キャッシュがわずかに改善されます。

あ 末尾再帰的 function は再帰関数であり、戻る前に行う最後の操作は再帰関数呼び出しです。つまり、再帰関数呼び出しの戻り値がすぐに返されます。たとえば、コードは次のようになります。

def recursiveFunction(some_params):
    # some code here
    return recursiveFunction(some_args)
    # no code after the return statement

を実装するコンパイラとインタプリタ テールコールの最適化 または テールコールの除去 再帰コードを最適化してスタックのオーバーフローを防ぐことができます。コンパイラーまたはインタープリター (CPython インタープリターなど) が末尾呼び出しの最適化を実装していない場合、この方法でコードを作成しても追加の利点はありません。

たとえば、これは Python の標準的な再帰階乗関数です。

def factorial(number):
    if number == 1:
        # BASE CASE
        return 1
    else:
        # RECURSIVE CASE
        # Note that `number *` happens *after* the recursive call.
        # This means that this is *not* tail call recursion.
        return number * factorial(number - 1)

これは階乗関数の末尾呼び出し再帰バージョンです。

def factorial(number, accumulator=1):
    if number == 0:
        # BASE CASE
        return accumulator
    else:
        # RECURSIVE CASE
        # There's no code after the recursive call.
        # This is tail call recursion:
        return factorial(number - 1, number * accumulator)
print(factorial(5))

(これは Python コードですが、CPython インタープリターは末尾呼び出しの最適化を行わないため、コードをこのように配置しても実行時の利点はありません。)

階乗例に示すように、末尾呼び出しの最適化を利用するには、コードをもう少し読みにくくする必要がある場合があります。(たとえば、基本ケースは少し直感的ではありません。 accumulator パラメータは一種のグローバル変数として効果的に使用されます。)

ただし、末尾呼び出しの最適化の利点は、スタックオーバーフローエラーを防止できることです。(再帰的アルゴリズムの代わりに反復アルゴリズムを使用しても、これと同じ利点が得られることに注意してください。)

スタックオーバーフローは、コールスタックにプッシュされたフレームオブジェクトが多すぎる場合に発生します。フレームオブジェクトは、関数が呼び出されるときに呼び出しスタックにプッシュされ、関数が返されるときに呼び出しスタックからポップされます。フレームオブジェクトには、ローカル変数や関数が戻ったときにコードのどの行に戻るかなどの情報が含まれています。

再帰関数が戻らずに再帰呼び出しを多すぎると、呼び出しスタックがフレームオブジェクトの制限を超える可能性があります。(数値はプラットフォームによって異なります。Python では、デフォルトで 1000 フレームオブジェクトです。)これにより、 スタックオーバーフロー エラー。（このウェブサイトの名前の由来はここにあります！）

ただし、再帰関数が最後に再帰呼び出しを行ってその戻り値を返すことであれば、現在のフレームオブジェクトをコールスタックに保持しておく必要がある理由はありません。結局のところ、再帰関数呼び出しの後にコードがない場合、現在のフレームオブジェクトのローカル変数を保持する理由はありません。したがって、現在のフレームオブジェクトを呼び出しスタックに保持するのではなく、すぐに削除できます。この結果、呼び出しスタックのサイズは増加せず、スタックオーバーフローが発生することはありません。

コンパイラーまたはインタープリターには、末尾呼び出しの最適化がいつ適用できるかを認識できるように、末尾呼び出しの最適化機能が必要です。その場合でも、再帰関数内のコードを再配置して末尾呼び出しの最適化を利用する場合がありますが、この可読性の低下の可能性を最適化する価値があるかどうかはあなた次第です。

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

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow