一遍又一遍地呼叫自己，但每次呼叫都變得更簡單－簡而言之，這就是遞歸！這是一個非正式的定義，但它完美地抓住了本質。
雖然我上一篇關於滑動視窗的文章的自然後續內容是兩指針模式，但我們走了一點彎路。為什麼？有時，處理稍微不同的概念實際上可以使學習變得更容易：
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) 將觸發一系列遞歸調用，每個遞歸調用都會透過減去 1 來簡化問題，直到達到基本情況 0。一旦達到基本情況，函數就會停止呼叫自身並遞歸“冒泡”，意味著先前的每個呼叫都以相反的順序完成執行。
這是遞歸呼叫如何與 count(3) 配合使用的 ASCII 表示：
count(3)
|
+-- count(2)
|
+-- count(1)
|
+-- count(0)
(base case: stop here)
從 count(0) 回傳的任何內容都會「冒泡」到 count(1) ... 直到 count 3。
所以它是由最簡單的基本情況組合而成的！ .更多問題！
遞迴範例
階乘
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
斐波那契
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)
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:
console.log(isPalindrome("racecar")); // Expected output: true
console.log(isPalindrome("hello")); // Expected output: false
console.log(reverseString("hello")); // Expected output: "olleh"
console.log(reverseString("world")); // Expected output: "dlrow"
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中文網其他相關文章！
