尾调用优化：递归性能提升策略 ​

// 递归的栈溢出问题
class RecursionStackOverflow {
  static demonstrateProblem() {
    console.log('=== 递归栈溢出示例 ===\n');
    
    // 普通递归
    function factorial(n) {
      if (n <= 1) return 1;
      return n * factorial(n - 1);
    }
    
    console.log('阶乘函数（普通递归）：');
    console.log(`factorial(5) = ${factorial(5)}`);
    console.log(`factorial(10) = ${factorial(10)}`);
    
    // 测试栈深度
    console.log('\n测试栈深度限制：');
    
    function countDown(n) {
      if (n === 0) return 'done';
      return countDown(n - 1);
    }
    
    try {
      countDown(10000);
      console.log('countDown(10000) 成功');
    } catch (e) {
      console.log(`countDown(10000) 失败: ${e.message}`);
    }
    
    try {
      countDown(100000);
      console.log('countDown(100000) 成功');
    } catch (e) {
      console.log(`countDown(100000) 失败: ${e.message}`);
    }
  }
  
  static demonstrateStackGrowth() {
    console.log('\n=== 栈增长过程 ===\n');
    
    console.log('调用 factorial(5) 时的栈：');
    console.log('');
    console.log('  factorial(5)');
    console.log('    └─ factorial(4)');
    console.log('        └─ factorial(3)');
    console.log('            └─ factorial(2)');
    console.log('                └─ factorial(1)');
    console.log('                    └─ return 1');
    console.log('                return 2 * 1 = 2');
    console.log('            return 3 * 2 = 6');
    console.log('        return 4 * 6 = 24');
    console.log('    return 5 * 24 = 120');
    console.log('');
    console.log('栈深度与n成正比，n很大时会溢出\n');
  }
  
  static runAll() {
    this.demonstrateProblem();
    this.demonstrateStackGrowth();
  }
}

RecursionStackOverflow.runAll();

// 尾调用定义
class TailCallDefinition {
  static demonstrate() {
    console.log('=== 尾调用的定义 ===\n');
    
    console.log('尾调用（Tail Call）：');
    console.log('  函数的最后一个动作是调用另一个函数，');
    console.log('  且直接返回该调用的结果。\n');
    
    console.log('✅ 尾调用示例：');
    console.log(`
    function foo(x) {
      return bar(x);  // 尾调用：直接返回bar的结果
    }
    
    function factorial(n, acc = 1) {
      if (n <= 1) return acc;
      return factorial(n - 1, n * acc);  // 尾调用
    }
    `);
    
    console.log('❌ 非尾调用示例：');
    console.log(`
    function foo(x) {
      return 1 + bar(x);  // 非尾调用：返回后还要加1
    }
    
    function factorial(n) {
      if (n <= 1) return 1;
      return n * factorial(n - 1);  // 非尾调用：返回后还要乘n
    }
    
    function foo(x) {
      const result = bar(x);
      return result;  // 非尾调用：有中间变量
    }
    `);
  }
  
  static demonstrateExamples() {
    console.log('=== 更多尾调用示例 ===\n');
    
    console.log('条件表达式中的尾调用：');
    console.log(`
    function foo(n) {
      return n > 0 ? bar(n) : baz(n);  // 两个都是尾调用
    }
    `);
    
    console.log('逻辑表达式中的尾调用：');
    console.log(`
    function foo(x) {
      return x && bar(x);  // bar是尾调用
    }
    
    function foo(x) {
      return x || bar(x);  // bar是尾调用
    }
    `);
    
    console.log('逗号表达式中的尾调用：');
    console.log(`
    function foo(x) {
      return (doSomething(), bar(x));  // bar是尾调用
    }
    `);
    
    console.log('非尾调用的情况：');
    console.log(`
    function foo(x) {
      try {
        return bar(x);  // 非尾调用：try块内的调用
      } catch (e) {
        // ...
      }
    }
    
    function foo(x) {
      return bar(x).then(cb);  // 非尾调用：返回Promise链
    }
    `);
  }
  
  static runAll() {
    this.demonstrate();
    this.demonstrateExamples();
  }
}

TailCallDefinition.runAll();

// 尾调用优化原理
class TCOPrinciple {
  static demonstrate() {
    console.log('=== 尾调用优化原理 ===\n');
    
    console.log('无优化时的调用过程：');
    console.log(`
    function A() {
      return B();  // 尾调用
    }
    
    调用A():
      1. 创建A的栈帧
      2. 执行A的代码
      3. 调用B，创建B的栈帧
      4. B返回，销毁B的栈帧
      5. A返回，销毁A的栈帧
    
    栈: [A] → [A, B] → [A] → []
    `);
    
    console.log('有TCO时的调用过程：');
    console.log(`
    调用A():
      1. 创建A的栈帧
      2. 执行A的代码
      3. 复用A的栈帧调用B（跳转而非调用）
      4. B返回，销毁栈帧
    
    栈: [A] → [B] → []
    
    关键：A的栈帧被B复用，无需额外空间
    `);
  }
  
  static demonstrateStackReuse() {
    console.log('=== 栈帧复用 ===\n');
    
    console.log('尾递归阶乘（有TCO）：');
    console.log(`
    function factorial(n, acc = 1) {
      if (n <= 1) return acc;
      return factorial(n - 1, n * acc);
    }
    
    调用 factorial(5):
    
    无TCO的栈：
      factorial(5, 1)
        factorial(4, 5)
          factorial(3, 20)
            factorial(2, 60)
              factorial(1, 120)
                return 120
    
    有TCO的栈：
      factorial(5, 1) → 参数: (5, 1)
      复用为 factorial(4, 5) → 参数: (4, 5)
      复用为 factorial(3, 20) → 参数: (3, 20)
      复用为 factorial(2, 60) → 参数: (2, 60)
      复用为 factorial(1, 120) → 参数: (1, 120)
      return 120
    
    栈深度始终为1！
    `);
  }
  
  static demonstrateTransformation() {
    console.log('=== TCO等价于循环 ===\n');
    
    console.log('尾递归版本：');
    console.log(`
    function factorial(n, acc = 1) {
      if (n <= 1) return acc;
      return factorial(n - 1, n * acc);
    }
    `);
    
    console.log('等价的循环版本：');
    console.log(`
    function factorial(n, acc = 1) {
      while (true) {
        if (n <= 1) return acc;
        // 更新参数，继续循环
        acc = n * acc;
        n = n - 1;
      }
    }
    `);
    
    // 验证两个版本结果相同
    function factorialRecursive(n, acc = 1) {
      if (n <= 1) return acc;
      return factorialRecursive(n - 1, n * acc);
    }
    
    function factorialLoop(n, acc = 1) {
      while (true) {
        if (n <= 1) return acc;
        acc = n * acc;
        n = n - 1;
      }
    }
    
    console.log('\n验证：');
    console.log(`递归版本 factorial(10) = ${factorialRecursive(10)}`);
    console.log(`循环版本 factorial(10) = ${factorialLoop(10)}\n`);
  }
  
  static runAll() {
    this.demonstrate();
    this.demonstrateStackReuse();
    this.demonstrateTransformation();
  }
}

TCOPrinciple.runAll();

// ECMAScript规范与实现
class ES6TCOSpec {
  static demonstrate() {
    console.log('=== ECMAScript 6 规范 ===\n');
    
    console.log('ES6（ES2015）规定：');
    console.log('  • 严格模式下必须实现尾调用优化');
    console.log('  • 规范章节：14.6.1 Tail Position Calls');
    console.log('  • 目的：让递归算法可以处理任意深度\n');
    
    console.log('触发TCO的条件：');
    console.log('  1. 严格模式（"use strict"）');
    console.log('  2. 函数在尾位置被调用');
    console.log('  3. 直接返回调用结果');
    console.log('  4. 不在try-catch-finally块内\n');
    
    console.log('示例：');
    console.log(`
    "use strict";
    
    function factorial(n, acc = 1) {
      if (n <= 1) return acc;
      return factorial(n - 1, n * acc);  // 应该被优化
    }
    `);
  }
  
  static demonstrateV8Status() {
    console.log('=== V8 的实现现状 ===\n');
    
    console.log('V8曾经实现了TCO，但后来移除：');
    console.log('');
    console.log('时间线：');
    console.log('  2016: V8实现了TCO');
    console.log('  2017: V8移除了TCO支持');
    console.log('  现在: V8不支持隐式TCO\n');
    
    console.log('移除的原因：');
    console.log('  1. 调试困难');
    console.log('     • 栈帧被复用后，调试信息丢失');
    console.log('     • Error.stack不完整');
    console.log('');
    console.log('  2. 性能开销');
    console.log('     • 需要检测尾调用位置');
    console.log('     • 某些场景下实际变慢');
    console.log('');
    console.log('  3. 开发者体验');
    console.log('     • 优化是"隐式"的，难以预测');
    console.log('     • 不清楚何时真正被优化\n');
  }
  
  static demonstrateBrowserSupport() {
    console.log('=== 浏览器支持情况 ===\n');
    
    console.log('当前支持情况（2024）：');
    console.log('');
    console.log('  浏览器/引擎     支持TCO');
    console.log('  '.padEnd(35, '-'));
    console.log('  Safari (JSC)    ✅ 支持');
    console.log('  Chrome (V8)     ❌ 不支持');
    console.log('  Firefox (SM)    ❌ 不支持');
    console.log('  Edge (V8)       ❌ 不支持');
    console.log('  Node.js (V8)    ❌ 不支持');
    console.log('');
    console.log('只有Safari/WebKit完整实现了ES6 TCO\n');
  }
  
  static runAll() {
    this.demonstrate();
    this.demonstrateV8Status();
    this.demonstrateBrowserSupport();
  }
}

ES6TCOSpec.runAll();

// 手动转换为循环
class ManualConversion {
  static demonstrateLoopConversion() {
    console.log('=== 手动转换为循环 ===\n');
    
    console.log('原始尾递归：');
    console.log(`
    function sumTo(n, acc = 0) {
      if (n === 0) return acc;
      return sumTo(n - 1, acc + n);
    }
    `);
    
    console.log('手动转换为循环：');
    console.log(`
    function sumTo(n, acc = 0) {
      while (true) {
        if (n === 0) return acc;
        // 更新参数
        const newN = n - 1;
        const newAcc = acc + n;
        n = newN;
        acc = newAcc;
      }
    }
    `);
    
    // 实现
    function sumToLoop(n, acc = 0) {
      while (true) {
        if (n === 0) return acc;
        acc = acc + n;
        n = n - 1;
      }
    }
    
    console.log('验证：');
    console.log(`sumTo(100) = ${sumToLoop(100)}`);
    console.log(`sumTo(10000) = ${sumToLoop(10000)}`);
    console.log(`sumTo(1000000) = ${sumToLoop(1000000)}\n`);
  }
  
  static demonstrateComplexConversion() {
    console.log('=== 复杂递归的转换 ===\n');
    
    console.log('斐波那契（尾递归形式）：');
    console.log(`
    function fib(n, a = 0, b = 1) {
      if (n === 0) return a;
      return fib(n - 1, b, a + b);
    }
    `);
    
    console.log('转换为循环：');
    console.log(`
    function fib(n, a = 0, b = 1) {
      while (true) {
        if (n === 0) return a;
        const newA = b;
        const newB = a + b;
        n = n - 1;
        a = newA;
        b = newB;
      }
    }
    `);
    
    function fibLoop(n, a = 0, b = 1) {
      while (true) {
        if (n === 0) return a;
        const newA = b;
        const newB = a + b;
        n = n - 1;
        a = newA;
        b = newB;
      }
    }
    
    console.log('验证：');
    console.log(`fib(10) = ${fibLoop(10)}`);
    console.log(`fib(50) = ${fibLoop(50)}`);
    console.log(`fib(1000) = ${fibLoop(1000)} (BigInt needed for accuracy)\n`);
  }
  
  static runAll() {
    this.demonstrateLoopConversion();
    this.demonstrateComplexConversion();
  }
}

ManualConversion.runAll();

// Trampoline模式
class TrampolinePattern {
  static demonstrate() {
    console.log('=== Trampoline模式 ===\n');
    
    console.log('思路：');
    console.log('  不直接递归调用，而是返回一个"继续函数"');
    console.log('  由外部循环来调用这些函数\n');
    
    console.log('实现：');
    console.log(`
    // Trampoline执行器
    function trampoline(fn) {
      return function(...args) {
        let result = fn(...args);
        while (typeof result === 'function') {
          result = result();  // 执行返回的函数
        }
        return result;
      };
    }
    
    // 尾递归函数（返回函数而非直接递归）
    function factorialT(n, acc = 1) {
      if (n <= 1) return acc;
      return () => factorialT(n - 1, n * acc);
    }
    
    const factorial = trampoline(factorialT);
    `);
  }
  
  static demonstrateImplementation() {
    console.log('=== Trampoline实现 ===\n');
    
    // Trampoline执行器
    function trampoline(fn) {
      return function(...args) {
        let result = fn(...args);
        while (typeof result === 'function') {
          result = result();
        }
        return result;
      };
    }
    
    // 普通递归（会栈溢出）
    function sumRecursive(n, acc = 0) {
      if (n === 0) return acc;
      return sumRecursive(n - 1, acc + n);
    }
    
    // Trampoline版本
    function sumT(n, acc = 0) {
      if (n === 0) return acc;
      return () => sumT(n - 1, acc + n);  // 返回函数
    }
    
    const sum = trampoline(sumT);
    
    console.log('测试Trampoline版本：');
    console.log(`sum(100) = ${sum(100)}`);
    console.log(`sum(10000) = ${sum(10000)}`);
    console.log(`sum(100000) = ${sum(100000)}`);
    
    console.log('\n测试普通递归：');
    try {
      console.log(`sumRecursive(100000) = ${sumRecursive(100000)}`);
    } catch (e) {
      console.log(`sumRecursive(100000) 失败: ${e.message}\n`);
    }
  }
  
  static demonstrateAdvanced() {
    console.log('=== 带返回值标记的Trampoline ===\n');
    
    // 更清晰的实现
    class Bounce {
      constructor(fn) { this.fn = fn; }
    }
    
    class Done {
      constructor(value) { this.value = value; }
    }
    
    function trampoline(fn) {
      return function(...args) {
        let result = fn(...args);
        while (result instanceof Bounce) {
          result = result.fn();
        }
        return result.value;
      };
    }
    
    function factorialT(n, acc = 1) {
      if (n <= 1) return new Done(acc);
      return new Bounce(() => factorialT(n - 1, n * acc));
    }
    
    const factorial = trampoline(factorialT);
    
    console.log('使用类标记：');
    console.log(`factorial(5) = ${factorial(5)}`);
    console.log(`factorial(10) = ${factorial(10)}`);
    console.log(`factorial(170) = ${factorial(170)}\n`);
  }
  
  static runAll() {
    this.demonstrate();
    this.demonstrateImplementation();
    this.demonstrateAdvanced();
  }
}

TrampolinePattern.runAll();

// 生成器方案
class GeneratorApproach {
  static demonstrate() {
    console.log('=== 生成器处理递归 ===\n');
    
    console.log('思路：');
    console.log('  使用yield暂停执行，由外部控制继续');
    console.log('  类似Trampoline，但语法更自然\n');
  }
  
  static demonstrateImplementation() {
    console.log('=== 生成器实现 ===\n');
    
    // 执行生成器直到完成
    function run(gen) {
      let result = gen.next();
      while (!result.done) {
        result = gen.next(result.value);
      }
      return result.value;
    }
    
    // 生成器版本的阶乘
    function* factorialGen(n, acc = 1) {
      while (n > 1) {
        acc = n * acc;
        n = n - 1;
        yield;  // 暂停点
      }
      return acc;
    }
    
    console.log('测试生成器版本：');
    console.log(`factorial(5) = ${run(factorialGen(5))}`);
    console.log(`factorial(10) = ${run(factorialGen(10))}`);
    console.log(`factorial(170) = ${run(factorialGen(170))}\n`);
  }
  
  static demonstrateTreeTraversal() {
    console.log('=== 生成器遍历树结构 ===\n');
    
    // 树节点
    const tree = {
      value: 1,
      children: [
        { value: 2, children: [
          { value: 4, children: [] },
          { value: 5, children: [] }
        ]},
        { value: 3, children: [
          { value: 6, children: [] },
          { value: 7, children: [] }
        ]}
      ]
    };
    
    // 递归遍历（可能栈溢出）
    function* traverseRecursive(node) {
      yield node.value;
      for (const child of node.children) {
        yield* traverseRecursive(child);
      }
    }
    
    // 迭代遍历（使用显式栈）
    function* traverseIterative(root) {
      const stack = [root];
      while (stack.length > 0) {
        const node = stack.pop();
        yield node.value;
        // 逆序压入子节点
        for (let i = node.children.length - 1; i >= 0; i--) {
          stack.push(node.children[i]);
        }
      }
    }
    
    console.log('树结构：');
    console.log('      1');
    console.log('     / \\');
    console.log('    2   3');
    console.log('   / \\ / \\');
    console.log('  4  5 6  7\n');
    
    console.log('递归遍历:', [...traverseRecursive(tree)].join(', '));
    console.log('迭代遍历:', [...traverseIterative(tree)].join(', '));
  }
  
  static runAll() {
    this.demonstrate();
    this.demonstrateImplementation();
    this.demonstrateTreeTraversal();
  }
}

GeneratorApproach.runAll();

// 性能对比
class PerformanceComparison {
  static test() {
    console.log('=== 性能对比测试 ===\n');
    
    const N = 10000;
    const iterations = 1000;
    
    // 循环版本
    function sumLoop(n) {
      let acc = 0;
      while (n > 0) {
        acc += n;
        n--;
      }
      return acc;
    }
    
    // Trampoline版本
    function trampoline(fn) {
      return function(...args) {
        let result = fn(...args);
        while (typeof result === 'function') {
          result = result();
        }
        return result;
      };
    }
    
    function sumT(n, acc = 0) {
      if (n === 0) return acc;
      return () => sumT(n - 1, acc + n);
    }
    
    const sumTrampoline = trampoline(sumT);
    
    // 预热
    for (let i = 0; i < 100; i++) {
      sumLoop(N);
      sumTrampoline(N);
    }
    
    // 测试循环
    console.time('循环版本');
    for (let i = 0; i < iterations; i++) {
      sumLoop(N);
    }
    console.timeEnd('循环版本');
    
    // 测试Trampoline
    console.time('Trampoline版本');
    for (let i = 0; i < iterations; i++) {
      sumTrampoline(N);
    }
    console.timeEnd('Trampoline版本');
    
    console.log('');
    console.log('结论：');
    console.log('  • 循环版本最快');
    console.log('  • Trampoline有函数创建开销');
    console.log('  • 但Trampoline保持了递归的代码结构\n');
  }
  
  static runAll() {
    this.test();
  }
}

PerformanceComparison.runAll();

// 实际应用场景
class RealWorldScenarios {
  static demonstrateDeepJSON() {
    console.log('=== 场景1：深度嵌套JSON处理 ===\n');
    
    console.log('问题：处理深度嵌套的JSON数据');
    console.log(`
    // 深度嵌套的数据
    const deepData = {
      level1: {
        level2: {
          level3: {
            // ... 可能有数千层
          }
        }
      }
    };
    `);
    
    console.log('解决方案：使用迭代遍历');
    console.log(`
    function traverse(obj, callback) {
      const stack = [{ value: obj, path: [] }];
      
      while (stack.length > 0) {
        const { value, path } = stack.pop();
        callback(value, path);
        
        if (value && typeof value === 'object') {
          for (const key in value) {
            stack.push({ 
              value: value[key], 
              path: [...path, key] 
            });
          }
        }
      }
    }
    `);
  }
  
  static demonstrateFolderTraversal() {
    console.log('=== 场景2：文件系统遍历 ===\n');
    
    console.log('问题：遍历深度目录结构');
    console.log(`
    // 可能有很深的目录层级
    /project
      /node_modules
        /package-a
          /node_modules
            /package-b
              /node_modules
                // ...
    `);
    
    console.log('解决方案：使用队列或栈的迭代方式');
    console.log(`
    async function* walkDir(dir) {
      const queue = [dir];
      
      while (queue.length > 0) {
        const current = queue.shift();
        const entries = await fs.readdir(current);
        
        for (const entry of entries) {
          const path = join(current, entry);
          const stat = await fs.stat(path);
          
          if (stat.isDirectory()) {
            queue.push(path);
          }
          yield path;
        }
      }
    }
    `);
  }
  
  static demonstrateParser() {
    console.log('=== 场景3：解析器和编译器 ===\n');
    
    console.log('问题：解析深度嵌套的表达式');
    console.log(`
    // 深度嵌套的括号表达式
    ((((((((((a + b))))))))))
    `);
    
    console.log('解决方案：使用显式栈');
    console.log(`
    function parseExpression(tokens) {
      const stack = [];
      let current = null;
      
      for (const token of tokens) {
        if (token === '(') {
          stack.push(current);
          current = { type: 'group', children: [] };
        } else if (token === ')') {
          const parent = stack.pop();
          if (parent) {
            parent.children.push(current);
            current = parent;
          }
        } else {
          current.children.push(token);
        }
      }
      
      return current;
    }
    `);
  }
  
  static runAll() {
    this.demonstrateDeepJSON();
    this.demonstrateFolderTraversal();
    this.demonstrateParser();
  }
}

RealWorldScenarios.runAll();

// 最佳实践总结
class BestPractices {
  static summary() {
    console.log('=== 递归处理最佳实践 ===\n');
    
    console.log('1. 评估递归深度');
    console.log('   • 预估最大递归深度');
    console.log('   • 小于1000层通常安全');
    console.log('   • 深度不确定时考虑迭代\n');
    
    console.log('2. 优先使用循环');
    console.log('   • 性能最好');
    console.log('   • 无栈溢出风险');
    console.log('   • 代码可能略复杂\n');
    
    console.log('3. 需要递归结构时使用Trampoline');
    console.log('   • 保持递归的代码结构');
    console.log('   • 有一定性能开销');
    console.log('   • 适合算法实现\n');
    
    console.log('4. 使用生成器处理遍历');
    console.log('   • 语法自然');
    console.log('   • 支持惰性求值');
    console.log('   • 适合数据流处理\n');
    
    console.log('5. 不要依赖TCO');
    console.log('   • V8不支持隐式TCO');
    console.log('   • 只有Safari支持');
    console.log('   • 假设TCO不存在来编码\n');
  }
  
  static codeComparison() {
    console.log('=== 代码选择指南 ===\n');
    
    console.log('递归深度 < 100:');
    console.log('  → 直接使用递归，简单易读\n');
    
    console.log('递归深度 100-1000:');
    console.log('  → 递归可能OK，但考虑循环\n');
    
    console.log('递归深度 > 1000:');
    console.log('  → 必须使用循环或Trampoline\n');
    
    console.log('深度不确定:');
    console.log('  → 使用循环或Trampoline确保安全\n');
  }
  
  static runAll() {
    this.summary();
    this.codeComparison();
  }
}

BestPractices.runAll();