// 經(jīng)典遞歸示例：計(jì)算階乘
function factorial(n) {
  if (n <= 1) return 1;
  return n * factorial(n - 1); // 每次調(diào)用增加一個(gè)棧幀
}

// 調(diào)用過(guò)程
factorial(5) // 需要5個(gè)棧幀
factorial(10000) // 可能導(dǎo)致棧溢出

// 尾遞歸版階乘函數(shù)
function factorial(n, accumulator = 1) {
  if (n <= 1) return accumulator;
  return factorial(n - 1, n * accumulator); // 尾遞歸調(diào)用
}

// 在支持TCO的環(huán)境中，該實(shí)現(xiàn)不會(huì)造成棧溢出

// 迭代版階乘函數(shù)
function factorialIterative(n) {
  let result = 1;
  
  for(let i = n; i > 1; i--) {
    result *= i; // 在循環(huán)中更新?tīng)顟B(tài)
  }
  
  return result;
}

// 遞歸版DFS
function dfsRecursive(node) {
  if (!node) return;
  console.log(node.value);
  node.children.forEach(child => dfsRecursive(child));
}

// 迭代版DFS - 使用顯式棧
function dfsIterative(root) {
  const stack = [root]; // 手動(dòng)維護(hù)的棧
  
  while (stack.length) {
    const node = stack.pop();
    console.log(node.value);
    
    // 將子節(jié)點(diǎn)逆序推入棧中
    for (let i = node.children.length - 1; i >= 0; i--) {
      stack.push(node.children[i]);
    }
  }
}

// 1. 定義遞歸類型：要么是值，要么是函數(shù)
const done = value => ({ done: true, value });
const trampoline = fn => (...args) => {
  let result = fn(...args);
  while (result && typeof result === 'function') {
    result = result();
  }
  return result;
};

// 2. 創(chuàng)建蹦床式遞歸函數(shù)
function factorialTrampoline(n, acc = 1) {
  if (n <= 1) return done(acc);
  return () => factorialTrampoline(n - 1, n * acc); // 返回函數(shù)而非調(diào)用
}

// 3. 包裝為蹦床
const safeFactorial = trampoline(factorialTrampoline);

// 斐波那契數(shù)列的蹦床實(shí)現(xiàn)
function fibonacciTrampoline(n) {
  function fib(n, a = 0, b = 1) {
    return n === 0 ? done(a) : () => fib(n - 1, b, a + b);
  }
  return trampoline(fib)(n);
}

console.log(fibonacciTrampoline(100000)); // 可以計(jì)算超大值

function deepRecursion(n, callback) {
  if (n <= 0) return callback(1);
  
  // 將遞歸調(diào)用拆分為異步塊
  setTimeout(() => {
    deepRecursion(n - 1, result => {
      callback(n * result);
    });
  }, 0);
}

// 使用
deepRecursion(10000, console.log); // 不會(huì)棧溢出

function asyncFactorial(n) {
  return new Promise(resolve => {
    const trampoline = (n, acc = 1) => {
      if (n <= 1) resolve(acc);
      else setTimeout(() => trampoline(n - 1, acc * n), 0);
    };
    trampoline(n);
  });
}

asyncFactorial(10000).then(console.log); // 處理超大數(shù)

async function microtaskRecursion(n, acc = 1) {
  if (n <= 1) return acc;
  
  // 使用微任務(wù)拆分調(diào)用棧
  await Promise.resolve();
  return microtaskRecursion(n - 1, n * acc);
}

microtaskRecursion(10000).then(console.log);

function withTrampoline(fn) {
  return function(...args) {
    let result = fn.apply(this, args);
    
    while (typeof result === 'function') {
      result = result();
    }
    
    return result;
  };
}

// 使用
const safeRecursion = withTrampoline(function myRecursion(n) {
  if (n === 0) return 1;
  return () => myRecursion(n - 1) * n;
});

function memoize(fn) {
  const cache = new Map();
  return function memoized(...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 memoFibonacci = memoize(n => 
  n <= 2 ? 1 : memoFibonacci(n - 1) + memoFibonacci(n - 2)
);

// 普通遞歸（易棧溢出）
function deepClone(obj) {
  if (obj === null || typeof obj !== 'object') return obj;
  const clone = Array.isArray(obj) ? [] : {};
  for (let key in obj) {
    clone[key] = deepClone(obj[key]);
  }
  return clone;
}

// 安全的迭代版
function safeDeepClone(obj) {
  const stack = [{ src: obj, clone: {} }];
  const clonedObjects = new WeakMap();
  
  while (stack.length) {
    const { src, clone, key } = stack.pop() || {};
    
    if (key !== undefined) {
      clone[key] = Array.isArray(src) ? [] : {};
      clonedObjects.set(src, clone[key]);
    }
    
    const current = key ? src : clone;
    for (let k in src) {
      const value = src[k];
      if (value && typeof value === 'object') {
        if (clonedObjects.has(value)) {
          current[k] = clonedObjects.get(value);
        } else {
          stack.push({ src: value, clone: current, key: k });
        }
      } else {
        current[k] = value;
      }
    }
  }
  
  return clonedObjects.get(obj) || obj;
}

// 測(cè)試不同策略的執(zhí)行時(shí)間
function testPerformance(fn, n, times = 100) {
  const start = performance.now();
  for (let i = 0; i < times; i++) {
    fn(n);
  }
  return (performance.now() - start).toFixed(2) + 'ms';
}

console.log('遞歸:', testPerformance(factorial, 1000)); // 注意：使用小數(shù)字以避免棧溢出
console.log('迭代:', testPerformance(factorialIterative, 1000));
console.log('蹦床:', testPerformance(safeFactorial, 1000));

// 估算可用棧深度
function measureStackDepth() {
  try {
    return 1 + measureStackDepth();
  } catch (e) {
    return 1;
  }
}

const maxDepth = measureStackDepth();
console.log('當(dāng)前環(huán)境最大調(diào)用深度:', maxDepth);