面试工具包：递归。

一遍又一遍地调用自己，但每次调用都变得更简单——简而言之，这就是递归！这是一个非正式的定义，但它完美地抓住了本质。

虽然我上一篇关于滑动窗口的文章的自然后续内容是两指针模式，但我们走了一点弯路。为什么？有时，处理有点不同的概念实际上可以使学习变得更容易：

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中文网其他相关文章！