1. 需求拆解从“100个不重复随机编号”说起之前在做一个抽奖模拟类项目X时遇到过这样一个需求从1到200的编号范围里随机抽出100个不重复的整数按生成顺序排成一排每个编号对应一个参与对象。当时某导师加了一条约束不能用Set、不能用哈希表、不能用现成的乱序工具只能基于数组和递归来实现。看上去很基础的题目真动手写才发现“随机”和“不重复”两个词放在一起并不是“随机后再去重”那么简单递归的写法更是藏着不少细节。这题的本质其实可以概括成一句话从200个整数中不放回地抽取100个得到一个长度为100的数组。注意这里有两个要求必须同时满足第一每个编号必须在1到200之间且包含两端第二100个编号彼此不能重复。前者考验对取值范围的处理后者考验去重逻辑。很多人一上来会想“先随机生成100个数再把重复的丢掉”但这样会导致最终数量不够100个还得循环补抽逻辑反而绕。生活化地理解这个需求就像你面前有200张写有数字的卡片你现在要闭着眼睛抽出100张每抽一张就把它放到一边如果抽到已经放在一边的卡片就把它放回去重新抽直到抽满100张为止。这个过程天然分成“抽卡-检查-决定收下还是重抽”三个动作而“纯数组递归”就是这三个动作最直接的代码映射。我打算在这篇文章里把这条递归解法彻底拆开先对比为什么选它再逐行解析代码然后算一算它到底要递归多少次最后把常见翻车现场都列出来。无论你是初学者还是写业务代码的开发者都能从里面拿到一点可复用的东西。1.1 范围与边界1-200的闭区间怎么表达随机数生成的第一个坑就是边界。Math.random()返回的是[0,1)区间的小数要映射到1到200的整数标准公式是const candidate Math.floor(Math.random() * 200) 1;这里Math.random() * 200会得到[0,200)的小数向下取整后得到0到199的整数再加1就得到1到200。为什么不能直接用Math.ceil(Math.random() * 200)因为Math.random()理论上可以返回0Math.ceil(0)得到0这时候编号就变成0了超出范围。这类边界错误在测试时很难发现因为概率极低但一旦出现就是数据污染。1.2 为什么“纯数组递归”值得单独写一篇如果只求结果三行Set写法就结束了。但“纯数组递归”的限制恰恰逼着你走一条更本质的路数组负责存储结果和完成线性查重递归负责表达“当前位置不满意就重新来”的控制流。这个写法在数据量不大的时候完全可用而且能把回溯思想的最小模型展示出来。等后面遇到N皇后、迷宫寻路这种真正的回溯题你会发现它们的核心骨架和这道题一模一样。2. 方案选型不重复随机数的几种常见写法在写递归版之前先把市面上常见的解法过一遍。不是为了凑篇幅而是为了让你理解为什么这个场景下递归数组有其存在的理由也方便你在面试或工程里做取舍。2.1 五种写法横向对比方案核心思路期望时间复杂度空间复杂度代码量适用场景Set while循环利用Set天然去重O(n)O(n)3行最快的业务实现标记数组boolean数组记录已用编号O(n)O(max)5行固定范围、数量中等Fisher-Yates洗牌构造全序列后打乱取前n个O(max)O(max)6行range与count接近时最优纯数组 while循环includes查重后pushO(n²) 期望O(n)5行教学演示小规模纯数组 递归includes查重 递归重试O(n²) 期望O(n) 栈深度6行本文主角思维训练先说Set方案它确实最实用。while (set.size 100) set.add(...)三行搞定靠的就是哈希表O(1)查重。但它需要一个额外的数据结构如果题目明确说只能用数组就不能用。标记数组方案是把1到200的每个编号是否被占用记录在一个长度201的bool数组里。查重变成了used[candidate] false的判断时间复杂度从O(n)降到O(1)。这个方案的缺点是额外空间和范围绑定如果范围是几百万bool数组也得几百万。Fisher-Yates洗牌是另一条路线先把1到200按顺序放到数组里然后从后往前依次和随机位置交换之后取前100个。它不依赖查重而是通过“打乱后取一部分”来保证不重复适合那种range和count几乎相等的情况。而纯数组递归本质上是“Set方案”的数组版查重靠includes线性扫描重试靠递归调用自身。2.2 为什么我最后还是选了递归版从工程角度看生产代码我大概率不会用递归版但作为题目解法和教学案例它的优势在于“意图清晰”。它把“对当前位置生成的编号不满意需要重新生成”这件事用一次自我调用来表达。循环版虽然也能写但递归版的函数调用栈天然携带“当前处理到第几个人”的上下文让代码读起来像在描述一个过程而不是在描述一个计数器。不用标记数组的原因是题目限定了“纯数组”这里的“纯”在我理解里就是只用普通数组存结果不额外开bool数组、不用Set也就是把查重压力全部交给数组本身。这虽然笨但正好能展示查重过程的成本。还有一个实际原因100个编号从200个里抽数量只有一半重复碰撞不算严重递归重试的总次数不会很高。这一点很多人会误判以为越到后面越难抽实际算下来你会发现平均比想象中少得多。后面我会专门列一节的推导。2.3 递归在这里解决的是“重试”问题递归版的核心控制流是生成候选编号→检查是否在已有数组中→如果在递归调用自己如果不在写入数组后递归处理下一个下标。这里的“递归调用自己”不是处理下一个元素而是“在当前下标再来一次”。这和回溯算法里的“失败则重新选择”是同一个动作只不过本题在失败时没有留下任何副作用所以不需要撤销是最简化的重试模型。很多人第一次看会奇怪为什么重复时不能直接index 1因为那样等于跳过了当前位置数组最终会少一个元素。还有人会把push写在判断外面导致重复值也被写进去。这些都是没理解“重试”语义造成的。3. 核心实现纯数组递归的代码逐行拆解3.1 基础版本一段能直接运行的JavaScript代码先给出完整代码再用小段说明解释每一行const records []; function generate(index) { // 递归出口100个编号全部生成完毕 if (index 100) return; // 生成 1-200 之间的候选编号 const candidate Math.floor(Math.random() * 200) 1; // 查重如果已有数组里已经存在这个编号重新生成 if (records.includes(candidate)) { generate(index); } else { // 不重复写入结果继续生成下一个编号 records.push(candidate); generate(index 1); } } generate(0);逐行拆开看第一行const records []是结果数组最终长度应该是100。generate(index)里的index表示当前要为第几个位置生成编号从0开始。递归出口写成index 100意思是一共需要100个编号当下标走到100时说明前0到99的位置都填好了。如果错误写成index 99最后会少一个。候选编号生成那行用到了前面说的闭区间公式。查重用records.includes(candidate)这是对数组做一次线性扫描复杂度O(n)。当records里已经存在这个编号就调用generate(index)注意下标没有变化这就是“重试当前位置”。当records里不存在就把候选编号push进结果然后调用generate(index 1)处理下一个人。整个流程走到最后records里会按生成顺序保存100个不重复的编号直接作为“一排”的结果输出。如果你还想要这排人“依次站好”的顺序生成顺序本身就是顺序不用额外排序。3.2 函数式改法把“生成不重复编号”和“构建队列”拆开基础版把所有状态都放在外部数组里代码简短但有一个隐患如果同一个页面里多次调用generate(0)records不会自动清空第二次调用结果就不对。更干净的做法是把数组作为参数层层传递同时把“挑一个不重复编号”单独抽成一个递归函数function pickUnique(existing) { const candidate Math.floor(Math.random() * 200) 1; return existing.includes(candidate) ? pickUnique(existing) : candidate; } function buildLine(index, existing) { if (index 100) return existing; const uniqueId pickUnique(existing); existing.push(uniqueId); return buildLine(index 1, existing); } const line buildLine(0, []);pickUnique内部做了完整的“生成-查重-重试”如果重复就递归调用自己直到拿到一个不重复编号。buildLine只负责控制长度和顺序拿一个编号、放进数组、处理下一个位置。这个拆分的好处是每个函数职责单一你甚至可以单独测pickUnique。如果连返回值也想保持纯函数风格可以把buildLine改成不修改原数组而是返回新数组但那样每次都要复制数据量大会多耗内存这里就不推荐了。保持push的写法在100这个规模下既清晰又高效。3.3 期望调用次数推导为什么它比想象中快得多现在来回答很多人的疑问这个递归到底要执行多少次会不会性能很差假设当前已经生成了i个不重复编号i从0到99接下来要生成第i1个。编号空间是1到200所以随机抽一个数抽到“从未出现过”的概率是p(i) (200 - i) / 200抽到“已经出现过”的概率就是i / 200。再次抽到新编号所需的尝试次数服从几何分布期望是E(i) 1 / p(i) 200 / (200 - i)于是整个流程的期望尝试总次数是E_total sum_{i0}^{99} 200 / (200 - i) 200 * (1/200 1/199 ... 1/101) 200 * (H_200 - H_100) ≈ 200 * (5.878 - 5.187) ≈ 138也就是说生成100个不重复编号平均只需要约138次随机尝试平均每个编号只需要1.38次。最后一个是第100个此时已占用99个编号剩余可选是101个成功概率还有101/200≈50.5%平均只尝试不到2次。这个结果和很多人的直觉不同以为抽到后面会非常难实际上因为只取200个里的一半最难的阶段也就平均2次尝试。真正困难的是把200个数全部抽满那时最后一个编号的期望尝试次数是200次。3.4 栈深风险分析极端参数下递归会不会爆代码里的重试是“同一个下标再一次调用自己”连续失败多少次调用栈就多叠多少层。正常100/200的参数下没问题连续失败20次的概率大约是(99/200)^20已经是个极小的小数。但如果你把需求改成“从200个数里抽出199个”情况就不同了最后一个编号的成功概率只有1/200期望尝试次数是200次连续失败几百次的概率也不低递归栈深度可能到几百甚至上千层。JavaScript引擎一般能承受几千到上万层递归所以100/200的题目怎么跑都安全。但如果你把这个函数直接套到count10000, max10000的场景最后一个编号连续失败上万次是很有可能的递归栈可能说爆就爆。这是递归写法最需要注意的边界。4. 实操验证跑起来看结果顺便统计调用次数4.1 正确性验证三件套代码写完先别急着用要做三个基本检查长度检查line.length 100范围检查每个元素都满足n 1 n 200重复检查new Set(line).size 100这三个条件通过结果才算基本正确。如果是在面试现场建议把这三个断言当场跑一遍比口头说“肯定没问题”有说服力得多。4.2 调用次数统计理论和实测对照在递归函数开头加一行计数器就能统计实际的随机尝试次数let attempts 0; function generate(index) { attempts; if (index 100) return; const candidate Math.floor(Math.random() * 200) 1; if (records.includes(candidate)) { generate(index); } else { records.push(candidate); generate(index 1); } }跑上一百轮把attempts均值打出来你会发现它非常接近138这个理论值波动区间大概在120到160之间。注意每轮结束后要把records和attempts重置成初始值再跑下一轮不然结果会互相污染。这种“理论推导实测对照”的习惯很值得保留它能让你的代码不再是“跑起来看着对”而是“每一步都有据可依”。4.3 扩展实验把参数推到极端看看退化趋势用同一个期望公式可以直观地看到不同参数的退化情况场景参数期望尝试总次数抽取四分之一count50, max200约57抽取一半count100, max200约138抽取四分之三count150, max200约276几乎抽满count190, max200约590全部抽满count200, max200约1176注意看最后一行同样是递归从200个里抽满200个的期望尝试次数是1176比100/200的138多了一个数量级最后几个编号每次成功概率极低递归重试会非常频繁。所以“纯数组递归”的适用边界就是count明显小于max。当count逼近max时换成Fisher-Yates洗牌才是正确选择。5. 踩坑实录这些错误写法我全都见过5.1 边界写错0-199和1-200完全不是一回事最常见的是把生成式写成Math.floor(Math.random() * 200)这样生成的是0到199范围下边界错了1。还有一种写法是Math.ceil(Math.random() * 200)前面说过Math.random()可能返回0所以罕见情况下会出现0号。要保证闭区间1到200最稳妥的就是Math.floor(Math.random() * 200) 1这也是所有语言里随机整数的通用模式。5.2 递归出口和分支顺序搞反两个典型错误// 错误一出口差一个 if (index 99) return; // 只生成99个 // 错误二重复时推进下标导致少元素 if (records.includes(candidate)) { generate(index 1); // 跳过当前编号 }第一种错误会让结果数组少一个元素。第二种错误更隐蔽从期望上看最终可能因为跳过了某些位置而多尝试几次但数组长度一定不对。判断分支的核心原则是重复时下标不动不重复时下标加一push只在确认不重复后执行。5.3 全局数组被反复使用基础版代码把records定义在函数外部如果同一脚本里执行两次generate(0)第二次运行时records已经非空结果长度和内容都会错。解决办法有三种每次调用前重置数组、把数组作为参数传入、或者把整个生成逻辑封装成一个函数内部声明数组function createLine() { const records []; function generate(index) { if (index 100) return; const candidate Math.floor(Math.random() * 200) 1; if (records.includes(candidate)) { generate(index); } else { records.push(candidate); generate(index 1); } } generate(0); return records; }这个封装版既保留了递归写法又避免了全局污染是我在演示时最推荐的版本。5.4 大参数下递归栈溢出工程里改用while更稳我曾经把这段逻辑扩展到一个模拟数据生成场景要生成8000个不重复编号范围也是8000。开始时直接套用递归版结果运行到后半段栈溢出了。原因就是末尾几个编号的成功概率极低连续失败造成递归深度过大。如果只想保留“数组重试”的思路又不希望有栈压力可以把重试模型改成等价循环function createLine(count, max) { const records []; while (records.length count) { const candidate Math.floor(Math.random() * max) 1; if (!records.includes(candidate)) { records.push(candidate); } } return records; }这个版本在100/200的场景和递归版行为完全一致但没有递归深度问题。我的建议是用来学习和面试讲思路时用递归版写进生产环境或数据规模不可控时用while版或者换Set/标记数组。6. 从这道题出发递归思维的真实应用场景6.1 不重复随机数的真实落地这类需求在业务里很常见。抽奖系统要生成一批不重复的中奖编号考试系统要给每个考生随机分配不重复的座位号游戏运营活动要发一批不重复的礼包码。它们本质上都是“从某个范围内不放回地抽取若干个编号”的变体只是规模可能不同。如果范围小、数量少递归版完全没有问题如果数量大换成洗牌或Set方案即可。6.2 同一思路的进阶题从“重试”到“回溯”这道题里递归解决的是“当前位置不满意就重新生成”因为没有副作用所以不需要撤销。而N皇后、迷宫寻路这类经典回溯题不仅要在当前位置尝试还要在整条路径都走不通时“撤销上一次的选择”再换一个分支尝试。换句话说这道题是最简单的回溯雏形理解了“递归调用自己处理同一位置”的动作后面看回溯代码就不会觉得陌生。拿N皇后举例在某一行放一个皇后后如果和前面的皇后冲突就要把这个皇后拿走换下一列继续试如果当前行所有列都不行就要回到上一行重新放。这和“生成编号重复就重试”在思维上是同一个链条只是多了“撤销”这一步。6.3 面试时怎么讲出亮点如果面试遇到这道题我建议这样答先给出递归版展示能跑通的代码然后主动算期望次数说出H_200减H_100的推导过程接着指出递归版的两个潜在问题includes的O(n)查重和极端参数下的栈深最后给出优化方向比如标记数组、洗牌算法或Set。全程不需要背标准答案只要把“从候选空间里不放回抽取”这个模型讲清楚问题基本就拿下了。我个人现在写业务代码很少直接写这种递归去重但那次被要求用纯数组递归实现后我对“随机不重复”的理解就深了一截。以后你看到别人三行Set解决同一个需求不用觉得递归版多余每种写法背后都有它适用的上下文。如果哪天你手头也有一个类似的“随机不重复编号”需求建议先判断count和max的比例再决定用哪一套代码别让一个看似简单的需求在数据量变大后悄悄翻车。