インタビューキット: 再帰。
自分自身を何度も呼び出しますが、呼び出すたびに簡単になります。これが簡単に言うと再帰です。これは非公式な定義ですが、本質を完璧に捉えています。
Sliding Window に関する前回の記事の自然なフォローアップは Two-Pointer パターンですが、少し回り道をします。なぜ?場合によっては、少し異なる概念に取り組むと、実際に学習が容易になることがあります。
1) 脳に作業の多様性を与えます。
2) 正直に言うと、ぼやけてしまう前に実行できる配列操作は限られています!
さらに、再帰はバイナリ ツリーに入る前に知っておく必要があるため、この記事ではそれに焦点を当てます。心配しないでください。Two-Pointer パターンとツリーは近日中に導入される予定です。私たちは、物事を新鮮に保つために戦略的に停止しているだけです!
再帰 101
再帰は、定義を暗記するよりも直感を構築することが重要である概念の 1 つです。重要なアイデアは? 繰り返し、問題を徐々に単純化していきます。
では、再帰とは何でしょうか?
再帰とは、問題に対してプロセスを何度も繰り返すことですが、繰り返すたびに、問題は単純化できなくなる点に達するまで単純になっていきます。これを 基本ケース.
いくつかの基本的なルールを見てみましょう。ルール 1: 問題は小さくなければならない
反復ごとに、問題のサイズや複雑さが軽減されるはずです。正方形から始めて、ステップごとにそれを縮小していくことを想像してください。
注: 小さな正方形の代わりにランダムな形状が得られた場合、それは再帰的なプロセスではなくなり、より単純な問題は、大きな正方形の問題の小さなバージョンになります。
ルール 2: 基本ケースが存在する必要がある
基本ケースは、問題の最も単純で簡単なバージョン、つまりそれ以上の再帰が必要ない点です。これがないと、関数は永久に自分自身を呼び出し続けることになり、スタック オーバーフローが発生します。
例: カウントダウンx から 0 までカウントダウンするという単純な問題があるとします。これは現実の問題ではありませんが、再帰の良い例です。
function count(x) { // Base case if (x == 0) { return 0; } // Recursive call: we simplify the problem by reducing x by 1 count(x - 1); // will only run during the bubbling up // the first function call to run is the one before base case backwards // The printing will start from 1.... console.log(x) }
逆の順序で実行を終了することを意味します。
再帰ツリーの例これは、再帰呼び出しが count(3) でどのように機能するかを ASCII で表現したものです:
count(3) | +-- count(2) | +-- count(1) | +-- count(0) (base case: stop here)
返されたはすべて、count(1) まで...カウント 3 まで「バブル」します。
つまり、最も単純な基本ケースから合成されます!さらなる問題!
再帰的な例
直感の部分を覚えていますか?より多くの再帰問題を解決するほど、より良い問題が解決されます。これは、古典的な再帰問題の簡単な概要です。
階乗
数値 n の階乗は、n 以下のすべての正の整数の積です。
const factorialRecursive = num => { if(num === 0) { return 1; } return num * factorialRecursive(num - 1); }
factorialRecursive(5)
factorialRecursive(5) │ ├── 5 * factorialRecursive(4) │ │ │ ├── 4 * factorialRecursive(3) │ │ │ │ │ ├── 3 * factorialRecursive(2) │ │ │ │ │ │ │ ├── 2 * factorialRecursive(1) │ │ │ │ │ │ │ │ │ ├── 1 * factorialRecursive(0) │ │ │ │ │ │ │ │ │ │ │ └── returns 1 │ │ │ │ └── returns 1 * 1 = 1 │ │ │ └── returns 2 * 1 = 2 │ │ └── returns 3 * 2 = 6 │ └── returns 4 * 6 = 24 └── returns 5 * 24 = 120
<- このアイデアをマスターしてください!
フィボナッチフィボナッチ数列の n 番目の数値を返す再帰関数。各数値は 0 と 1 から始まる前の 2 つの数値の合計です。
const fibonacci = num => { if (num <= 1) { return num; } return fibonacci(num - 1) + fibonacci(num - 2); }
フィボナッチ(4)
fibonacci(4) │ ├── fibonacci(3) │ ├── fibonacci(2) │ │ ├── fibonacci(1) (returns 1) │ │ └── fibonacci(0) (returns 0) │ └── returns 1 + 0 = 1 │ ├── fibonacci(2) │ ├── fibonacci(1) (returns 1) │ └── fibonacci(0) (returns 0) └── returns 1 + 1 = 2 a bit tricky to visualize in ascii (way better in a tree like structure)
- fibonacci(4) は fibonacci(3) と fibonacci(2) を呼び出します。
- fibonacci(3) は次のように分解されます。
- fibonacci(2) → これは fibonacci(1) (1 を返す) と fibonacci(0) (0 を返す) に分割されます。それらの合計は 1 + 0 = 1 です。
- fibonacci(1) → これは 1 を返します。 したがって、
- fibonacci(3) は 1 (fibonacci(2) から) + 1 (fibonacci(1) から) = 2 を返します。
- fibonacci(2) は再び分解されます。
- fibonacci(1) は 1 を返します。
- fibonacci(0) は 0 を返します。 それらの合計は 1 + 0 = 1 です。
最後に、 - fibonacci(4) は 2 (fibonacci(3) から) + 1 (fibonacci(2) から) = 3 を返します。
Sum Array
Write a recursive function to find the sum of all elements in an array.
const sumArray = arr => { if(arr.length == 0){ return 0 } return arr.pop() + sumArray(arr) } </p> <p>visual</p> <p>sumArray([1, 2, 3, 4])<br> </p> <pre class="brush:php;toolbar:false">sumArray([1, 2, 3, 4]) │ ├── 4 + sumArray([1, 2, 3]) │ │ │ ├── 3 + sumArray([1, 2]) │ │ │ │ │ ├── 2 + sumArray([1]) │ │ │ │ │ │ │ ├── 1 + sumArray([]) │ │ │ │ │ │ │ │ │ └── returns 0 │ │ │ └── returns 1 + 0 = 1 │ │ └── returns 2 + 1 = 3 │ └── returns 3 + 3 = 6 └── returns 4 + 6 = 10
This covers the basics, the more problems you solve the better when it comes to recursion.
I am going to leave a few challenges below:
Challenges for Practice
- Check Palindrome: Write a recursive function to check if a given string is a palindrome (reads the same backward as forward).
console.log(isPalindrome("racecar")); // Expected output: true console.log(isPalindrome("hello")); // Expected output: false
- Reverse String: Write a recursive function to reverse a given string.
console.log(reverseString("hello")); // Expected output: "olleh" console.log(reverseString("world")); // Expected output: "dlrow"
- Check Sorted Array: Write a recursive function to check if a given array of numbers is sorted in ascending order.
console.log(isSorted([1, 2, 3, 4])); // Expected output: true console.log(isSorted([1, 3, 2, 4])); // Expected output: false
Recursion is all about practice and building that muscle memory. The more you solve, the more intuitive it becomes. Keep challenging yourself with new problems!
If you want more exclusive content, you can follow me on Twitter or Ko-fi I'll be posting some extra stuff there!
以上がインタビューキット: 再帰。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

ホットAIツール

Undresser.AI Undress
リアルなヌード写真を作成する AI 搭載アプリ

AI Clothes Remover
写真から衣服を削除するオンライン AI ツール。

Undress AI Tool
脱衣画像を無料で

Clothoff.io
AI衣類リムーバー

Video Face Swap
完全無料の AI 顔交換ツールを使用して、あらゆるビデオの顔を簡単に交換できます。

人気の記事

ホットツール

メモ帳++7.3.1
使いやすく無料のコードエディター

SublimeText3 中国語版
中国語版、とても使いやすい

ゼンドスタジオ 13.0.1
強力な PHP 統合開発環境

ドリームウィーバー CS6
ビジュアル Web 開発ツール

SublimeText3 Mac版
神レベルのコード編集ソフト(SublimeText3)

ホットトピック











フロントエンドのサーマルペーパーチケット印刷のためのよくある質問とソリューションフロントエンド開発におけるチケット印刷は、一般的な要件です。しかし、多くの開発者が実装しています...

JavaScriptは現代のWeb開発の基礎であり、その主な機能には、イベント駆動型のプログラミング、動的コンテンツ生成、非同期プログラミングが含まれます。 1)イベント駆動型プログラミングにより、Webページはユーザー操作に応じて動的に変更できます。 2)動的コンテンツ生成により、条件に応じてページコンテンツを調整できます。 3)非同期プログラミングにより、ユーザーインターフェイスがブロックされないようにします。 JavaScriptは、Webインタラクション、シングルページアプリケーション、サーバー側の開発で広く使用されており、ユーザーエクスペリエンスとクロスプラットフォーム開発の柔軟性を大幅に改善しています。

スキルや業界のニーズに応じて、PythonおよびJavaScript開発者には絶対的な給与はありません。 1. Pythonは、データサイエンスと機械学習でさらに支払われる場合があります。 2。JavaScriptは、フロントエンドとフルスタックの開発に大きな需要があり、その給与もかなりです。 3。影響要因には、経験、地理的位置、会社の規模、特定のスキルが含まれます。

この記事の視差スクロールと要素のアニメーション効果の実現に関する議論では、Shiseidoの公式ウェブサイト(https://www.shisido.co.co.jp/sb/wonderland/)と同様の達成方法について説明します。

JavaScriptを学ぶことは難しくありませんが、挑戦的です。 1)変数、データ型、関数などの基本概念を理解します。2)非同期プログラミングをマスターし、イベントループを通じて実装します。 3)DOM操作を使用し、非同期リクエストを処理することを約束します。 4)一般的な間違いを避け、デバッグテクニックを使用します。 5)パフォーマンスを最適化し、ベストプラクティスに従ってください。

JavaScriptの最新トレンドには、TypeScriptの台頭、最新のフレームワークとライブラリの人気、WebAssemblyの適用が含まれます。将来の見通しは、より強力なタイプシステム、サーバー側のJavaScriptの開発、人工知能と機械学習の拡大、およびIoTおよびEDGEコンピューティングの可能性をカバーしています。

同じIDを持つ配列要素をJavaScriptの1つのオブジェクトにマージする方法は?データを処理するとき、私たちはしばしば同じIDを持つ必要性に遭遇します...

Zustand非同期操作のデータの更新問題。 Zustand State Management Libraryを使用する場合、非同期操作を不当にするデータ更新の問題に遭遇することがよくあります。 �...
