递归入门

作为一名编程新手，递归的概念曾让我百思不得其解。它似乎只在编程领域才会用到，而且它的优势也并不显而易见，因此很难理解。本文旨在有效地向那些不确定递归是什么、如何运作以及为什么它有用的人解释递归。

什么是递归？
根据韦氏词典的定义，递归是：

“一种计算机编程技术，涉及使用一个过程、子程序、函数或算法，该过程、子程序、函数或算法会调用自身一次或多次，直到满足特定条件为止，此时会从最后一次调用开始，依次处理每次重复的剩余部分。”

但这到底是什么意思呢？我们已经知道这是一种计算机编程技巧，但在什么情况下你会希望一个函数调用自身呢？

简而言之，递归是指函数不断调用自身，直到完成所有需要执行的操作。这有点像循环（有些语言实际上在底层就使用了递归来实现循环），但关键区别在于循环（迭代）是通过显式指定重复结构来实现的，而递归则是通过连续的方法调用来实现重复。考虑以下任务：

创建一个方法，该方法接受任意两个数字作为参数，并对它们运行斐波那契数列算法 100 次，并显示每一步的输出。

你可以像这样迭代地进行操作：

const fib = (a, b) => {   // Create the method
  counter = 0              // Instantiate a counter
  while(counter < 100) {     // Loop until the counter reaches 99 
    sum = a + b
    console.log(sum)
    a = b                  // Reassign the variables for the next iteration
    b = sum
    counter++
  }
}

fib(4,5);                   // Call the function

这样就能得到想要的结果，而且运行良好。但是，递归地来说，它看起来会像这样：

fib = (a, b, counter = 0) => { // Create the method
  if (counter > 100) return // Check exit condition
  counter++
  console.log(a + b)
  return fib(b, a + b, counter) // Call itself again if exit condition isnt met
}

fib(4,5)

如您所见，两者结果相同，但递归代码略短且更易读。递归能够有效处理指数级增长的问题。虽然递归在很多情况下都很有用，但也有一些情况下迭代求解更为合适。递归通常占用更多内存，因此对于需要极少内存的问题，它可能并非最佳选择。