写程序时，排序几乎是绕不开的坎。不管是整理一堆学生的成绩，还是优化电商网站的商品展示顺序，背后都少不了排序算法的身影。但很多人只记得冒泡、快排这些名字，却没细想过——同一个排序，为什么会有递归和非递归两种写法？它们到底差在哪儿？
递归：像剥洋葱一样一层层来
递归排序，最典型的例子就是快速排序。它的思路很自然：挑一个基准值，把数组分成两半，左边小、右边大，然后对左右两部分继续做同样的事。这个“继续做同样的事”，其实就是函数调用自己。
比如下面这个简化的快排递归实现：
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pivot = partition(arr, low, high);
quickSort(arr, low, pivot - 1);
quickSort(arr, pivot + 1, high);
}
}每次调用自己，系统都会在栈上保存当前的状态。这就像你一边切洋葱，一边把每层皮编号记下来，等内层处理完再按顺序回溯。逻辑清晰，代码也短，写起来顺手。
非递归：自己动手管理“记忆”
可问题来了，如果递归太深，比如要排一万个数，函数调用栈可能撑爆，程序直接崩溃。这时候就得换非递归写法。
非递归的核心是：不用函数自己调自己，而是用数据结构（通常是栈）手动模拟调用过程。相当于你不靠大脑记洋葱剥到第几层了，而是拿个小本子记下每一层的起止位置，处理完就翻本子看下一层。
还是快排，改成非递归后长这样：
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int low, high;
} Range;
void quickSortIterative(int arr[], int low, int high) {
Range* stack = (Range*)malloc(sizeof(Range) * (high - low + 1));
int top = -1;
stack[++top] = (Range){low, high};
while (top >= 0) {
low = stack[top].low;
high = stack[top--].high;
if (low < high) {
int pivot = partition(arr, low, high);
stack[++top] = (Range){low, pivot - 1};
stack[++top] = (Range){pivot + 1, high};
}
}
free(stack);
}看起来啰嗦点，但好处是栈空间你自己控制，不怕系统限制。尤其在嵌入式设备或老系统上跑程序，这种写法更稳当。
实际选择：别光看理论
理论上递归写法简洁，适合教学；非递归更可控，适合生产。但现实中还得看语言和场景。
比如 Python，默认递归深度只有几百层，排个大数组直接报错。而 C/C++ 虽然能调栈大小，但在服务器上批量处理数据时，谁也不敢保证不会突然来个极端情况。
反过来，有些排序天生就适合非递归。堆排序就是典型——它基于数组下标操作，压根不需要递归。归并排序也可以写成从下往上的非递归版本，先两两合并，再四四合并，像搭积木一样往上垒。
你在写代码时，不妨先写个递归版理清思路，确认逻辑没问题后，再考虑是否需要改成非递归。尤其是上线到服务端的模块，稳定性比代码长短重要得多。
说到底，递归和非递归不是谁替代谁，而是不同场合下的不同选择。就像炒菜可以用燃气灶也能用电磁炉，关键是你得知道什么时候该开大火，什么时候得控温慢炖。