递归与迭代

1. 阶乘计算

计算一个数的阶乘，展示递归和迭代两种实现方式。

// 递归实现
const factorialRecursive = (n) => {
  if (n <= 1) return 1;
  return n * factorialRecursive(n - 1);
};

// 迭代实现
const factorialIterative = (n) => {
  let result = 1;
  for (let i = 2; i <= n; i++) {
    result *= i;
  }
  return result;
};

2. 数组扁平化

将多维数组转换为一维数组。

// 递归实现
const flattenRecursive = (arr) => {
  return arr.reduce((flat, item) => {
    return flat.concat(Array.isArray(item) ? flattenRecursive(item) : item);
  }, []);
};

// 迭代实现
const flattenIterative = (arr) => {
  const stack = [...arr];
  const result = [];
  
  while (stack.length) {
    const next = stack.pop();
    if (Array.isArray(next)) {
      stack.push(...next);
    } else {
      result.unshift(next);
    }
  }
  
  return result;
};

3. 深拷贝

实现对象的深拷贝。

// 递归实现
const deepCloneRecursive = (obj) => {
  if (obj === null || typeof obj !== 'object') return obj;
  
  const clone = Array.isArray(obj) ? [] : {};
  
  for (let key in obj) {
    if (Object.prototype.hasOwnProperty.call(obj, key)) {
      clone[key] = deepCloneRecursive(obj[key]);
    }
  }
  
  return clone;
};

// 迭代实现
const deepCloneIterative = (obj) => {
  const stack = [[obj, {}]];
  const rootClone = stack[0][1];
  
  while (stack.length) {
    const [original, clone] = stack.pop();
    
    for (let key in original) {
      if (Object.prototype.hasOwnProperty.call(original, key)) {
        const value = original[key];
        
        if (value === null || typeof value !== 'object') {
          clone[key] = value;
        } else {
          clone[key] = Array.isArray(value) ? [] : {};
          stack.push([value, clone[key]]);
        }
      }
    }
  }
  
  return rootClone;
};

4. 树的遍历

实现树结构的遍历。

class TreeNode {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

// 递归实现前序遍历
const preorderTraversalRecursive = (root) => {
  const result = [];
  
  const traverse = (node) => {
    if (!node) return;
    result.push(node.val);    // 根
    traverse(node.left);      // 左
    traverse(node.right);     // 右
  };
  
  traverse(root);
  return result;
};

// 迭代实现前序遍历
const preorderTraversalIterative = (root) => {
  if (!root) return [];
  
  const result = [];
  const stack = [root];
  
  while (stack.length) {
    const node = stack.pop();
    result.push(node.val);
    
    // 先压入右节点，再压入左节点，这样出栈时就是先左后右
    if (node.right) stack.push(node.right);
    if (node.left) stack.push(node.left);
  }
  
  return result;
};

5. 汉诺塔问题

经典的汉诺塔问题解法。

// 递归实现
const hanoiRecursive = (n, source, auxiliary, target) => {
  if (n === 1) {
    console.log(`Move disk 1 from ${source} to ${target}`);
    return;
  }
  
  hanoiRecursive(n - 1, source, target, auxiliary);
  console.log(`Move disk ${n} from ${source} to ${target}`);
  hanoiRecursive(n - 1, auxiliary, source, target);
};

// 迭代实现
const hanoiIterative = (n) => {
  const totalMoves = Math.pow(2, n) - 1;
  const isEven = n % 2 === 0;
  
  for (let i = 1; i <= totalMoves; i++) {
    const disk = getBit(i);
    const from = getSource(disk, i, isEven);
    const to = getTarget(disk, i, isEven);
    
    console.log(`Move disk ${disk} from ${from} to ${to}`);
  }
};

// 辅助函数
const getBit = (n) => {
  let count = 1;
  while ((n & 1) === 0) {
    count++;
    n >>= 1;
  }
  return count;
};

const getSource = (disk, move, isEven) => {
  const position = Math.floor(move % 3);
  if (isEven) {
    return ['A', 'C', 'B'][position];
  }
  return ['A', 'B', 'C'][position];
};

const getTarget = (disk, move, isEven) => {
  const position = Math.floor((move + 1) % 3);
  if (isEven) {
    return ['B', 'A', 'C'][position];
  }
  return ['C', 'A', 'B'][position];
};

每个示例都包含了递归和迭代两种实现方式，并附带详细注释。递归通常代码更简洁，逻辑更清晰，但在处理大规模数据时可能会导致栈溢出。迭代虽然代码较长，但性能通常更好，且不会有栈溢出的问题。在实际开发中，应根据具体场景选择合适的实现方式。