递归函数

什么是递归函数

递归函数是一种在函数体内调用自身的函数。它通过将问题分解为更小的子问题来解决复杂任务，直到达到基本情况为止。递归在解决某些类型的问题时特别有用，比如树形结构遍历、数学序列计算等。

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

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

递归的基本要素

每个递归函数都必须包含两个关键部分：基本情况和递归情况。基本情况是递归停止的条件，防止无限循环；递归情况则是函数调用自身的部分。

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

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

递归与迭代的比较

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

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

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

console.log(fibonacciRecursive(6)); // 8
console.log(fibonacciIterative(6)); // 8

常见的递归应用场景

递归特别适合处理具有自相似结构的问题，如树形结构、分治算法等。

1. 树形结构遍历

const tree = {
  value: 1,
  left: {
    value: 2,
    left: { value: 4 },
    right: { value: 5 }
  },
  right: {
    value: 3,
    left: { value: 6 },
    right: { value: 7 }
  }
};

function traverse(node) {
  if (!node) return;
  console.log(node.value); // 前序遍历
  traverse(node.left);
  traverse(node.right);
}

traverse(tree);
// 输出: 1, 2, 4, 5, 3, 6, 7

2. 数组扁平化

function flattenArray(arr) {
  let result = [];
  arr.forEach(item => {
    if (Array.isArray(item)) {
      result = result.concat(flattenArray(item));
    } else {
      result.push(item);
    }
  });
  return result;
}

console.log(flattenArray([1, [2, [3, 4], 5]])); // [1, 2, 3, 4, 5]

尾递归优化

尾递归是一种特殊的递归形式，递归调用是函数的最后操作。某些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

递归的潜在问题

虽然递归强大，但不正确使用会导致问题：

1. 栈溢出：递归深度过大会耗尽调用栈
2. 性能问题：重复计算可能导致性能低下
3. 内存消耗：每次递归调用都会创建新的栈帧

// 低效的递归实现
function fibonacci(n) {
  if (n <= 1) return n;
  return fibonacci(n - 1) + fibonacci(n - 2);
}

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

console.time('普通递归');
fibonacci(35); // 非常慢
console.timeEnd('普通递归');

console.time('记忆化递归');
fibonacciMemo(35); // 快很多
console.timeEnd('记忆化递归');

递归与高阶函数

递归可以与高阶函数结合，实现更强大的功能。

// 递归实现map函数
function recursiveMap(arr, fn) {
  if (arr.length === 0) return [];
  return [fn(arr[0])].concat(recursiveMap(arr.slice(1), fn));
}

const numbers = [1, 2, 3, 4];
const doubled = recursiveMap(numbers, x => x * 2);
console.log(doubled); // [2, 4, 6, 8]

递归的调试技巧

调试递归函数可能具有挑战性，以下是一些技巧：

1. 使用console.log打印每次递归调用的参数
2. 添加深度参数跟踪递归层级
3. 使用调试器设置断点

function debugRecursion(n, depth = 0) {
  console.log(`深度: ${depth}, n: ${n}`);
  if (n <= 0) {
    console.log('到达基本情况');
    return;
  }
  debugRecursion(n - 1, depth + 1);
}

debugRecursion(3);
// 输出:
// 深度: 0, n: 3
// 深度: 1, n: 2
// 深度: 2, n: 1
// 深度: 3, n: 0
// 到达基本情况

递归在实际项目中的应用

递归在前端开发中有许多实际应用场景：

1. 组件树渲染

function renderComponent(component) {
  // 渲染当前组件
  console.log(`渲染组件: ${component.name}`);
  
  // 递归渲染子组件
  component.children?.forEach(child => {
    renderComponent(child);
  });
}

const app = {
  name: 'App',
  children: [
    {
      name: 'Header',
      children: [
        { name: 'Logo' },
        { name: 'Navigation' }
      ]
    },
    {
      name: 'MainContent',
      children: [
        { name: 'Article' }
      ]
    }
  ]
};

renderComponent(app);

2. JSON数据深度处理

function deepClone(obj) {
  if (obj === null || typeof obj !== 'object') {
    return obj;
  }
  
  const clone = Array.isArray(obj) ? [] : {};
  
  for (const key in obj) {
    if (obj.hasOwnProperty(key)) {
      clone[key] = deepClone(obj[key]);
    }
  }
  
  return clone;
}

const original = { a: 1, b: { c: 2 } };
const cloned = deepClone(original);
console.log(cloned); // { a: 1, b: { c: 2 } }
console.log(cloned.b === original.b); // false

递归的替代方案

在某些情况下，可以使用以下方法替代递归：

1. 迭代：使用循环结构
2. 显式栈：手动管理调用栈
3. 生成器：使用yield实现类似递归的控制流

// 使用显式栈模拟递归
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