面試工具包：遞迴。

一遍又一遍地呼叫自己，但每次呼叫都變得更簡單－簡而言之，這就是遞歸！這是一個非正式的定義，但它完美地抓住了本質。

雖然我上一篇關於滑動視窗的文章的自然後續內容是兩指針模式，但我們走了一點彎路。為什麼？有時，處理稍微不同的概念實際上可以使學習變得更容易：

1) 它為大腦提供了一些工作的多樣性。
2) 讓我們面對現實吧，在事情開始變得模糊之前，我們只能進行這麼多的陣列操作！

另外，在深入研究二元樹之前，遞歸是必須了解的，所以本文將重點討論它。別擔心——雙指針模式和樹的介紹即將推出。我們只是策略性地停留以保持新鮮感！

遞迴101

遞迴是建立直覺比記住定義更重要的概念之一。關鍵想法是什麼？ 重複並使問題逐漸變得更簡單。

那麼，什麼是遞迴呢？

遞歸就是在一個問題上一遍又一遍地重複一個過程，但每次重複，問題都會變得更簡單，直到達到無法再簡化的​​程度- 這稱為基本情況.

讓我們用一些基本規則來分解它。

規則一：問題必須變得更小

在每次迭代中，問題的規模或複雜性都應該減少。想像一下從一個正方形開始，每一步都會縮小它。

注意：如果您得到的不是較小的正方形，而是隨機形狀，則它不再是遞歸過程，更簡單的問題是較大的較小版本。

規則 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) 將觸發一系列遞歸調用，每個遞歸調用都會透過減去 1 來簡化問題，直到達到基本情況 0。一旦達到基本情況，函數就會停止呼叫自身並遞歸“冒泡”，意味著先前的每個呼叫都以相反的順序完成執行。

遞歸樹範例

這是遞歸呼叫如何與 count(3) 配合使用的 ASCII 表示：

count(3)
   |
   +-- count(2)
        |
        +-- count(1)
             |
             +-- count(0)
                 (base case: stop here)

從 count(0) 回傳的任何內容都會「冒泡」到 count(1) ... 直到 count 3。

所以它是由最簡單的基本情況組合而成的！ .

更多問題！

遞迴範例

還記得直覺部分嗎？解決的遞歸問題越多越好，這是經典遞歸問題的快速概述。

階乘

數字 n 的階乘是所有小於或等於 n 的正整數的乘積。

const factorialRecursive = num => {
    if(num === 0) {
        return 1;
    }
    return num * factorialRecursive(num - 1);
}

視覺

階乘遞歸(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 * FactorialRecursive(1) 的答案冒泡成為 3 * FactorialRecursive(2) 的參數，依此類推...

斐波那契

一個遞歸函數，傳回斐波那契數列中的第 n 個數字，其中每個數字都是前兩個數字的總和，從 0 和 1 開始。

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)

這就是它的運作方式：

• 斐波那契(4)呼叫斐波那契(3)和斐波那契(2)。
• 斐波那契(3) 分解為：
  • fibonacci(2) → 這分為 fibonacci(1)（回傳 1）和 fibonacci(0)（回傳 0）。它們的和是 1 + 0 = 1。
  • 斐波那契(1) → 回傳 1.
  因此，
  • fibonacci(3) 回傳 1（來自 fibonacci(2)）+ 1（來自 fibonacci(1)）= 2。
• 斐波那契(2)再分解：
  • 斐波那契(1) 回傳 1.
  • 斐波那契(0) 回傳 0.
  它們的和是 1 + 0 = 1。
最後，
• fibonacci(4) 回傳 2（來自 fibonacci(3)）+ 1（來自 fibonacci(2)）= 3。

最佳化挑戰：如果您在視覺化中註意到 fib(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)
}

visual

sumArray([1, 2, 3, 4])

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中文網其他相關文章！