再帰的に考える

私は料理のものがあまり得意ではありません、しかし、私は伝統的なポーランド料理のすべての時間崇拝者です.私は先週仕事から数日休みをとりました.そして、すべての日がポーランドの繊細さに私の手を得ることなく飛ぶことができないと決めました.今、私はどこから始めるべきかさえわからないと理解します.さて、友達は何ですか?今、忍耐でこれを読んでください!私はワルシャワで「Darek」に電話をして、彼に私に若干の方向を与えることができるかどうか尋ねました.ダレクは、ちょうどもう一つのオタクであると、彼が野菜をする方法を知っていると私に話しましたthe filling ) しかし、彼は別の友人に、ラップを準備する方法を尋ねる.彼は私を抱きしめて、彼の友人、マレックを呼ぶために進んだ.マレックは、彼が実際にラップをする方法を知っているとDarekに言います、しかし、彼はAlekを呼びます私の友人であるソースは重要です.彼は、同様にDarekを持ちます.愚か!alek、隣人は最終的にもう一人の友人を呼びませんが、ソースのレシピを与えます.マレックはAlekがソースについて彼に話したものとラップの彼のレシピを結合して、それをただ単に私に完全な情報を届けるために充填のレシピとこの情報を結合するのを待っていたDarekにそれを伝えます.長い日、しかし、私は最終的に、私が必要としたものを持っています.
コンテキストを切り替えます.既に呼び出しスタックを視覚化しましたか?JavaScriptランタイムでは、関数の実行を追跡するために呼び出しスタックを使用します.メモリ上の関数の実行コンテキストを規則的に配置したスタック以外は、現在実行中の関数がトップに留まるようにします.私の例によって行って、それが実際に描写される方法を見てください.関数getRecorpeHelp ()への定期的な呼び出しと考えてください.

let alek = { name: 'Alek', friend: null, ingr: 'sauce', done: true };

let marek = { name: 'Marek', friend: alek, ingr: 'wrap' };

let darek = { name: 'Darek', friend: marek, ingr: 'filling' };

function getRecipeHelp(friend) {
  if(friend.done) {
    // bail out condition
    return friend.ingr;
  }
  return friend.ingr + ' + ' + getRecipeHelp(friend.friend);
}

// Here we call Darek to get help with the recipe who then calls his friend Marek and Marek finally calls his friend Alek
console.log(getRecipeHelp(darek)); // "filling + wrap + sauce"

Try on Codepen
あなたが本当によく例を消化したと仮定して、私は今あなたに尋ねることができます、あなたはどのように'再帰'を定義すると思いますか?アカデミックな定義は「非葉機能自体を呼び出す」と言います.個人的な注意点では、回帰値が最終的な出力に順番に解決できるように、保釈条件を満たすクエストとして再帰を理解しています.あなたが定義するすべての再帰関数が保釈条件を持たなければならないと理解しない限り、これはあなたを少し混乱させるかもしれません.大まかに言えば、どんな再帰的な関数についても3つのことを覚えておいてください.あの3つのものは何ですか.

1. You should start with thinking of the bail out condition
2. Understand that the values start resolving in LIFO fashion to finally render the output
3. Recursively call the function itself but with a different argument ofcourse ( Make sure you'e moving towards the bail out condition)

保留条件は、例では非常に目に見えますが、より明確にするために、あなたが再帰的な呼び出しを止めるためにこのチェックを持っていないならば、あなたは機能が戻ることなくスタックの上で積み重なっているスタックオーバーフローで終わるかもしれません.LIFOの値の値の解像度によって、すべての意味では、スタック内の関数は、最後の関数(保釈条件を満たす)が返されるまで待機し続けることになります.手でこの情報の多くで、先に行くと古典的な要因関数を実装してみてください.

function factorial(n) {
  if(n<2) {
    // bail out condition
    return 1;
  } 
  // make sure you're moving towards the bail out condition and not away from it
  return n * factorial(n-1);
}

Try on Codepen

CodeAcademyから借りたイラスト
イラストは自己説明的だと思います.そうでない場合は、別の例をカバーします.フィボナッチのシリーズを取得します.ほとんど誰も野生では、fibinacciシリーズを知らないでしょうが、それでも、それはこの0、1、1、2、3、5、8、13、21、34、55、89のように行きます.シリーズの3番目から始まる他のすべての数は、前の2の合計です.Fibonacciは魔法、先に行くと読むthis .

// 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... starts with 0 and 1 and then each number is the sum of previous two numbers in the series

function fib(n) {
  return n <= 1 
  ? n // bail out condition
  : fib(n-1) + fib(n-2); // make sure you're moving towards the bail out condition and not away from it
}
console.log(fib(10)); // 55

Try on Codepen
概念的に、我々が因数分解のためにしたものとは大きく異なりません.すべての再帰関数を数学関数として考えてください.おそらく、それはより明白になるでしょう.我々は(n <= 1)で保釈条件を持っています、そこで、我々は単に1未満のどんな引数も返します.さもなければ、我々は進んで、n - 1とn - 2のためにFIB機能への再帰的な呼び出しをします.さて、それは私にn fifiacciメンバーを与えるだけです.どのように、あなたは全部のシリーズを印刷しますか?ループを使用しないようにし、再帰関数Showfibそれはすぐにシリーズを印刷します.Here's the code .
ああ!FIB ( 999999 )やFIB ( 9999999 )のようなFIB関数を呼び出します.あなたは既に結果を見るか?あなたがそれを見るだけで言うことができるように、巨大な膨大な数になるでしょう、あなたのブラウザーはこれをあきらめて、這い始めるかもしれません、あるいは、呼び出しスタックの内容に応じてスタックオーバーフロー例外さえ得るかもしれません.Factorialプログラムのスタックを示すイラストに切り替えます.あなたは999999の機能は、すべての後継者のいくつかの値を返すのを待って積んで想像することはできますか?どうやってこれを回避できますか?実際にアウトウェイだが、それはトレードオフのようなものだ.私たちはそれを呼び出すProper Tail Calls (PTC) . 関数の最後の行をチェックアウトします.階乗関数ではreturn文を返します.戻り値のステートメントには

1. a multiplier i.e. n
2. a recursive call i.e. factorial(n-1)

再帰的な呼び出しが何らかの値を返すのを待っている乗数を持っているので、この関数はスタックから無効にすることはできません.これは再帰的な呼び出しが戻った後に終了するためにこの保留中の仕事(Nによって掛け算)をします.我々は、乗算器を待っての代わりに、再帰的な呼び出しには、製品を渡すか?さて、保留中の仕事が毎回再帰的な呼び出しに委任されるので、エンジンは待機中の機能で実行スタックを混雑させ続ける必要はありません.

function factorial(n, product = 1) {
  return n < 1
  ? product
  : factorial(n-1, n * product);
}

console.log(factorial(99)); // 9.332621544394415e+155
console.log(factorial(999)); // Infinity
console.log(factorial(999999)); // Error- Maximum call stack size exceeded 

Try on Codepen
あなたは、それが現在よりよく働くのを見ます.無制限のフレームとする関数を再帰的に呼び出すことができます何回もしたいですか?PTCに言及する前に、私はそれがトレードオフであると言いました.スタックトレースのトレードオフ.あなたは、もはやあなたの機能のための簡単なデバッグを持っていません.関数フレームが実行スタック内のスペースを作成するために失われるため、エラーをトレースしても表示されません.Read more here . だからあなたの馬を保持し、最適化された再帰的な解決策を選ぶ前に考える.今、あなたは関数の末尾に関数コールを配置するたびに失火ではないと考えている?スタックトレースを失う必要はありません.良いニュースと悪いニュース、私が適切な尾呼び出しについてあなたに話したすべては、単にJavascriptCore以外のJSエンジン(アップルによって)で働きません.アップルは、テールコール最適化(TCO)と呼ぶのが好きです.TCOは、実際にあなたの関数実行を最適化するために、PTCの一歩を踏み出します.v 8 Infactはしばらくの間これをサポートしました、しかし、同じ理由とおそらく若干のバグのために、それを降ろしました.クロムの場合は、デバッガでこれをテストできます.あるいは、あなたはthis . V 8はすべての関数呼び出しのフレームを作成し、コードを書く方法に関係なくスタック内に保持します.したがって、リミットをリミットすると、スタックオーバーフロー例外が得られます.PTCの明示的なバージョンは議論されています.彼らはそれを呼び出すSyntactic Tail Calls (STC) .

関数呼び出しの積み重ね

もともとここに投稿-

https://mayankav.webflow.io/blog/think-recursive