如何消除递归简化区间细分有序值生成器？

你可以通过两个队列分别跟踪左、右分支的待处理区间，交替处理两个队列的元素，来模拟原递归生成器的交替输出逻辑，完全消除递归。以下是实现代码：

function* orderedSubdivisor(start: number, end: number): Generator<number> {
  const leftQueue: [number, number][] = [];
  const rightQueue: [number, number][] = [];

  // 输出根节点（初始区间的中点）
  const rootMid = (end - start) / 2 + start;
  yield rootMid;

  // 初始化左右队列，存入初始区间的左右子区间
  leftQueue.push([start, rootMid]);
  rightQueue.push([rootMid, end]);

  while (true) {
    // 处理左队列的下一个区间
    if (leftQueue.length > 0) {
      const [currStart, currEnd] = leftQueue.shift()!;
      const mid = (currEnd - currStart) / 2 + currStart;
      yield mid;
      // 将当前区间的左右子区间加入左队列，保持原递归的分支遍历顺序
      leftQueue.push([currStart, mid]);
      leftQueue.push([mid, currEnd]);
    }

    // 处理右队列的下一个区间
    if (rightQueue.length > 0) {
      const [currStart, currEnd] = rightQueue.shift()!;
      const mid = (currEnd - currStart) / 2 + currStart;
      yield mid;
      // 将当前区间的左右子区间加入右队列
      rightQueue.push([currStart, mid]);
      rightQueue.push([mid, currEnd]);
    }

    // 当两个队列都为空时退出（仅当区间无法再细分时触发）
    if (leftQueue.length === 0 && rightQueue.length === 0) {
      break;
    }
  }
}

// 测试示例
const iter = orderedSubdivisor(0, 64);
console.log(Array.from({ length: 63 }, () => iter.next().value));

逻辑说明 #

1. 初始步骤：先输出初始区间的中点，然后将初始区间拆分为左右两个子区间，分别存入leftQueue和rightQueue。
2. 交替处理队列：循环中先处理左队列的第一个区间，输出其中点，再将该区间的左右子区间加入左队列；接着处理右队列的第一个区间，执行同样的操作。
3. 终止条件：当两个队列都为空时（区间无法再细分，比如整数区间细分到最小单位），生成器停止。

满足需求验证 #

• 值唯一：每个区间的中点都是唯一的，且所有区间互不重叠（仅端点共享，不会产生重复中点）。
• 顺序一致：队列的处理顺序是确定的，每次运行生成器都会按相同顺序输出值。
• 间隔较大：交替从左、右分支取中点，相邻输出的数值间隔始终保持较大范围（比如32→16→48→8→40...）。
• 按需生成：生成器按需yield值，你可以根据需要取任意数量的输出，无需提前确定总数。

内容的提问来源于stack exchange，提问作者Zak Henry