很多朋友在初学排序算法时，通常先接触递归版本。递归写起来很爽，逻辑也顺，可一旦数据量变大，程序突然就崩了。这时候你可能会想：有没有一种写法，既能保留递归的清晰，又不担心栈溢出？今天我们就从排序这个例子聊聊非递归排序，顺便把尾递归优化、递归与迭代的关系、以及递归转迭代的通用方法一次性讲透。
一、递归排序为什么让人又爱又恨
递归排序最大的优点就是“照着思想写代码”。比如快速排序，核心思想是“分而治之”，用递归表达就是：左边排一下，右边排一下。归并排序也是，把数组分成两半，各自排好，再合并。这种自顶向下的思考方式，跟我们人类的思维习惯非常接近。
可是递归也有一个绕不开的代价：每一次函数调用，系统都要在内存里开出一块区域，叫做“栈帧”。栈帧里放着这个函数的局部变量、参数、返回地址等等。递归多深，系统栈就得叠多高。排序一个十万级别的数组，如果划分得特别不均匀，递归深度可能达到十万层。很多语言默认的调用栈根本扛不住，直接抛出“栈溢出”错误。
二、调用栈：递归背后的“隐形山”
2.1 什么是调用栈
你可以把调用栈想象成食堂里一摞盘子。每次调用一个函数，就像往上面摞一个盘子；函数返回，相当于拿走一个盘子。盘子摞得太高，风一吹就倒，这就是栈溢出。每个盘子就是前面说的栈帧。
在递归排序中，每一层递归不但要保存自己的参数，还要保存当前执行到哪一行，这样递归返回时才知道下一步干什么。比如递归快排里，先递归排序左半部分，等左半部分完成后，还得回到原来的位置继续处理右半部分。这个“回到原来的位置”的信息，就存在栈帧里。
2.2 递归排序的栈消耗
我们来看一个典型的递归快排实现。
// 技术栈：JavaScript
// 分区函数：把数组分成“小于轴点”和“大于轴点”两块
function partition(arr, left, right) {
const pivot = arr[right]; // 选最右边的元素当轴点
let i = left; // i 指向小于区间的末尾
for (let j = left; j < right; j++) {
if (arr[j] < pivot) {
[arr[i], arr[j]] = [arr[j], arr[i]]; // 交换
i++;
}
}
// 把轴点放到正确位置
[arr[i], arr[right]] = [arr[right], arr[i]];
return i; // 返回轴点下标
}
// 递归快速排序
function quickSortRecursive(arr, left = 0, right = arr.length - 1) {
if (left >= right) return; // 递归出口
const pivotIndex = partition(arr, left, right); // 获取轴点位置
quickSortRecursive(arr, left, pivotIndex - 1); // 排序左区间
quickSortRecursive(arr, pivotIndex + 1, right); // 排序右区间
}
这段代码逻辑很漂亮，但极端情况下，比如数组已经有序，而且每次选最后一个元素做轴点，那么每次划分都只能排除一个元素，递归深度直接变成n。n是十万的时候，系统栈要存放十万个栈帧，每个栈帧即使只占几十字节，加起来也是好几兆，甚至超过默认栈大小。这就是递归排序的“隐形山”。
三、尾递归优化：救星还是安慰剂？
3.1 什么是尾递归
尾递归是指递归调用是函数的最后一个操作，并且递归调用的结果直接返回，不再参与其他计算。比如计算阶乘时，普通递归是“先递归再乘”，尾递归则是“先乘再递归”，把累乘结果当成参数传下去。
下面演示一下尾递归风格的阶乘。
// 技术栈：JavaScript
// 普通递归：计算 n! 要先递归，返回后再乘以 n
function factorialNormal(n) {
if (n <= 1) return 1;
return n * factorialNormal(n - 1); // 返回后还要做乘法
}
// 尾递归：把每一步的结果缓存在 total 里
function factorialTail(n, total = 1) {
if (n <= 1) return total;
return factorialTail(n - 1, n * total); // 递归调用是最后一步
}
普通递归的每一层都需要保留“n”，因为要等递归返回后做乘法。而尾递归的每一层不再需要保留当前帧的任何信息，因为结果已经通过参数传下去了。如果编译器做了尾递归优化，可以复用当前栈帧，把递归变成循环，避免栈增长。
3.2 尾递归优化确实有用
在支持尾递归优化的语言里，尾递归几乎等价于循环。比如 Scala、Kotlin 等 JVM 语言的某些实现，或者开启了优化标志的编译器，都可以把尾递归编译成字节码循环。这样，上面的 factorialTail 在 n 很大时也不会爆栈。
3.3 尾递归优化替代不了迭代的原因
首先，并不是所有递归函数都能改写成尾递归。拿快速排序来说，它有两个递归调用，而且两个调用都必须执行，不是“只有最后一步”。你就算把其中一个递归放到最后，另一个递归仍然占据栈帧，所以它本质上不是尾递归。有一种技巧叫“尾递归快排”，通过手动选择只递归短区间、用循环处理长区间，来把栈深度控制在 logn 级别，但这不是严格的单一尾递归。
其次，很多编程环境根本不支持尾递归优化。JavaScript 虽然规范里提到过尾调用优化，但主流浏览器真正实现的并不多。你写了漂亮尾递归，跑起来照样爆栈。
最后，迭代的控制粒度更细。用循环你可以自由地管理临时变量、提前退出、跳过某些步骤，甚至暂停恢复。递归则受限于函数调用的模型，想中途记录状态或者控制栈上限，往往还要借助自定义栈。
所以我的结论是：尾递归优化是一个好的优化手段，但它既不能拯救所有递归，也不能取代迭代。特别是在“排序”这种需要处理大数据的场景，主动把递归改写成迭代，才是更稳的办法。
四、从栈空间角度比较递归与迭代排序
4.1 快速排序的递归版本栈消耗
递归快排每次调用都会分配固定大小的栈帧。理想情况下，每次划分能把数组对半开，递归深度是 log2(n)。但最坏情况下，递归深度是 n。即使采用随机选轴点，仍存在概率性的深度风险。而且系统栈除了快排自己的帧，还要容纳调用方、其他函数等，所以可用空间更有限。
4.2 迭代快排的栈消耗
迭代快排使用一个显式的数组（或者对象）作为栈。这个栈只保存区间的左右边界，不保存运行时上下文，通常非常轻量。最坏情况下栈里需要保存多少个区间？其实也就是 O(n) 个边界，但每个元素只是两个整数，比完整栈帧小很多。而且这个栈在内存的堆区，不像系统调用栈那样容易被卡死。所以迭代快排在极端情况下不容易爆栈，至少我们能控制它。
4.3 归并排序的递归与迭代
归并排序的递归版本深度很稳定，永远是 log2(n)，因为它总是对半划分。但每一层递归都要等待两个子递归的结果，所以系统栈上同时存在的栈帧数也差不多是 log2(n)。这其实不算危险。可是递归带来的函数调用开销依然存在。而自底向上的迭代归并，完全不用递归，只用两层循环，栈空间几乎为零，只额外使用一个辅助数组。性能更稳定，更适合处理超大规模数据。
下面这段代码演示自底向上的归并排序。它先合并长度为1的小块，再合并长度为2、4、8……直到整个数组有序。
// 技术栈：JavaScript
// 合并两个有序区间：arr[left...mid] 和 arr[mid+1...right]
function merge(arr, left, mid, right) {
const temp = []; // 临时数组，用来存合并结果
let i = left; // 左区间起点
let j = mid + 1; // 右区间起点
// 依次取出较小的数放进 temp
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp.push(arr[i]);
i++;
} else {
temp.push(arr[j]);
j++;
}
}
// 把左边剩下的全放进去
while (i <= mid) {
temp.push(arr[i]);
i++;
}
// 把右边剩下的全放进去
while (j <= right) {
temp.push(arr[j]);
j++;
}
// 把临时数组的内容复制回原数组
for (let k = 0; k < temp.length; k++) {
arr[left + k] = temp[k];
}
}
// 迭代版归并排序：自底向上
function mergeSortIterative(arr) {
const n = arr.length;
let size = 1; // 当前合并区间的半长度
while (size < n) {
for (let left = 0; left < n; left += size * 2) {
const mid = Math.min(left + size - 1, n - 1); // 左区间结束
const right = Math.min(left + size * 2 - 1, n - 1); // 右区间结束
if (mid < right) {
merge(arr, left, mid, right); // 合并两个区间
}
}
size *= 2; // 每次翻倍，直到覆盖全数组
}
}
这个迭代版在栈空间上几乎不消耗递归调用栈，辅助数组也是显式分配的，不会出现“一不注意就栈溢出”的尴尬。
五、递归转迭代的通用方法
既然递归在栈空间上有这些风险，把递归改成迭代就成了一个实用技能。下面分享三个通用套路。
5.1 方法一：用显式栈模拟系统调用
最直接的办法就是自己准备一个栈，把原来递归里需要保存的“参数”和“执行到哪一步”的信息存进去。以快速排序为例，递归需要保存的是左右边界。那么我们在栈里就放区间边界，用 while 循环不停地取出区间、处理区间、再把新的区间压回栈中。
// 技术栈：JavaScript
// 非递归快速排序：使用显式栈
function quickSortIterative(arr) {
const stack = []; // 自定义栈，存放待排序区间
stack.push([0, arr.length - 1]); // 初始区间：整个数组
while (stack.length > 0) {
const [left, right] = stack.pop(); // 取出一个区间
if (left >= right) continue; // 区间内没有元素或只有一个，跳过
const pivotIndex = partition(arr, left, right); // 分区
// 这里注意压栈顺序：因为栈是后进先出
// 先压右区间，再压左区间，这样左区间先被取出处理
if (pivotIndex + 1 < right) {
stack.push([pivotIndex + 1, right]);
}
if (left < pivotIndex - 1) {
stack.push([left, pivotIndex - 1]);
}
}
}
这种方法的优点是能保留原递归的结构，逻辑清晰；缺点是你要手动管理好状态，否则容易漏掉某些区间。
5.2 方法二：把尾递归直接改写成循环
如果递归本身是尾递归，那改起来最简单。把递归调用换成更新循环变量，再用 while 包住函数体即可。比如阶乘：
// 技术栈：JavaScript
// 尾递归改写成循环
function factorialIterative(n) {
let total = 1;
while (n > 1) {
total = total * n; // 相当于 factorialTail(n - 1, n * total)
n--;
}
return total;
}
对于排序算法来说，纯粹的尾递归其实不多。但我们可以把快排改造成“带循环的递归”，也就是手动选择较短的区间递归，较长的区间用循环处理。这种“混合版”也能让栈深度变成 O(log n)。
// 技术栈：JavaScript
// 混合版快速排序：短区间递归，长区间迭代
function quickSortHybrid(arr, left = 0, right = arr.length - 1) {
while (left < right) {
const pivotIndex = partition(arr, left, right);
// 如果左区间比右区间短，就递归左区间，然后迭代右区间
if (pivotIndex - left < right - pivotIndex) {
quickSortHybrid(arr, left, pivotIndex - 1);
left = pivotIndex + 1;
} else {
// 否则递归右区间，然后迭代左区间
quickSortHybrid(arr, pivotIndex + 1, right);
right = pivotIndex - 1;
}
}
}
这种写法仍然有递归调用，但深度受 O(log n) 限制，适合那些不想彻底改成显式栈的场景。严格说它不完全等价于迭代，但可以看作递归向迭代过渡的中间形态。
5.3 方法三：从“处理状态”的角度重新设计
有些递归算法自带一种对应的迭代方案，甚至比模拟递归更高效。归并排序就是一个典型。递归版是从最大区间往下拆，迭代版则直接最小区间往上合并。这就是“自顶向下”与“自底向上”的区别。
自底向上的归并排序不关心递归树，直接按长度 1、2、4、8……不断合并。整个过程不需要栈，只需要一个循环控制“步长”，一个内层循环控制“区间起点”。我们前面写过的 mergeSortIterative 就是这种思路。所以当你觉得模拟栈很麻烦时，不妨退一步想想：这个算法能不能换一种从底向上的构造方式？往往能打开新思路。
六、完整演示：三种排序代码跑起来
下面我们用一个完整的 JavaScript 程序，同时测试前面写的递归快排、迭代快排和迭代归并排序，并输出每次排序的结果。这样你能更直观地看到它们的行为差异。
// 技术栈：JavaScript
// 完整演示：递归快排、迭代快排、迭代归并排序
// ---------- 分区函数（供快排使用） ----------
function partition(arr, left, right) {
const pivot = arr[right];
let i = left;
for (let j = left; j < right; j++) {
if (arr[j] < pivot) {
[arr[i], arr[j]] = [arr[j], arr[i]];
i++;
}
}
[arr[i], arr[right]] = [arr[right], arr[i]];
return i;
}
// ---------- 递归快速排序 ----------
function quickSortRecursive(arr, left = 0, right = arr.length - 1) {
if (left >= right) return;
const pivotIndex = partition(arr, left, right);
quickSortRecursive(arr, left, pivotIndex - 1);
quickSortRecursive(arr, pivotIndex + 1, right);
}
// ---------- 迭代快速排序 ----------
function quickSortIterative(arr) {
const stack = [];
stack.push([0, arr.length - 1]);
while (stack.length > 0) {
const [left, right] = stack.pop();
if (left >= right) continue;
const pivotIndex = partition(arr, left, right);
if (pivotIndex + 1 < right) {
stack.push([pivotIndex + 1, right]);
}
if (left < pivotIndex - 1) {
stack.push([left, pivotIndex - 1]);
}
}
}
// ---------- 合并函数（供归并排序使用） ----------
function merge(arr, left, mid, right) {
const temp = [];
let i = left;
let j = mid + 1;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp.push(arr[i]);
i++;
} else {
temp.push(arr[j]);
j++;
}
}
while (i <= mid) {
temp.push(arr[i]);
i++;
}
while (j <= right) {
temp.push(arr[j]);
j++;
}
for (let k = 0; k < temp.length; k++) {
arr[left + k] = temp[k];
}
}
// ---------- 迭代归并排序 ----------
function mergeSortIterative(arr) {
const n = arr.length;
let size = 1;
while (size < n) {
for (let left = 0; left < n; left += size * 2) {
const mid = Math.min(left + size - 1, n - 1);
const right = Math.min(left + size * 2 - 1, n - 1);
if (mid < right) {
merge(arr, left, mid, right);
}
}
size *= 2;
}
}
// ---------- 测试 ----------
const data1 = [9, 2, 8, 1, 7, 3, 6, 4, 5];
const data2 = [...data1]; // 复制一份，避免互相影响
const data3 = [...data1]; // 再复制一份
quickSortRecursive(data1);
quickSortIterative(data2);
mergeSortIterative(data3);
console.log('递归快排结果：', data1.join(','));
console.log('迭代快排结果：', data2.join(','));
console.log('迭代归并结果：', data3.join(','));
运行这段代码，你会看到三个结果都是 1,2,3,4,5,6,7,8,9。说明不同实现虽然内部机制不一样，最终效果是一致的。
七、应用场景与优缺点对比
7.1 递归排序的应用场景
递归排序适合小规模数据，或者在教学、快速验证算法思想时使用。它的代码可读性高，几乎和算法描述一一对应。如果数据规模不大，比如几千个元素，递归快排完全没问题。很多高级语言也提供了递归排序的库实现，内部会自动优化或限制深度。
7.2 迭代排序的应用场景
迭代排序更适合生产环境，特别是大数据量、内存受限、或对性能稳定性要求高的场景。比如处理几百万条记录的日志文件，或者做嵌入式系统中对栈空间要求苛刻的排序，迭代版本能让我们更精确地预测内存占用。另一个典型场景是流式处理：数据不断进来，希望保持有序。自底向上的归并排序天然适合分块合并，所以迭代版本更实用。
7.3 优缺点对比
递归排序的优点是代码短、逻辑直白、容易组合。缺点是调用栈不可控，极端情况下会爆栈，且函数调用本身的性能开销略大。迭代排序的优点是栈空间可预测，大部分情况下不会爆栈，性能更稳；缺点是代码往往更复杂，状态管理更容易出错。两者并没有绝对的好坏，关键看你的约束条件。如果追求开发效率和可读性，递归优先；如果追求稳定和极限性能，迭代优先。
八、注意事项
第一，使用显式栈模拟递归时，压栈顺序决定处理顺序。如果希望保持和原来递归一致（先处理左区间），就需要先把右区间压进去。不然处理顺序反了，排序结果通常没问题，但某些依赖处理顺序的逻辑会有影响。
第二，迭代归并排序要小心边界计算。特别是数组长度不是 2 的幂时，mid 和 right 要取 min，防止数组越界。计算区间时建议多用变量名，少用魔法数字。
第三，不要以为迭代版就一定比递归版快。递归版在某些场景下因为局部性更好、函数内联优化等，可能反而更快。迭代版的主要优势在于“栈安全”和“可预测性”，而不仅是速度。
第四，如果递归深度可控，完全没必要强行改成迭代。比如平衡树相关的遍历，深度只有 logn，递归写起来更舒服。非递归只是工具，不是目的。
第五，JavaScript 这类语言里，数组的 push/pop 是 O(1) 的，适合用来模拟栈。但要注意，如果频繁创建区间数组 [left, right] 会产生大量垃圾对象。为了更高性能，你可以用两个平行栈分别存 left 和 right，或者用索引存。这里为了可读性用了数组，生产环境可以再优化。
九、文章总结
递归排序和迭代排序本质上是同一种算法思想的两种表达方式。递归写起来爽，但栈空间是我们无法忽视的成本。尾递归优化虽然能缓解部分问题，但并不能完全替代迭代，因为它既不能覆盖所有递归，也不保证每个运行环境都支持。从栈空间角度看，递归排序的最大深度取决于划分情况，而迭代排序通过显式栈或自底向上的循环，把栈消耗控制在更安全的范围内。把递归转成迭代并不神秘，核心就是“自己管理状态”：要么用栈模拟系统调用，要么把尾递归改写成循环，要么换一种自底向上的构造方式。掌握这些方法之后，你遇到类似的问题就不必再怕爆栈了。希望今天的分享能让你在写出正确代码的同时，还能多一份对底层机制的理解。
Comments