面试工具包：递归

知识点掌握了，还需要不断练习才能熟练运用。下面golang学习网给大家带来一个文章开发实战，手把手教大家学习《面试工具包：递归》，在实现功能的过程中也带大家重新温习相关知识点，温故而知新，回头看看说不定又有不一样的感悟！

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

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

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) 的计算结果是相同答案的两倍，我们可以做些什么吗？缓存？想象一下重复的大问题！

求和数组

编写一个递归函数来求数组中所有元素的总和。

  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

这涵盖了基础知识，解决的问题越多在递归方面就越好。

我将在下面留下一些挑战：

实践挑战

1. 检查回文：编写一个递归函数来检查给定的字符串是否是回文（向后读取与向前读取相同）。

console.log(ispalindrome("racecar")); // expected output: true
console.log(ispalindrome("hello"));   // expected output: false

1. 反转字符串：编写一个递归函数来反转给定的字符串。

console.log(reversestring("hello")); // expected output: "olleh"
console.log(reversestring("world")); // expected output: "dlrow"

1. 检查排序数组：编写一个递归函数来检查给定的数字数组是否按升序排序。

console.log(isSorted([1, 2, 3, 4]));    // Expected output: true
console.log(isSorted([1, 3, 2, 4]));    // Expected output: false

递归就是练习和建立肌肉记忆。你解决的问题越多，它就会变得越直观。不断用新问题挑战自己！

如果您想要更多独家内容，可以在 twitter 或 ko-fi 上关注我，我会在那里发布一些额外的内容！

理论要掌握，实操不能落！以上关于《面试工具包：递归》的详细介绍，大家都掌握了吧！如果想要继续提升自己的能力，那么就来关注golang学习网公众号吧！