为什么你应该学习递归

在Twitter上关注我，很高兴接受您对主题或改进的建议/Chris

好的，这是一张羊的大图。现在他真的迷路了？其实，它和递归类似，有很多类似的函数调用，几乎相同但又不同;) 如果你继续阅读，你会看到递归的解释，甚至一些问题得到了解决。

我正在写一个关于计算机科学基础的系列文章。你问，为什么不用最新的 JS 框架或者类似的框架呢？

嗯，原因不止一个，了解基础知识是一项永恒的技能，无论你学习什么框架、语言或库，基础知识永远都在那里。

好的，这听起来像是教科书式的答案，我们应该买那个吗？

当然，还有更多。我从事 IT 行业十多年，用过大量的库和语言之后，你会发现，一段时间后，你会努力拓展思维，解决以前从未见过的问题，甚至用新的方式解决同样的问题。

是否可以说你只是在解决问题，有时是以一种不熟练的方式？

是的，我想我们都可以证明这一点，有时我们的解决方案很好，有时则不太好。

说实话，我并不是大学里最专心的学生，但我对大 O 符号、算法、递归、编译器等内容研究得越多，当我最终理解并欣赏它的优雅时，感觉就越好。

因此，我将从介绍递归开始本系列，它是“巨鲸”之一，也是需要攻克的重要概念之一。我希望展示以下内容：

什么是递归
为什么使用递归，它可以用于解决什么问题，以及为什么它是一种非常优雅的方法
问题解决我们将展示一系列递归真正发挥作用的问题以及如何解决这些问题

什么是递归

关于递归的一个流行笑话是：

如果你想知道递归是什么，请参阅递归

简而言之，递归是一种多次调用自身的方法。

这听起来像是一个while-true循环，就像我们将要耗尽内存一样

是的，这是递归的陷阱之一，如果你做错了，你会看到如下错误消息：

为什么

我究竟为什么要给自己打 x 次电话？

嗯，这取决于你问题的性质。有些问题可以看作是一种重复出现的模式，你可以反复应用相同的解决方案。

好的，你必须更好地解释这一点。

当然，我们将通过解决一系列问题来表明我们的意思。

好吧，公平地说，但你还没有解释原因吗？

简而言之，优雅。正确编写的递归解决方案通常只需几行代码。这意味着我们理解甚至修改代码的认知负担大大降低。

好的，我明白了，每个人都喜欢简单，还有什么？

递归通常用来替代“for-loops与”while语句。它的本质就是循环，或者更确切地说，就是重复应用它的逻辑。我认为可以说它是一种分而治之的方法。不要与真正的“分而治之”混淆。我在这里想说的是，我们通过意识到我们正在查看一个充满相似模式的数据集（即自相似性）来慢慢地攻克我们的问题。这种自相似性使得我们可以反复应用相同的算法。

你真的必须解释一下

嗯，你首先要处理一组逐渐减少的数据，这意味着我们要朝着一个点努力。一旦我们达到这个点，问题就解决了。

我们可以解决什么类型的问题？

好吧，这里有一个非详尽的列表，以便您了解它：

求和，我们可以轻松地将列表中的所有项目相加
幂，计算某个数的幂等同于将一个数乘以自身 x 次
阶乘，阶乘是将所有数字按降序相乘
树，树在计算机科学中用于很多事情，比如编译器、计算器之类的后前缀处理等等。
转换，例如将字符串转换为数字
排序，递归通常用于实现排序算法，例如合并排序。

这只是我们可以解决的一小部分问题，是的，您可以使用for 循环和while结构解决上述大部分问题，但这通常会导致代码更加混乱。

解决一些问题

您现在一定迫不及待地想看一些代码，所以让我们首先展示一下典型的递归：

function recursion(data) {
  if(condition) {
    return 'something'
  } else {
   recursion(data)
  }
}

如上所示，我们以 IF 子句开始，这也称为起始条件或终止条件。为了避免最终陷入while-true条件，您需要确保满足此条件。

我们的 ELSE 语句是我们再次调用自身的地方，正如你所见，我们recursion()再次调用了该方法。这里的想法是稍微修改一下，以便最终达到我们的基准情况。

接下来我们来看一些实际问题。

阶乘

阶乘的计算思路是把所有数相乘，直到包含它本身。对于一个数来说，5这意味着我们需要像这样计算：

5 * 4 * 3 * 2 * 1

正如我们上面看到的，我们正在处理一系列缓慢下降至基本条件的数字1。让我们看一些代码：

function factorial(num) {
  if(num === 1) {
    return 1;
  } else {
    return num * factorial(num -1); 
  }
}

我必须承认，当我第一次看到这样的解决方案时，我的脑袋就爆炸了，我无法接受它，我想这甚至是有效的代码，或者使用像这样的 for 循环会更简单：

function factorial(num) {
  var sum = 1;
  for(var i = num; i > 0; i--) {
    sum *= i; 
  }
  return sum;
}

我理解过去的自己，也理解一些读者的感受。初次接触递归时，你会感到很痛苦，除非你的大脑有某种特定的思维方式 ;)。

那么为什么递归解决方案更好呢？至少对我来说，是因为简单。如果我们看某一行：

return num * factorial(num -1);

这里我们只需要考虑返回num，其余部分留给它自己计算，当我们factorial()再次调用时，这次会使用调整后的值num。对我来说，难以理解的是，这是一段有效的代码。我看得出来这会导致某种5 * 4 * 3 * 2 * 1情况。我只是不明白编译器是否能接受。但事实确实如此，这就引出了下一个问题。

转换，字符串到数字

现在，这很有趣。当我们将某个数从转换"234"为时，究竟发生了什么234？嗯，这是一个加法。它是200 + 30 + 4。它是什么样子的？

下降系列？

是的，确实如此，但让我们更详细地讲，它看起来如下所示：

2 * 10^2 + 3 * 10 ^ 1 + 4 * 10 ^ 0

根据我们从阶乘中学到的知识，我们可以开始对其进行勾勒：

currentcharacter * Math.pow(10, pow) + convert(character)

好了，我们大致了解了“如何”实现。下一个问题是，我们的基本条件是什么样的？答案是，我们只处理一个字符，如下所示：

if (chars.length === 1) {
  return parseInt(chars[0]);
}

上面的代码告诉我们，我们将从左到右处理数字，一旦处理到最左边的字符，就认为它已经处理完毕，我们应该继续处理更小的数据集。缩小数据集对于达到基本条件至关重要。让我们看看剩下的代码：

function convert(num) {
  let chars = (num + '');

  if(chars.length === 1) {
    return parseInt(chars[0])
  } else {
    let pow = chars.length -1;
    return Math.pow(10, pow) * parseInt(chars[0]) + convert(num.substr(1));
  }
}

放大我们的 else 条件：

else {
  let pow = chars.length -1;
  return Math.pow(10, pow) * parseInt(chars[0]) + convert(num.substr(1));
}

我们可以看到，我们应用了的降序模式2* 10^2 + 3* 10^1 + 4，或"234"变成了234。它之所以降序，是因为我们这样做：

convert(num.substr(1))

我们从左边挑选一个字符，因此234，变成34，最后4，从而我们达到了基本条件。

概括

我可以向你展示树和大量其他实现，但我们就此打住。看看这个repo，我用递归解决了更多问题。我想表达的重点是递归是什么，为什么它对于某些问题来说是一个更简单、更优雅的解决方案，当然，我也想解释递归的构成要素以及解决这些问题时的思维方式。

希望这篇文章对你有帮助。如果你想让我写一篇关于这个主题的后续文章，请在评论区留言。

读完这篇文章，你可能不会相信递归适合你。我很长时间以来都不确定。说实话，我喜欢递归带来的模式。如果你的工作内容之一是编写算法，或者你渴望成为下一个 Code Wars 大师，或者想在一家知名科技公司求职，那么你需要了解这一点。如果不是，那就继续吧，for 循环也是这门语言的一部分 :)

或者就像我住的地方说的那样：

保持冷静并进行：）

文章来源：https://dev.to/itnext/why-you-should-learn-recursion-3dao