学习笔记（17）递归

定义

递归：是一种自己调用自己的算法，将大型的复杂问题，层层转化为一个与原问题相似但规模较小的问题来求解。而在JavaScript中，函数直接或间接的调用自己，则该函数便称为递归函数。

递归使用

//计算阶乘
function factorial(n) {
  // 基本情况
  if (n === 0 || n === 1) {
    return 1;
  } 
  // 递归调用
  else {
    return n * factorial(n - 1);
  }
}

console.log(factorial(5));  //120

递归函数一般包括两个关键部分：

1. 基本情况（Base Case）: 这是递归终止的条件，也被称为递归出口。在递归过程中，函数检查是否达到基本情况，如果满足基本情况，则直接返回结果，不再进行进一步的递归调用。

例如，在计算阶乘时，基本情况可能是 n === 0 或 n === 1，此时我们知道阶乘的结果是 1。

2. 递归调用（Recursive Call）: 当函数未达到基本情况时，它会基于较小或简化的问题再次调用自身。每一次递归调用都会向函数传递更接近基本情况的参数，直到最终达到基本情况并开始逐层返回结果。

递归分类

头递归

如果递归有在函数调用后要执行的代码语句，则它是头递归。头递归通常很难转换为循环语句。

function head(n) {
    if (n == 0) {
        return 0
    }
    head(n - 1)
    console.log(n);
}

head(5)  //1 2 3 4 5

尾递归

尾递归在函数调用之后不会有任何代码语句，通常在函数声明的末尾。尾递归很容易转换成循环语句。

function tail(n) {
    if (n == 0) {
        return 0
    }
    console.log(n);
    tail(n - 1)
}

tail(5)  //5 4 3 2 1

注意事项

递归函数需要注意几个要点：

1. 递归函数必须有一个或多个基本情况（base case），这些情况是递归的终止条件。如果没有基本情况，函数将进入死循环，无限递归下去，导致堆栈溢出错误。

//无递归出口
function fn(){			
	console.log(‘你好’);		
	fn();				
}
fn();					

2. 递归函数在调用自身时，每次调用的信息会被存储在调用栈（Call Stack）中，直到遇到基本情况退出递归，然后逐级返回结果。因此，对于大数据量的递归，要小心栈空间的限制。
3. 在某些情况下，可以使用尾递归优化，现代JavaScript引擎（如V8）支持尾递归优化，能够减少栈空间的占用。尾递归是指在函数返回的时候，调用自身本身，并且return语句不能包含表达式（即函数必须是最后一句）。但并非所有递归都适用于尾递归优化。