Javascriptでの再帰の簡単な紹介

この関数は、誰かが停止するまで自分自身を呼び出します。

再帰は、新しい開発者にとって難しいと感じる可能性があります。おそらくそれは、多くのリソースがアルゴリズムの例(フィボナッチ、リンクリスト)を使用してそれを教えているためです。この作品は、1つの簡単な例を使用して、物事をわかりやすく紹介することを願っています。

コアアイデア

再帰とは、誰かが停止するまで関数がそれ自体を呼び出すことです。誰もそれを止めなければ、それは永遠に繰り返されます(それ自体を呼び出します)。

これはパトリックではありません

再帰関数を使用すると、作業単位を複数回実行できます。これはまさにfor/whileループが私たちに達成させてくれることです!ただし、問題を解決するためのより洗練されたアプローチが再帰的ソリューションである場合もあります。

カウントダウン機能

与えられた数からカウントダウンする関数を作成しましょう。このように使います。

countDownFrom(5); // 5 // 4 // 3 // 2 // 1 

そして、これがこの問題を解決するためのアルゴリズムです。

  1. と呼ばれる1つのパラメータを取りますnumber。これが私たちの出発点です。
  2. number下から0に移動し、途中でそれぞれをログに記録します。

forループアプローチから始めて、それを再帰的アプローチと比較します。

命令型アプローチ(ループ)

function countDownFrom(number) { for (let i = number; i > 0; i--) { console.log(i); } } countDownFrom(5); // 5 // 4 // 3 // 2 // 1 

これには、両方のアルゴリズムステップが含まれています。

  1. ✅と呼ばれる1つのパラメータを取りますnumber
  2. ✅からnumberまですべてをログに記録します0

再帰的アプローチ

function countDownFrom(number) { if (number === 0) { return; } console.log(number); countDownFrom(number - 1); } countDownFrom(5); // 5 // 4 // 3 // 2 // 1 

これも合格です。

  1. ✅と呼ばれる1つのパラメータを取りますnumber
  2. ✅からnumberまですべてをログに記録します0

したがって、概念的には2つのアプローチは同じです。しかし、彼らはさまざまな方法で仕事を成し遂げます。

命令型ソリューションのデバッグ

より視覚的な例として、debuggerループバージョンにを入れてChromeデベロッパーツールに投入しましょう。

function countDownFrom(number) { for (let i = number; i > 0; i--) { console.log(i); debugger; } } 

countdownFrom-反復

i現在の番号を追跡するために、追加の変数、をどのように使用するかをご覧ください。反復するとi減少し、最終的にはヒット0して終了します。

そして、forループで「stopif」を指定しましたi > 0

再帰的ソリューションのデバッグ

function countDownFrom(number) { if (number === 0) { return; } console.log(number); debugger; countDownFrom(number - 1); } 

countdownFrom-再帰的

再帰バージョンでは、進行状況を追跡するために追加の変数は必要ありません。再帰するにつれて、関数の山(コールスタック)がどのように大きくなるかに注目してください。

これcountDownFromは、を呼び出すたびにスタックに追加され、スタックにフィードされるためnumber - 1です。これを行うことで、number毎回更新されたものを渡すことになります。追加の状態は必要ありません!

これが2つのアプローチの主な違いです。

  1. 反復は内部状態(カウント用の追加変数など)を使用します。
  2. Recursiveはそうではなく、各呼び出し間で更新されたパラメーターを渡すだけです。

しかし、どちらのバージョンもいつ停止するかをどのように知るのでしょうか?

無限ループ

あなたの旅行で、あなたは恐ろしい無限ループについて警告されたかもしれません。

? THIS RUNS FOREVER, BE WARNED ? while (true) { console.log('WHY DID YOU RUN THIS?!' } ? THIS RUNS FOREVER, BE WARNED ? for (i = 0;;) { console.log('WHY DID YOU RUN THIS?!') } 

それらは理論的には永久に実行されるため、無限ループはプログラムを停止し、ブラウザをクラッシュさせる可能性があります。常に停止条件をコーディングすることで、これらを防ぐことができます

✅ This does not run forever x = 0; while (x < 3) { console.log(x); x++; } ✅ This does not run forever for (x = 0; x < 3; x++) { console.log(x); } 

どちらの場合も、ログに記録xしてインクリメントし、になったら停止します3。私たちのcountDownFrom関数にも同様のロジックがありました。

// Stop at 0 for (let i = number; i > 0; i--) 

繰り返しますが、ループはいつ停止するかを決定するために追加の状態が必要です。それは何だxiするためのものです。

無限再帰

再帰も同じ危険をもたらします。ブラウザをクラッシュさせる自己参照関数を書くのは難しくありません。

?THIS RUNS FOREVER, BE WARNED? function run() { console.log('running'); run(); } run(); // running // running // ... 

is-this-a-recursive

Without a stopping condition, run will forever call itself. You can fix that with an if statement.

✅ This does not run forever function run(x) { if (x === 3) return; console.log('running'); run(x + 1); } run(0); // running // running // running // x is 3 now, we're done. 

Base case

This is known as the base case–our recursive countDownFrom had one.

if (number === 0) { return; } 

It's the same idea as our loop's stopping logic. Whichever approach you pick, always remember that at some point it needs to be stopped.

これは止められる必要があります

Summary

  • Recursion is when a function calls itself until someone stops it.
  • It can be used instead of a loop.
  • If no one stops it, it'll recurse forever and crash your program.
  • A base case is a condition that stops the recursion. Don't forget to add them!
  • Loops use extra state variables for tracking and counting, while recursion only uses the provided parameters.

消えるループ

Thanks for reading

このようなその他のコンテンツについては、// yazeedb.comをご覧ください。そして、他に何を見たいか教えてください!私のDMはTwitterで公開されています。

次回まで!