JS 中的递归简介

如果你刚开始学习编程，你可能听说过这个主题：递归。就我个人而言，递归是那些花了我很长时间才理解的编程概念之一。诚然，我还有很长的路要走，但在我看来，有几个主要原因导致了这个主题如此短暂。

1) 不使用递归也能解决任何问题，所以它经常被初学者忽略。2
) 它的优势并不明显。3
) 它可能让人一头雾水。

我的一个好朋友曾经写道：“就像字典用一个词来描述自己一样，理解递归可能会令人沮丧。递归是违反直觉的。程序员第一次接触递归时，通常会想起电影《盗梦空间》。

我可能为此感到羞愧，或许这也是我应得的，但我还没看过《盗梦空间》。这只是我没时间看的那些东西之一……也许这就是为什么我花了这么长时间才搞清楚整个递归的事情><。

我认为递归的主要优势在于，对于一些较长的问题，它能使算法更易读、更优雅。然而，在大多数情况下，递归可能会比较慢，并且会占用更多的调用堆栈。

这是一篇很棒的文章，解释了递归和迭代解决方案之间的一些区别！

请耐心听我向您介绍一些关键术语和一些基本问题，以帮助您掌握令人生畏的递归主题。

也许我应该早点定义它，但是递归是一个调用自身直到满足指定条件的函数。

如果我们想编写一个从数字倒数的函数，我们可以这样做。

function sayDownFrom(n){
    console.log(n)
    if(n > 1){
        sayDownFrom(n -1) // recursive call
    } else {
        return true // base case
    }
}

在函数主体中，我们看到函数实际上调用了自身。这被称为递归调用。我们还可以看到函数有一个停止点，可以将其称为起始条件。如果没有起始条件，我们将陷入无限循环。

那么，这个函数到底起什么作用？

逐行…

function sayDownFrom(n){
    // we print the number first
    console.log(n)
    // then we check if n is greater than 1, which is essentially setting a counter to stop if it is less
    if(n > 1){
        // if n is greater than 1, we call our function which will print out the number before n (in essence, counting down)
        sayDownFrom(n -1) // recursive call
    } else {
        // if n is not greater than one it will go to our base case here and return true and complete the execution
        return true // base case
    }
}

现在，让我们逐行解决更多问题以获得更多经验，看看我们是否可以在递归解决方案中找出任何重复出现的主题。

让我们递归地写出经典的 isPalindrome 解决方案。这里我们想判断传入函数的字符串是否是回文……比如“racecar”或“hannah”。

function isPalindrome(str) {
    // setting a variable to the length of our string
    var strLen = str.length;

    //checking if the length is zero or if the length is 1
    if (strLen === 0 || strLen === 1) {
      //if we reach either of these cases we will want to return true because of our next 'if' statement
        return true;
    }

    if (str[0] === str[strLen - 1]) {
      // here we are checking if the first index in the string and the last index in the string are the same

      // if they are the same then we are going to make our recursive call, but this time pass in the string without the letters that we just checked for
      // hence the use of slice
        return isPalindrome( str.slice(1, strLen - 1) );
    }

    // if this last 'if' statement were to fail and neither of the first or last letters were equal to each other at any time in our functions life
    // then we would return false immediately since it would not pass the 'if' statement above
    return false;
}

我们已经研究了两种解决方案，一种是整数，一种是字符串。让我们再来一个数组方案！

让我们编写一个函数来查看数组是否包含给定元素。

function includesNumber(arr, element) {
  //if there are no more elements in the array, then we have checked them all and it is not there
  if (!arr.length) {
    // so we will return false
    return false

    // we are now checking if the first element is equal to the passed in element
  } else if (arr[0] === element) {
    // if it is we return true
    return true

    // if none of those things are true yet, we check the array without the first element that we had just checked
  } else {
    return includesNumber(arr.slice(1), element)
  }

结论

我们可以从这几个简单的问题中发现一些规律，尤其是我们的 includesNumber 和 isPalindrome 函数。在这两个函数中，我们检查等价项并使用 .slice 方法。就像编程中的其他任何事情一样，练习得越多，就越能发现规律。如果你在练习算法，我始终建议你先找到解决方案（无论它多么冗长和丑陋），然后再从那里进行重构（包括以递归的方式思考或尝试解决问题）。

希望通过这几个问题的解答，你对需要注意的事项以及如何开始思考递归解决方案有了大致的了解。干杯！

文章来源：https://dev.to/ryanfarney3/intro-to-recursion-in-js-32g