インタビューキット: 再帰。

Sep 05, 2024 pm 05:32 PM

Interview Kit: Recursion.

自分自身を何度も呼び出しますが、呼び出すたびに簡単になります。これが簡単に言うと再帰です。これは非公式な定義ですが、本質を完璧に捉えています。

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(10) を呼び出すと一連の再帰呼び出しがトリガーされ、基本ケースの 0 に達するまで 1 を減算することで問題が単純化されます。基本ケースに達すると、関数はそれ自体の呼び出しを停止し、再帰が「バブルアップ」します。これは、以前の各呼び出しが

逆の順序で実行を終了することを意味します。

再帰ツリーの例

これは、再帰呼び出しが count(3) でどのように機能するかを ASCII で表現したものです:


count(3)
   |
   +-- count(2)
        |
        +-- count(1)
             |
             +-- count(0)
                 (base case: stop here)
ログイン後にコピー
count(0) から

返されたはすべて、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

ログイン後にコピー
前に計算された答えがどのようにバブルアップするか、2 * fastialRecursive(1) の答えが 3 * fastialRecursive(2) の引数になるようにバブルアップするなどに注目してください...

<- このアイデアをマスターしてください!

フィボナッチ

フィボナッチ数列の 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 を返します。
最適化の課題: viz で fib(2) が同じ答えを 2 回計算していることに気づいた場合、何かできるでしょうか?キャッシュ?重複による大きな問題を想像してみてください!

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

  1. 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
ログイン後にコピー
  1. 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"
ログイン後にコピー
  1. 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 サイトの他の関連記事を参照してください。

このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。

ホットAIツール

Undresser.AI Undress

Undresser.AI Undress

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

AI Clothes Remover

AI Clothes Remover

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

Undress AI Tool

Undress AI Tool

脱衣画像を無料で

Clothoff.io

Clothoff.io

AI衣類リムーバー

Video Face Swap

Video Face Swap

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

ホットツール

メモ帳++7.3.1

メモ帳++7.3.1

使いやすく無料のコードエディター

SublimeText3 中国語版

SublimeText3 中国語版

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

ゼンドスタジオ 13.0.1

ゼンドスタジオ 13.0.1

強力な PHP 統合開発環境

ドリームウィーバー CS6

ドリームウィーバー CS6

ビジュアル Web 開発ツール

SublimeText3 Mac版

SublimeText3 Mac版

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

Python vs. JavaScript:学習曲線と使いやすさ Python vs. JavaScript:学習曲線と使いやすさ Apr 16, 2025 am 12:12 AM

Pythonは、スムーズな学習曲線と簡潔な構文を備えた初心者により適しています。 JavaScriptは、急な学習曲線と柔軟な構文を備えたフロントエンド開発に適しています。 1。Python構文は直感的で、データサイエンスやバックエンド開発に適しています。 2。JavaScriptは柔軟で、フロントエンドおよびサーバー側のプログラミングで広く使用されています。

C/CからJavaScriptへ:すべてがどのように機能するか C/CからJavaScriptへ:すべてがどのように機能するか Apr 14, 2025 am 12:05 AM

C/CからJavaScriptへのシフトには、動的なタイピング、ゴミ収集、非同期プログラミングへの適応が必要です。 1)C/Cは、手動メモリ管理を必要とする静的に型付けられた言語であり、JavaScriptは動的に型付けされ、ごみ収集が自動的に処理されます。 2)C/Cはマシンコードにコンパイルする必要がありますが、JavaScriptは解釈言語です。 3)JavaScriptは、閉鎖、プロトタイプチェーン、約束などの概念を導入します。これにより、柔軟性と非同期プログラミング機能が向上します。

JavaScriptとWeb:コア機能とユースケース JavaScriptとWeb:コア機能とユースケース Apr 18, 2025 am 12:19 AM

Web開発におけるJavaScriptの主な用途には、クライアントの相互作用、フォーム検証、非同期通信が含まれます。 1)DOM操作による動的なコンテンツの更新とユーザーインタラクション。 2)ユーザーエクスペリエンスを改善するためにデータを提出する前に、クライアントの検証が実行されます。 3)サーバーとのリフレッシュレス通信は、AJAXテクノロジーを通じて達成されます。

JavaScript in Action:実際の例とプロジェクト JavaScript in Action:実際の例とプロジェクト Apr 19, 2025 am 12:13 AM

現実世界でのJavaScriptのアプリケーションには、フロントエンドとバックエンドの開発が含まれます。 1)DOM操作とイベント処理を含むTODOリストアプリケーションを構築して、フロントエンドアプリケーションを表示します。 2)node.jsを介してRestfulapiを構築し、バックエンドアプリケーションをデモンストレーションします。

JavaScriptエンジンの理解:実装の詳細 JavaScriptエンジンの理解:実装の詳細 Apr 17, 2025 am 12:05 AM

JavaScriptエンジンが内部的にどのように機能するかを理解することは、開発者にとってより効率的なコードの作成とパフォーマンスのボトルネックと最適化戦略の理解に役立つためです。 1)エンジンのワークフローには、3つの段階が含まれます。解析、コンパイル、実行。 2)実行プロセス中、エンジンはインラインキャッシュや非表示クラスなどの動的最適化を実行します。 3)ベストプラクティスには、グローバル変数の避け、ループの最適化、constとletsの使用、閉鎖の過度の使用の回避が含まれます。

Python vs. JavaScript:コミュニティ、ライブラリ、リソース Python vs. JavaScript:コミュニティ、ライブラリ、リソース Apr 15, 2025 am 12:16 AM

PythonとJavaScriptには、コミュニティ、ライブラリ、リソースの観点から、独自の利点と短所があります。 1)Pythonコミュニティはフレンドリーで初心者に適していますが、フロントエンドの開発リソースはJavaScriptほど豊富ではありません。 2)Pythonはデータサイエンスおよび機械学習ライブラリで強力ですが、JavaScriptはフロントエンド開発ライブラリとフレームワークで優れています。 3)どちらも豊富な学習リソースを持っていますが、Pythonは公式文書から始めるのに適していますが、JavaScriptはMDNWebDocsにより優れています。選択は、プロジェクトのニーズと個人的な関心に基づいている必要があります。

Python vs. JavaScript:開発環境とツール Python vs. JavaScript:開発環境とツール Apr 26, 2025 am 12:09 AM

開発環境におけるPythonとJavaScriptの両方の選択が重要です。 1)Pythonの開発環境には、Pycharm、Jupyternotebook、Anacondaが含まれます。これらは、データサイエンスと迅速なプロトタイピングに適しています。 2)JavaScriptの開発環境には、フロントエンドおよびバックエンド開発に適したnode.js、vscode、およびwebpackが含まれます。プロジェクトのニーズに応じて適切なツールを選択すると、開発効率とプロジェクトの成功率が向上する可能性があります。

JavaScript通訳者とコンパイラにおけるC/Cの役割 JavaScript通訳者とコンパイラにおけるC/Cの役割 Apr 20, 2025 am 12:01 AM

CとCは、主に通訳者とJITコンパイラを実装するために使用されるJavaScriptエンジンで重要な役割を果たします。 1)cは、JavaScriptソースコードを解析し、抽象的な構文ツリーを生成するために使用されます。 2)Cは、Bytecodeの生成と実行を担当します。 3)Cは、JITコンパイラを実装し、実行時にホットスポットコードを最適化およびコンパイルし、JavaScriptの実行効率を大幅に改善します。

See all articles