一遍又一遍地调用自己，但每次调用都变得更简单——简而言之，这就是递归！这是一个非正式的定义，但它完美地抓住了本质。
虽然我上一篇关于滑动窗口的文章的自然后续内容是两指针模式，但我们走了一点弯路。为什么？有时，处理稍微不同的概念实际上可以使学习变得更容易：
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 = 2a 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: trueconsole.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: trueconsole.log(isSorted([1, 3, 2, 4])); // Expected output: false
递归就是练习和建立肌肉记忆。你解决的问题越多，它就会变得越直观。不断用新问题挑战自己！
如果您想要更多独家内容，可以在 twitter 或 ko-fi 上关注我，我会在那里发布一些额外的内容！
以上就是面试工具包：递归的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1491185.html
微信扫一扫 
支付宝扫一扫 
