递归实现水壶问题遇Recursion Error，但循环迭代多低于5000次

核心差异：递归堆栈帧，循环原地更新 #

递归调用每次都会在Python的调用栈中新建一个栈帧，存储当前函数的参数、临时变量等上下文信息；而while循环始终在同一个栈帧里执行，仅更新amt1、amt2的状态，不会增加栈的深度。

你的问题根源在随机搜索的不确定性：虽然多数情况下几百到几千步就能找到目标，但偶尔会随机触发循环操作（比如反复装满7升壶再倒空，一直卡在(7,0)→(0,0)→(7,0)的循环状态）。此时递归会持续压栈，次数一旦突破你设置的sys.setrecursionlimit(5000)上限，就会触发栈溢出错误；而循环碰到这种情况，只是在原地反复执行，栈深度始终不变，最多多耗些时间直到随机选到正确路径。

代码细节拆解 #

递归实现的隐患 #

你写的random_search函数，每一次递归调用都会在栈中新增一层，哪怕是重复状态也会持续压栈。比如连续随机选中“装满j1”→“倒空j1”，递归深度会飞速上涨，分分钟突破5000的限制。即便设置了递归上限，也架不住某次随机操作一直循环同一个动作。

循环实现的稳定性 #

while循环全程在同一个栈帧内执行，所有状态更新都是原地修改变量，不管迭代多少次，栈深度始终为1，自然不会出现栈溢出问题。

验证一下？ #

给递归代码加个深度计数器，打印每次调用的深度，就能看到某次运行中深度会直接冲过5000：

import random
import sys 
sys.setrecursionlimit(5000)

j1, j2, target = 7, 3, 5
depth = 0

def random_search(amt1, amt2):
    global depth
    depth +=1
    print(f"当前递归深度：{depth}")
    r = random.randint(1,6)

    if amt1 == target:
        amt2 = 0
        print(f"We have reached the target state {(amt1, amt2)}")
        return
    
    if r==1:
        return random_search(0, amt2)
    elif r==2:
        return random_search(amt1, 0)
    elif r==3:
        return random_search(j1, amt2)
    elif r==4:
        return random_search(amt1, j2)
    elif r==5:
        return random_search(amt1 + min(amt2, (j1-amt1)), amt2 - min(amt2, (j1-amt1)))
    elif r==6:
        return random_search(amt1 - min(amt1, (j2-amt2)), amt2 + min(amt1, (j2-amt2)))

random_search(0, 0)

多跑几次就能碰到深度突破5000并触发错误的情况。

非要用递归怎么办？ #

可以加入深度阈值，超过后重置状态重新开始：

import random
import sys 
sys.setrecursionlimit(5000)

j1, j2, target = 7, 3, 5

def random_search(amt1, amt2, depth=0):
    if depth > 4990:  # 留余量避免触发栈上限
        return random_search(0, 0, 0)
    
    r = random.randint(1,6)

    if amt1 == target:
        amt2 = 0
        print(f"We have reached the target state {(amt1, amt2)}")
        return
    
    if r==1:
        return random_search(0, amt2, depth+1)
    elif r==2:
        return random_search(amt1, 0, depth+1)
    elif r==3:
        return random_search(j1, amt2, depth+1)
    elif r==4:
        return random_search(amt1, j2, depth+1)
    elif r==5:
        new_amt1 = amt1 + min(amt2, (j1-amt1))
        new_amt2 = amt2 - min(amt2, (j1-amt1))
        return random_search(new_amt1, new_amt2, depth+1)
    elif r==6:
        new_amt1 = amt1 - min(amt1, (j2-amt2))
        new_amt2 = amt2 + min(amt1, (j2-amt2))
        return random_search(new_amt1, new_amt2, depth+1)

random_search(0, 0)

不过这种方案只是规避问题，本质上还是不如循环稳定。

内容的提问来源于stack exchange，提问作者Sivashankaran S