面试工具包：递归
一遍又一遍地调用自己，但每次调用都变得更简单——简而言之，这就是递归！这是一个非正式的定义，但它完美地抓住了本质。
虽然我上一篇关于滑动窗口的文章的自然后续内容是两指针模式，但我们走了一点弯路。为什么？有时，处理稍微不同的概念实际上可以使学习变得更容易：
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
<p>视觉</p>
<p>斐波那契(4)<br></p>
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) 的计算结果是相同答案的两倍，我们可以做些什么吗？缓存？想象一下重复的大问题！
求和数组
编写一个递归函数来求数组中所有元素的总和。
const sumarray = arr => {
if(arr.length == 0){
return 0
}
return arr.pop() + sumarray(arr)
}
视觉
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
这涵盖了基础知识，解决的问题越多在递归方面就越好。
我将在下面留下一些挑战：
实践挑战
- 检查回文：编写一个递归函数来检查给定的字符串是否是回文（向后读取与向前读取相同）。
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
递归就是练习和建立肌肉记忆。你解决的问题越多，它就会变得越直观。不断用新问题挑战自己！
如果您想要更多独家内容，可以在 twitter 或 ko-fi 上关注我，我会在那里发布一些额外的内容！
以上就是面试工具包：递归的详细内容，更多请关注其它相关文章！