Hackerrank Game of Two Stacks递归解法报错原因咨询

1. 运行时错误（测试用例8-13）：递归深度超出Python限制 #

Python默认递归深度上限在1000左右。当其中一个栈的元素数量超过这个上限，且所有元素累加和不超过maxSum时，你的递归会沿着单栈方向连续调用上千次，直接触发RecursionError。比如栈A有2000个小元素，你的代码会一直递归调用recur取A的元素，层数远超Python的默认限制，导致运行时崩溃。

2. 超时（测试用例2-3）：无记忆化导致指数级重复计算 #

你的递归没有对已计算过的状态做缓存，大量(a_i, b_i, remaining_maxSum)的状态会被重复计算。比如先取A再取B，和先取B再取A，最终会到达同一个(a_i+1, b_i+1)状态，但你的代码会重复执行两次相同的递归逻辑，时间复杂度直接退化为O(2^n)，当输入规模稍大时必然超时。

额外的逻辑小问题（不影响核心功能，但值得注意） #

你的计数逻辑里，当取完最后一个元素且刚好耗尽maxSum时，会多执行一次res +=1再返回res-1，这个逻辑刚好能得到正确结果，但其实res完全可以用a_i + b_i来替代——因为每取一个元素对应a_i或b_i加1，当前已取元素数量就是a_i + b_i，没必要把res作为递归参数传递，这也能减少缓存状态的维度。

若要修复递归解法的可选方案 #

• 针对递归深度问题：把递归改成迭代（用栈或队列模拟递归过程），彻底避免深度限制；
• 针对超时问题：给递归函数添加记忆化缓存，比如用functools.lru_cache，注意要把列表类型的a、b转换成元组（因为列表不可哈希，无法作为缓存键）。

内容的提问来源于stack exchange，提问作者Ryan Pan