递归与尾调用优化

// 直接递归
function countdown(n) {
  if (n <= 0) {
    console.log('Done!')
    return
  }
  console.log(n)
  countdown(n - 1)
}

countdown(5)
// 输出: 5 4 3 2 1 Done!

// 间接递归
function foo(n) {
  if (n <= 0) return
  console.log('foo:', n)
  bar(n - 1)
}

function bar(n) {
  if (n <= 0) return
  console.log('bar:', n)
  foo(n - 1)
}

foo(3)
// 输出: foo: 3, bar: 2, foo: 1

function factorial(n) {
  // 1. 基线条件(Base Case):终止递归的条件
  if (n <= 1) return 1
  
  // 2. 递归条件(Recursive Case):缩小问题规模
  const subProblem = n - 1
  
  // 3. 递归调用(Recursive Call):调用自身解决子问题
  return n * factorial(subProblem)
}

console.log(factorial(5))  // 120
// 执行过程:5 * 4 * 3 * 2 * 1 = 120

function factorial(n) {
  if (n <= 1) return 1
  return n * factorial(n - 1)
}

factorial(5)

┌─────────────────────────────────────┐
│ 调用栈变化示意图                      │
├─────────────────────────────────────┤
│ 1. factorial(5) 入栈                 │
│    栈:[factorial(5)]                │
│                                     │
│ 2. factorial(4) 入栈                 │
│    栈:[factorial(5), factorial(4)] │
│                                     │
│ 3. factorial(3) 入栈                 │
│    栈:[factorial(5), factorial(4), │
│         factorial(3)]               │
│                                     │
│ 4. factorial(2) 入栈                 │
│    栈:[..., factorial(3),          │
│         factorial(2)]               │
│                                     │
│ 5. factorial(1) 入栈, 满足终止条件  │
│    栈:[..., factorial(2),          │
│         factorial(1)]               │
│                                     │
│ 6. factorial(1) 出栈, 返回 1        │
│    factorial(2) 继续执行:2 * 1 = 2 │
│                                     │
│ 7. factorial(2) 出栈,返回 2         │
│    factorial(3) 继续执行:3 * 2 = 6 │
│                                     │
│ 8. 以此类推...                       │
│    最终结果:120                     │
└─────────────────────────────────────┘

// 栈帧结构示意
{
  函数参数:n = 5,
  局部变量:{},
  返回地址:调用者的代码位置,
  临时变量:中间计算结果
}

function testStackSize(n) {
  try {
    return testStackSize(n + 1)
  } catch (e) {
    return n
  }
}

console.log('最大栈深度:', testStackSize(0))

// 基础版本(性能较差)
function fibonacci(n) {
  if (n <= 1) return n
  return fibonacci(n - 1) + fibonacci(n - 2)
}

console.log(fibonacci(10))  // 55
// 数列:0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55

fibonacci(5) 的调用树:
                fib(5)
               /      \
           fib(4)     fib(3)
          /    \      /    \
      fib(3)  fib(2) fib(2) fib(1)
       /  \    /  \
   fib(2) fib(1) fib(1) fib(0)
    /  \
 fib(1) fib(0)

function fibonacciMemo(n, memo = new Map()) {
  if (memo.has(n)) return memo.get(n)
  if (n <= 1) return n
  
  const result = fibonacciMemo(n - 1, memo) + fibonacciMemo(n - 2, memo)
  memo.set(n, result)
  
  return result
}

console.log(fibonacciMemo(50))  // 12586269025
// 时间复杂度降为 O(n),空间复杂度 O(n)

function fibonacciIterative(n) {
  if (n <= 1) return n
  
  let prev = 0
  let curr = 1
  
  for (let i = 2; i <= n; i++) {
    const next = prev + curr
    prev = curr
    curr = next
  }
  
  return curr
}
// 时间复杂度 O(n),空间复杂度 O(1)

function factorial(n) {
  if (n <= 1) return 1
  return n * factorial(n - 1)
}

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

// 基础版本
function sum(array) {
  if (array.length === 0) return 0
  return array[0] + sum(array.slice(1))
}

console.log(sum([1, 2, 3, 4, 5]))  // 15

// 优化版本:避免创建新数组
function sumOptimized(array, index = 0) {
  if (index >= array.length) return 0
  return array[index] + sumOptimized(array, index + 1)
}

// 尾递归版本
function sumTail(array, index = 0, total = 0) {
  if (index >= array.length) return total
  return sumTail(array, index + 1, total + array[index])
}

// 递归版本：扁平化所有层级
function flatten(array) {
  const result = []
  
  for (const item of array) {
    if (Array.isArray(item)) {
      result.push(...flatten(item))
    } else {
      result.push(item)
    }
  }
  return result
}

// 指定深度的扁平化（递归控制 depth）
function flattenDepth(array, depth) {
  return array.reduce((acc, item) => {
    if (Array.isArray(item) && depth > 1) {
      return acc.concat(flattenDepth(item, depth - 1))
    }
    return acc.concat(item)
  }, [])
}

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

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

function deepClone(obj, hash = new WeakMap()) {
  // 处理 null 和非对象类型
  if (obj === null || typeof obj !== 'object') {
    return obj
  }
  
  // 处理循环引用
  if (hash.has(obj)) {
    return hash.get(obj)
  }
  
  // 处理 Date
  if (obj instanceof Date) {
    return new Date(obj.getTime())
  }
  
  // 处理 RegExp
  if (obj instanceof RegExp) {
    return new RegExp(obj.source, obj.flags)
  }
  
  // 处理 Map
  if (obj instanceof Map) {
    const map = new Map()
    obj.forEach((value, key) => map.set(key, deepClone(value, hash)))
    return map
  }
  
  // 处理 Set
  if (obj instanceof Set) {
    const set = new Set()
    obj.forEach((value) => set.add(deepClone(value, hash)))
    return set
  }
  
  // 处理数组
  if (Array.isArray(obj)) {
    hash.set(obj, obj)
    const arr = obj.map((item) => deepClone(item, hash))
    hash.set(obj, arr)
    return arr
  }
  
  // 处理普通对象
  const cloned = {}
  hash.set(obj, cloned)
  for (const key in obj) {
    if (Object.prototype.hasOwnProperty.call(obj, key)) {
      cloned[key] = deepClone(obj[key], hash)
    }
  }
  return cloned
}

// 使用
const obj = { a: 1, nested: { b: 2 }, date: new Date(), list: [1, 2, 3] }
obj.self = obj  // 循环引用

const cloned = deepClone(obj)
console.log(cloned.a)        // 1
console.log(cloned.self.a)   // 1

const tree = {
  value: 1,
  children: [
    {
      value: 2,
      children: [
        { value: 4, children: [] },
        { value: 5, children: [] }
      ]
    },
    {
      value: 3,
      children: [
        { value: 6, children: [] },
        { value: 7, children: [] }
      ]
    }
  ]
}

// 深度优先遍历查找节点
function findNode(node, predicate) {
  // 先检查当前节点
  if (predicate(node)) {
    return node
  }
  // 递归遍历子节点
  for (const child of node.children) {
    const found = findNode(child, predicate)
    if (found) {
      return found
    }
  }
  return null
}

console.log(findNode(tree, node => node.value === 5))
// { value: 5, children: [] }

function binarySearch(array, target, left = 0, right = array.length - 1) {
  // 基线条件
  if (left > right) return -1
  
  const mid = Math.floor((left + right) / 2)
  
  if (array[mid] === target) return mid
  if (array[mid] > target) {
    return binarySearch(array, target, left, mid - 1)
  }
  return binarySearch(array, target, mid + 1, right)
}

const arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
console.log(binarySearch(arr, 7))  // 6

function quickSort(array) {
  // 基线条件
  if (array.length <= 1) return array
  
  const pivot = array[0]
  const left = []
  const right = []
  
  // 分区
  for (let i = 1; i < array.length; i++) {
    if (array[i] < pivot) {
      left.push(array[i])
    } else {
      right.push(array[i])
    }
  }
  
  // 递归排序并合并
  return [...quickSort(left), pivot, ...quickSort(right)]
}

console.log(quickSort([3, 1, 4, 1, 5, 9, 2, 6]))
// [1, 1, 2, 3, 4, 5, 6, 9]

// 模拟文件系统
const fileSystem = {
  name: 'root',
  type: 'directory',
  children: [
    {
      name: 'src',
      type: 'directory',
      children: [
        { name: 'index.js', type: 'file', size: 1024 },
        { name: 'utils.js', type: 'file', size: 512 }
      ]
    },
    { name: 'package.json', type: 'file', size: 6400 }
  ]
}

// 递归计算目录大小
function calculateDirectorySize(node) {
  if (node.type === 'file') {
    return node.size
  }
  return node.children.reduce((sum, child) => {
    return sum + calculateDirectorySize(child)
  }, 0)
}

console.log('Total size:', calculateDirectorySize(fileSystem), 'bytes')
// Total size: 7936 bytes

// 遍历 DOM 树
function traverseDOM(node, callback, depth = 0) {
  callback(node, depth)
  
  if (node.children && node.children.length > 0) {
    Array.from(node.children).forEach(child => {
      traverseDOM(child, callback, depth + 1)
    })
  }
}

// 使用示例
traverseDOM(document.body, (node, depth) => {
  console.log(`${'  '.repeat(depth)}<${node.nodeName.toLowerCase()}>`)
})

// 递归查找所有指定 class 的元素
function findAllByClass(node, className, result = []) {
  if (node.classList && node.classList.contains(className)) {
    result.push(node)
  }
  
  if (node.children) {
    Array.from(node.children).forEach(child => {
      findAllByClass(child, className, result)
    })
  }
  
  return result
}

// 根据 JSONPath 查找数据
function findByPath(obj, path) {
  const keys = path.split('.').filter(Boolean)
  
  function traverse(current, remaining) {
    if (remaining.length === 0) return current
    
    const [key, ...rest] = remaining
    
    // 处理数组索引
    if (Array.isArray(current) && /^\d+$/.test(key)) {
      return traverse(current[parseInt(key)], rest)
    }
    
    // 处理通配符 `*`：遍历数组所有元素
    if (Array.isArray(current) && key === '*') {
      return current.map(item => traverse(item, rest))
    }
    
    // 处理对象属性
    if (current && typeof current === 'object' && key in current) {
      return traverse(current[key], rest)
    }
    
    return undefined
  }
  
  return traverse(obj, keys)
}

// 使用
const data = {
  users: [
    { name: 'Alice', age: 25 },
    { name: 'Bob', age: 30 }
  ]
}

console.log(findByPath(data, 'users.0.name'))  // 'Alice'
console.log(findByPath(data, 'users.*.name'))  // ['Alice', 'Bob']

// 将扁平数组转换为树形结构
function arrayToTree(items, parentId = null) {
  return items
    .filter(item => item.parentId === parentId)
    .map(item => ({
      ...item,
      children: arrayToTree(items, item.id)
    }))
}

const flatArray = [
  { id: 1, name: 'Root', parentId: null },
  { id: 2, name: 'Child1', parentId: 1 },
  { id: 3, name: 'Child2', parentId: 1 },
  { id: 4, name: 'Grandchild1', parentId: 2 }
]

const tree = arrayToTree(flatArray)
console.log(JSON.stringify(tree, null, 2))

// 将树形结构转回扁平数组
function treeToArray(node, result = [], parentId = null) {
  result.push({ ...node, parentId })
  if (node.children) {
    node.children.forEach(child => {
      treeToArray(child, result, node.id)
    })
  }
  
  return result
}

function countdown(n) {
  if (n <= 0) return
  countdown(n - 1)
}

countdown(100000)
// RangeError: Maximum call stack size exceeded

function fibonacci(n) {
  if (n <= 1) return n
  return fibonacci(n - 1) + fibonacci(n - 2)
}

// fibonacci(50) 的计算时间会非常长
// 时间复杂度:O(2^n)

function fibonacciMemo(n, memo = new Map()) {
  if (memo.has(n)) return memo.get(n)
  if (n <= 1) return n
  
  const result = fibonacciMemo(n - 1, memo) + fibonacciMemo(n - 2, memo)
  memo.set(n, result)
  
  return result
}

// 时间复杂度:O(n)

function createCounter() {
  let count = 0
  return function increment() {
    count++
    if (count < 100000) {
      return increment()  // 闭包引用 count,可能导致内存问题
    }
    return count
  }
}

const obj = { a: 1 }
obj.self = obj

function deepCloneBad(obj) {
  if (obj === null || typeof obj !== 'object') return obj
  
  const clone = Array.isArray(obj) ? [] : {}
  for (const key in obj) {
    clone[key] = deepCloneBad(obj[key])  // 无限递归
  }
  
  return clone
}

// RangeError: Maximum call stack size exceeded

function deepClone(obj, hash = new WeakMap()) {
  if (obj === null || typeof obj !== 'object') return obj
  
  if (hash.has(obj)) return hash.get(obj)
  
  const clone = Array.isArray(obj) ? [] : {}
  hash.set(obj, clone)
  
  for (const key in obj) {
    if (obj.hasOwnProperty(key)) {
      clone[key] = deepClone(obj[key], hash)
    }
  }
  
  return clone
}

// ❌ 错误示例
function infinite(n) {
  return infinite(n - 1)  // 缺少基线条件
}

// ✅ 正确示例
function finite(n) {
  if (n <= 0) return 0  // 添加基线条件
  return finite(n - 1)
}

// ❌ 错误示例:递增而非递减
function countdown(n) {
  if (n <= 0) return
  countdown(n + 1)  // 永远不会到达基线条件
}

// ✅ 正确示例
function countdown(n) {
  if (n <= 0) return
  countdown(n - 1)  // 向基线条件推进
}

// 性能测试工具
function measurePerformance(name, fn, ...args) {
  const start = performance.now()
  const result = fn(...args)
  const end = performance.now()
  
  console.log(`${name}:`)
  console.log(`  结果:${result}`)
  console.log(`  耗时:${(end - start).toFixed(4)} ms`)
  
  return result
}

// 测试不同实现
measurePerformance('fibonacci(35) 朴素递归', fibonacci, 35)
measurePerformance('fibonacci(35) 记忆化', fibonacciMemo, 35)
measurePerformance('fibonacci(35) 迭代', fibonacciIterative, 35)

fibonacci(35) 朴素递归:
  结果:9227465
  耗时:42.3512 ms

fibonacci(35) 记忆化:
  结果:9227465
  耗时:0.1234 ms

fibonacci(35) 迭代:
  结果:9227465
  耗时:0.0456 ms

// 通用记忆化函数
function memoize(fn) {
  const cache = new Map()
  
  return function(...args) {
    const key = JSON.stringify(args)
    
    if (cache.has(key)) {
      return cache.get(key)
    }
    
    const result = fn.apply(this, args)
    cache.set(key, result)
    
    return result
  }
}

// 使用示例
const memoizedFib = memoize(function fib(n) {
  if (n <= 1) return n
  return fib(n - 1) + fib(n - 2)
})

console.log(memoizedFib(50))  // 12586269025

// 普通递归
function factorial(n) {
  if (n <= 1) return 1
  return n * factorial(n - 1)  // 不是尾递归
}

// 尾递归
function factorialTail(n, total = 1) {
  if (n <= 1) return total
  return factorialTail(n - 1, n * total)  // 尾递归
}

// 结合记忆化和迭代
function fibonacciOptimized(n) {
  const cache = new Map([[0, 0], [1, 1]])
  
  function fib(m) {
    if (cache.has(m)) return cache.get(m)
    
    let a = 0, b = 1
    for (let i = 2; i <= m; i++) {
      [a, b] = [b, a + b]
      cache.set(i, b)
    }
    
    return b
  }
  
  return fib(n)
}

// ✅ 尾调用
function foo() {
  return bar()  // 最后一步调用 bar
}

// ❌ 不是尾调用
function foo() {
  bar()  // 最后一步不是调用
  return  // 隐式返回 undefined
}

function foo() {
  return bar() + 1  // 最后一步是加法,不是调用
}

function foo() {
  const result = bar()
  return result  // 最后一步是返回变量,不是调用
}

// ✅ 尾调用示例
function foo1() { return bar(); }
function foo2(x) { return x ? bar() : baz(); }
function foo3() { return bar.arguments; }
function foo4() { return (bar)(); }
function foo5() { return (bar)(); }

// ❌ 非尾调用示例
function foo6() { bar(); }
function foo7() { return bar() + 1; }
function foo8() { return 1 + bar(); }
function foo9() { return bar(), baz(); }  // 最后调用 baz,但前面还有 bar
function foo10() { return new bar(); }    // new 操作符创建对象

普通递归的调用栈:
┌─────────────────────┐
│ factorial(1)        │ 返回 1
├─────────────────────┤
│ factorial(2)        │ 计算 2 * 1,等待返回
├─────────────────────┤
│ factorial(3)        │ 计算 3 * ?,等待返回
├─────────────────────┤
│ factorial(4)        │ 计算 4 * ?,等待返回
├─────────────────────┤
│ factorial(5)        │ 计算 5 * ?,等待返回
└─────────────────────┘
需要保留所有栈帧

尾递归的调用栈:
┌─────────────────────┐
│ factorial(5, 1)     │
├─────────────────────┤
│ factorial(4, 5)     │ 替换上一个栈帧
├─────────────────────┤
│ factorial(3, 20)    │ 替换上一个栈帧
├─────────────────────┤
│ factorial(2, 60)    │ 替换上一个栈帧
├─────────────────────┤
│ factorial(1, 120)   │ 替换上一个栈帧
└─────────────────────┘
返回 120
只需一个栈帧

// 原始函数
function sum(n) {
  if (n <= 0) return 0
  return n + sum(n - 1)  // 递归后还有加法操作
}

// 添加累加器
function sumTail(n, total = 0) {
  if (n <= 0) return total
  return sumTail(n - 1, total + n)  // 递归是最后一步
}

// 普通递归
function factorial(n) {
  if (n <= 1) return 1
  return n * factorial(n - 1)
}

// 尾递归
function factorialTail(n, total = 1) {
  if (n <= 1) return total
  return factorialTail(n - 1, n * total)
}

// 普通递归
function fibonacci(n) {
  if (n <= 1) return n
  return fibonacci(n - 1) + fibonacci(n - 2)
}

// 尾递归
function fibonacciTail(n, a = 0, b = 1) {
  if (n === 0) return a
  if (n === 1) return b
  return fibonacciTail(n - 1, b, a + b)
}

// 普通递归
function sum(array) {
  if (array.length === 0) return 0
  return array[0] + sum(array.slice(1))
}

// 尾递归
function sumTail(array, total = 0) {
  if (array.length === 0) return total
  return sumTail(array.slice(1), total + array[0])
}

// 更高效的尾递归(避免创建新数组)
function sumTailOptimized(array, index = 0, total = 0) {
  if (index >= array.length) return total
  return sumTailOptimized(array, index + 1, total + array[index])
}

'use strict'

function factorial(n, total = 1) {
  if (n <= 1) return total
  return factorial(n - 1, n * total)
}

// ✅ 正确
function foo() {
  return bar()
}

// ❌ 不在尾位置
function foo() {
  const result = bar()
  return result
}

// ❌ 会导致优化失败
function foo() {
  'use strict'
  console.log(foo.caller)  // 访问 caller
  return bar()
}

function isTailCallOptimized() {
  'use strict'
  
  function test(n) {
    if (n === 0) return 0
    return test(n - 1)
  }
  
  try {
    test(100000)
    return true
  } catch (e) {
    return false
  }
}

console.log('支持尾调用优化:', isTailCallOptimized())

// 蹦床函数
function trampoline(fn) {
  return function(...args) {
    let result = fn(...args)
    
    while (typeof result === 'function') {
      result = result()
    }
    
    return result
  }
}

// 使用蹦床的递归函数
function sumThunk(n, total = 0) {
  if (n <= 0) return total
  return () => sumThunk(n - 1, total + n)
}

const sum = trampoline(sumThunk)
console.log(sum(100000))  // 5000050000

class Trampoline {
  static run(fn, ...args) {
    let result = fn(...args)
    
    while (result instanceof Trampoline) {
      result = result.execute()
    }
    
    return result
  }
  
  // 打包一个"延迟执行"的步骤
  static bounce(fn, ...args) {
    return new Trampoline(() => fn(...args))
  }
  
  // 标记递归结束，返回最终值
  static done(value) {
    return new Trampoline(() => value, true)
  }
  
  constructor(fn, done = false) {
    this.fn = fn
    this.done = done
  }
  
  execute() {
    if (this.done) {
      return this.fn()
    }
    // 执行一步，返回下一个待执行的步骤或最终值
    return this.fn()
  }
}

// 使用蹦床函数避免栈溢出
function sumTrampoline(n, total = 0) {
  if (n <= 0) return Trampoline.done(total)
  return Trampoline.bounce(sumTrampoline, n - 1, total + n)
}

const result = Trampoline.run(sumTrampoline, 100000)
console.log(result)  // 5000050000

// 阶乘的蹦床实现
function factorialTrampoline(n, total = 1) {
  if (n <= 1) return total
  return () => factorialTrampoline(n - 1, n * total)
}

function trampoline(fn, ...args) {
  let result = fn(...args)
  
  while (typeof result === 'function') {
    result = result()
  }
  
  return result
}

console.log(trampoline(factorialTrampoline, 10000))

// 斐波那契的蹦床实现
function fibonacciTrampoline(n, a = 0, b = 1) {
  if (n === 0) return a
  if (n === 1) return b
  return () => fibonacciTrampoline(n - 1, b, a + b)
}

console.log(trampoline(fibonacciTrampoline, 1000))

// ❌ 无限递归
function foo() {
  foo()
}

// ✅ 有明确的基线条件
function foo(n) {
  if (n <= 0) return  // 基线条件
  foo(n - 1)
}

// ✅ 多个基线条件
function validate(obj, path = '') {
  if (obj === null) return { valid: false, path }
  if (typeof obj !== 'object') return { valid: true }
  // ... 其他逻辑
}

// ❌ 没有推进
function countdown(n) {
  if (n <= 0) return
  countdown(n)  // 参数不变
}

// ✅ 正确推进
function countdown(n) {
  if (n <= 0) return
  countdown(n - 1)  // 参数递减
}

// ❌ 重复计算
function fibonacci(n) {
  if (n <= 1) return n
  return fibonacci(n - 1) + fibonacci(n - 2)
}

// ✅ 使用记忆化
function fibonacciMemo(n, memo = new Map()) {
  if (memo.has(n)) return memo.get(n)
  if (n <= 1) return n
  
  const result = fibonacciMemo(n - 1, memo) + fibonacciMemo(n - 2, memo)
  memo.set(n, result)
  
  return result
}

// ✅ 完善的边界检查
function deepClone(obj, hash = new WeakMap()) {
  // 边界情况 1:null
  if (obj === null) return null
  
  // 边界情况 2:非对象类型
  if (typeof obj !== 'object') return obj
  
  // 边界情况 3:循环引用
  if (hash.has(obj)) return hash.get(obj)
  
  // 边界情况 4:特殊对象
  if (obj instanceof Date) return new Date(obj)
  if (obj instanceof RegExp) return new RegExp(obj)
  
  // 正常递归逻辑
  const clone = Array.isArray(obj) ? [] : {}
  hash.set(obj, clone)
  
  for (const key in obj) {
    if (obj.hasOwnProperty(key)) {
      clone[key] = deepClone(obj[key], hash)
    }
  }
  
  return clone
}

function safeRecurse(obj, fn, maxDepth = 1000, depth = 0) {
  if (depth > maxDepth) {
    throw new Error(`递归深度超过限制:${maxDepth}`)
  }
  
  fn(obj, depth)
  
  if (typeof obj === 'object' && obj !== null) {
    Object.values(obj).forEach(value => {
      safeRecurse(value, fn, maxDepth, depth + 1)
    })
  }
}

// 简单问题:优先使用递归(代码清晰)
function factorial(n) {
  if (n <= 1) return 1
  return n * factorial(n - 1)
}

// 性能敏感:使用迭代
function factorialIterative(n) {
  let result = 1
  for (let i = 2; i <= n; i++) {
    result *= i
  }
  return result
}

// 深度大:使用尾递归或蹦床
function factorialTail(n, total = 1) {
  if (n <= 1) return total
  return factorialTail(n - 1, n * total)
}

// 外部接口简洁,内部递归实现
function flatten(array) {
  const result = []
  
  function flattenRecursive(arr) {
    for (const item of arr) {
      if (Array.isArray(item)) {
        flattenRecursive(item)
      } else {
        result.push(item)
      }
    }
  }
  
  flattenRecursive(array)
  return result
}

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

function debugRecurse(obj, depth = 0, maxDepth = 100) {
  if (depth > maxDepth) {
    console.warn(`达到最大深度 ${maxDepth}`)
    return
  }
  
  const indent = '  '.repeat(depth)
  console.log(`${indent}处理:`, obj)
  
  if (typeof obj === 'object' && obj !== null) {
    Object.entries(obj).forEach(([key, value]) => {
      console.log(`${indent}${key}:`)
      debugRecurse(value, depth + 1, maxDepth)
    })
  }
}

// 场景 1:树形结构处理 - 推荐递归
function traverseTree(node) {
  if (!node) return
  
  console.log(node.value)
  traverseTree(node.left)
  traverseTree(node.right)
}

// 场景 2:简单计数 - 推荐迭代
function sumTo(n) {
  let total = 0
  for (let i = 1; i <= n; i++) {
    total += i
  }
  return total
}

// 场景 3:斐波那契 - 迭代比递归更高效
function fibonacciIterative(n) {
  if (n <= 1) return n
  let a = 0, b = 1
  for (let i = 2; i <= n; i++) {
    [a, b] = [b, a + b]
  }
  
  return b
}

// 递归版本
function factorialRecursive(n) {
  if (n <= 1) return 1
  return n * factorialRecursive(n - 1)
}

// 迭代版本
function factorialIterative(n) {
  let result = 1
  for (let i = 2; i <= n; i++) {
    result *= i
  }
  return result
}

// 迭代版本
function sumIterative(array) {
  let total = 0
  for (let i = 0; i < array.length; i++) {
    total += array[i]
  }
  return total
}

// 递归版本
function sumRecursive(array, index = 0) {
  if (index >= array.length) return 0
  return array[index] + sumRecursive(array, index + 1)
}

function factorialWithTrace(n, depth = 0) {
  const indent = '  '.repeat(depth)
  console.log(`${indent}factorial(${n})`)
  
  if (n <= 1) {
    console.log(`${indent}返回 1`)
    return 1
  }
  
  const result = n * factorialWithTrace(n - 1, depth + 1)
  console.log(`${indent}返回 ${result}`)
  
  return result
}

factorialWithTrace(5)

factorial(5)
  factorial(4)
    factorial(3)
      factorial(2)
        factorial(1)
        返回 1
      返回 2
    返回 6
  返回 24
返回 120

function deepCloneWithDepth(obj, hash = new WeakMap(), depth = 0) {
  console.log(`深度:${depth}, 类型:${typeof obj}`)
  
  if (depth > 100) {
    throw new Error('递归深度超过限制')
  }
  
  if (obj === null || typeof obj !== 'object') {
    return obj
  }
  
  if (hash.has(obj)) {
    return hash.get(obj)
  }
  
  const clone = Array.isArray(obj) ? [] : {}
  hash.set(obj, clone)
  
  for (const key in obj) {
    if (obj.hasOwnProperty(key)) {
      clone[key] = deepCloneWithDepth(obj[key], hash, depth + 1)
    }
  }
  
  return clone
}

function analyzePerformance(fn, name) {
  return function(...args) {
    const start = performance.now()
    const startMem = process.memoryUsage ? process.memoryUsage().heapUsed : 0
    
    const result = fn(...args)
    
    const end = performance.now()
    const endMem = process.memoryUsage ? process.memoryUsage().heapUsed : 0
    
    console.log(`[${name}]`)
    console.log(`  时间:${(end - start).toFixed(4)} ms`)
    if (process.memoryUsage) {
      console.log(`  内存:${((endMem - startMem) / 1024).toFixed(2)} KB`)
    }
    
    return result
  }
}

const factorialAnalyzed = analyzePerformance(factorial, '阶乘')
factorialAnalyzed(10)

function recursiveWithBreakpoint(n, breakpoints = []) {
  // 在特定值设置断点
  if (breakpoints.includes(n)) {
    debugger  // 触发断点
  }
  
  if (n <= 0) return 0
  return n + recursiveWithBreakpoint(n - 1, breakpoints)
}

// 在 n = 5, 3, 1 时触发断点
recursiveWithBreakpoint(10, [5, 3, 1])

// 方案 1:使用尾递归(需环境支持)
function tailRecursion(n, acc = 0) {
  if (n <= 0) return acc
  return tailRecursion(n - 1, acc + n)
}

// 方案 2:使用蹦床函数
function trampoline(n, acc = 0) {
  if (n <= 0) return acc
  return () => trampoline(n - 1, acc + n)
}

// 方案 3:使用迭代
function iterative(n) {
  let acc = 0
  for (let i = 1; i <= n; i++) {
    acc += i
  }
  return acc
}

// 方案 4:限制递归深度
function safeRecurse(n, maxDepth = 10000, depth = 0) {
  if (depth > maxDepth) throw new Error('递归过深')
  if (n <= 0) return 0
  return n + safeRecurse(n - 1, maxDepth, depth + 1)
}

// 带缓存大小限制的记忆化
function memoizeWithLimit(fn, limit = 100) {
  const cache = new Map()
  const keys = []
  
  return function(...args) {
    const key = JSON.stringify(args)
    
    if (cache.has(key)) {
      return cache.get(key)
    }
    
    const result = fn.apply(this, args)
    cache.set(key, result)
    keys.push(key)
    
    // 超过限制时删除最旧的缓存
    if (keys.length > limit) {
      const oldest = keys.shift()
      cache.delete(oldest)
    }
    
    return result
  }
}

// 异步递归
async function asyncRecurse(n) {
  if (n <= 0) return 0
  
  // 模拟异步操作
  await new Promise(resolve => setTimeout(resolve, 100))
  
  return n + await asyncRecurse(n - 1)
}

// 并行异步递归
async function asyncParallel(array) {
  if (array.length === 0) return []
  
  const [first, ...rest] = array
  const [firstResult, restResult] = await Promise.all([
    processItem(first),
    asyncParallel(rest)
  ])
  
  return [firstResult, ...restResult]
}

async function processItem(item) {
  await new Promise(resolve => setTimeout(resolve, 50))
  return item * 2
}

// Babel 转换配置
{
  "plugins":[
    ["@babel/plugin-transform-runtime", {
      "helpers":true,
      "regenerator":true
    }]
  ]
}

// 或使用显式的循环
function sumLoop(n) {
  let total = 0
  while (n > 0) {
    total += n
    n--
  }
  return total
}

// 单元测试示例
function testFactorial() {
  // 测试基线条件
  console.assert(factorial(0) === 1, 'factorial(0) should be 1')
  console.assert(factorial(1) === 1, 'factorial(1) should be 1')
  
  // 测试正常情况
  console.assert(factorial(5) === 120, 'factorial(5) should be 120')
  console.assert(factorial(10) === 3628800, 'factorial(10) should be 3628800')
  
  // 测试边界情况
  console.assert(factorial(-1) === 1, 'factorial(-1) should be 1')
  
  console.log('所有测试通过')
}

// 性能测试
function testPerformance() {
  const start = performance.now()
  const result = fibonacciMemo(50)
  const end = performance.now()
  
  console.log(`结果:${result}`)
  console.log(`耗时:${end - start} ms`)
  console.assert(end - start < 10, '性能测试未通过')
}

// Y 组合子:在匿名函数中实现递归
const Y = (f) => ((x) => f((v) => x(x)(v)))((x) => f((v) => x(x)(v)))

// 使用 Y 组合子实现阶乘
const factorial = Y((fact) => (n) => {
  if (n <= 1) return 1
  return n * fact(n - 1)
})

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

// 柯里化递归函数
const curriedFactorial = (n) => (total = 1) => {
  if (n <= 1) return total
  return curriedFactorial(n - 1)(n * total)
}

console.log(curriedFactorial(5)())  // 120

// 链表
class ListNode {
  constructor(value, next = null) {
    this.value = value
    this.next = next
  }
}

// 递归遍历链表
function traverseList(node, callback) {
  if (node === null) return
  callback(node.value)
  traverseList(node.next, callback)
}

// 中序遍历二叉树（左-根-右）
class TreeNode {
  constructor(value, left = null, right = null) {
    this.value = value
    this.left = left
    this.right = right
  }
}

function inorderTraversal(node, callback) {
  if (node === null) return
  
  inorderTraversal(node.left, callback)
  callback(node.value)
  inorderTraversal(node.right, callback)
}

// 递归生成器
function* fibonacciGenerator(n, a = 0, b = 1) {
  if (n === 0) return
  yield a
  yield* fibonacciGenerator(n - 1, b, a + b)
}

const fib = fibonacciGenerator(10)
console.log([...fib])  // [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

// 无限序列
function* infiniteFibonacci() {
  let a = 0, b = 1
  while (true) {
    yield a
    ;[a, b] = [b, a + b]
  }
}

const infiniteFib = infiniteFibonacci()
console.log(infiniteFib.next().value)  // 0
console.log(infiniteFib.next().value)  // 1
console.log(infiniteFib.next().value)  // 1

// 自定义记忆化策略
class AdvancedMemo {
  constructor(fn, options = {}) {
    this.fn = fn
    this.cache = new Map()
    this.maxSize = options.maxSize || 100
    this.ttl = options.ttl || 60000  // 默认 60 秒
    this.hits = 0
    this.misses = 0
  }
  
  call(...args) {
    const key = JSON.stringify(args)
    const now = Date.now()
    const entry = this.cache.get(key)
    
    // 命中缓存且未过期
    if (entry && now - entry.time < this.ttl) {
      this.hits++
      return entry.value
    }
    
    // 未命中或已过期
    this.misses++
    const value = this.fn(...args)
    
    // 超过最大容量时，删除最旧的缓存（简单 LRU）
    if (this.cache.size >= this.maxSize) {
      const oldestKey = this.cache.keys().next().value
      this.cache.delete(oldestKey)
    }
    this.cache.set(key, { value, time: now })
    
    return value
  }
  
  // 获取统计信息
  getStats() {
    return {
      hits: this.hits,
      misses: this.misses,
      cacheSize: this.cache.size,
      hitRate: this.hits / (this.hits + this.misses)
    }
  }
}


// 使用示例
const memoFib = new AdvancedMemo(fibonacci, { maxSize:50, ttl:30000 })
console.log(memoFib.call(40))
console.log(memoFib.call(40))  // 从缓存读取
console.log(memoFib.getStats())

问题复杂度
    ↓
简单的重复操作 → 迭代
    ↓
树形/嵌套结构 → 递归
    ↓
深度可能很大 → 尾递归/蹦床
    ↓
性能关键 → 迭代 + 记忆化