递归函数

递归函数的基本概念

递归函数是指在函数内部调用自身的函数。这种技术允许将复杂问题分解为更小的相同问题，直到达到基本情况。递归在解决某些类型的问题时非常有效，特别是那些具有自相似结构的问题。

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

console.log(factorial(5)); // 输出: 120

递归的核心要素

每个递归函数都需要两个关键部分才能正常工作：递归情况和基本情况。基本情况是递归停止的条件，防止无限循环；递归情况则是函数调用自身的部分。

function countDown(n) {
  if (n <= 0) { // 基本情况
    console.log("Done!");
    return;
  }
  console.log(n);
  countDown(n - 1); // 递归情况
}

countDown(3);
// 输出:
// 3
// 2
// 1
// Done!

递归与迭代的比较

递归和迭代(循环)都可以解决重复性问题，但各有优缺点。递归代码通常更简洁，但可能消耗更多内存；迭代通常效率更高，但代码可能更复杂。

// 迭代实现斐波那契数列
function fibIterative(n) {
  let a = 0, b = 1, temp;
  for (let i = 0; i < n; i++) {
    temp = a;
    a = b;
    b = temp + b;
  }
  return a;
}

// 递归实现斐波那契数列
function fibRecursive(n) {
  if (n <= 1) return n;
  return fibRecursive(n - 1) + fibRecursive(n - 2);
}

console.log(fibIterative(10)); // 55
console.log(fibRecursive(10)); // 55

递归的常见应用场景

递归特别适合处理树形结构、分治算法、回溯问题等。在JavaScript中，DOM遍历、JSON数据处理等场景经常使用递归。

// 深度优先遍历DOM树
function traverseDOM(node, callback) {
  callback(node);
  let child = node.firstChild;
  while (child) {
    traverseDOM(child, callback);
    child = child.nextSibling;
  }
}

// 使用示例
traverseDOM(document.body, node => {
  if (node.nodeType === Node.ELEMENT_NODE) {
    console.log(node.tagName);
  }
});

尾递归优化

尾递归是指递归调用是函数中的最后一步操作。某些JavaScript引擎可以优化尾递归，避免调用栈溢出。

// 普通递归
function sum(n) {
  if (n === 1) return 1;
  return n + sum(n - 1); // 不是尾递归
}

// 尾递归版本
function sumTail(n, acc = 0) {
  if (n === 0) return acc;
  return sumTail(n - 1, acc + n); // 尾递归
}

console.log(sum(100)); // 5050
console.log(sumTail(100)); // 5050

递归的潜在问题

递归可能导致堆栈溢出，特别是当递归深度很大时。此外，不当的递归实现可能产生重复计算，降低性能。

// 低效的斐波那契递归实现
function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2); // 重复计算严重
}

// 使用记忆化优化
function fibMemo(n, memo = {}) {
  if (n in memo) return memo[n];
  if (n <= 1) return n;
  memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
  return memo[n];
}

console.log(fib(35)); // 较慢
console.log(fibMemo(35)); // 快速

递归与异步编程

在异步环境中使用递归需要特别注意，因为每次递归调用都会创建新的执行上下文。

// 异步递归示例
function asyncCountDown(n, delay = 1000) {
  if (n < 0) return;
  setTimeout(() => {
    console.log(n);
    asyncCountDown(n - 1, delay);
  }, delay);
}

asyncCountDown(3);
// 输出(每秒一个数字):
// 3
// 2
// 1
// 0

递归的替代方案

在某些情况下，可以使用堆栈数据结构模拟递归行为，避免递归的潜在问题。

// 使用栈模拟递归
function factorialStack(n) {
  const stack = [];
  let result = 1;
  
  while (n > 1) {
    stack.push(n);
    n--;
  }
  
  while (stack.length > 0) {
    result *= stack.pop();
  }
  
  return result;
}

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

递归在算法中的应用

许多经典算法如快速排序、归并排序、二叉树遍历等都天然适合递归实现。

// 快速排序递归实现
function quickSort(arr) {
  if (arr.length <= 1) return arr;
  
  const pivot = arr[0];
  const left = [];
  const right = [];
  
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
  
  return [...quickSort(left), pivot, ...quickSort(right)];
}

console.log(quickSort([3, 6, 8, 10, 1, 2, 1]));
// 输出: [1, 1, 2, 3, 6, 8, 10]

递归的调试技巧

调试递归函数可能比较困难，可以通过添加日志、使用调试器或可视化工具来理解递归的执行流程。

// 带调试日志的递归函数
function debugFactorial(n, depth = 0) {
  console.log(`${' '.repeat(depth * 2)}调用 factorial(${n})`);
  
  if (n <= 1) {
    console.log(`${' '.repeat(depth * 2)}返回 1`);
    return 1;
  }
  
  const result = n * debugFactorial(n - 1, depth + 1);
  console.log(`${' '.repeat(depth * 2)}返回 ${result}`);
  return result;
}

debugFactorial(3);
// 输出:
// 调用 factorial(3)
//   调用 factorial(2)
//     调用 factorial(1)
//     返回 1
//   返回 2
// 返回 6