一遍又一遍地调用自己，但每次调用都变得更简单——简而言之，这就是递归！这是一个非正式的定义，但它完美地抓住了本质。
虽然我上一篇关于滑动窗口的文章的自然后续内容是两指针模式，但我们走了一点弯路。为什么？有时，处理有点不同的概念实际上可以使学习变得更容易：
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中文网其他相关文章！
