Python递归实现冒泡排序报maximum recursion depth exceeded错误原因求解
报错触发原因
- 递归终止条件永远无法满足:
count变量被定义在函数内部,每次递归调用bubble_sort时都会被重新初始化为0,即使当前调用中执行了count += 1,下次递归时count值还是会被重置为0,因此count == len(l)-1的判断永远不会成立,函数会无限递归,超过Python默认的最大递归深度限制后就会抛出该报错。 - 现有逻辑存在冗余计算:每一轮冒泡排序后,最大的未排序元素已经被移动到对应末尾位置,不需要在下一轮遍历中再参与比较,原代码每轮都遍历整个数组长度减1的范围,存在不必要的计算。
修复方案
方案1:将计数作为参数传入递归函数
把count作为可选参数放在函数定义中,默认值为0,每次递归调用时传入累加后的值,保证终止条件可以正常触发,同时优化遍历范围减少冗余计算:
def bubble_sort(l, count=0): if count == len(l)-1: print(l) return # 每轮跳过末尾已经排好序的count个元素 for j in range(0, len(l) - 1 - count): if l[j] > l[j + 1]: l[j], l[j + 1] = l[j + 1], l[j] bubble_sort(l, count + 1)
测试调用:
l = [5, 3, 8, 6, 7, 2] bubble_sort(l) # 输出:[2, 3, 5, 6, 7, 8]
方案2:用交换状态判断终止(效率更高)
不需要计数变量,每轮遍历后判断是否发生过元素交换,如果没有发生交换说明数组已经完全有序,直接终止递归即可:
def bubble_sort(l): swapped = False for j in range(0, len(l) - 1): if l[j] > l[j + 1]: l[j], l[j + 1] = l[j + 1], l[j] swapped = True # 无交换说明已排序完成 if not swapped: print(l) return bubble_sort(l)
内容的提问来源于stack exchange,提问作者Mohit Chauhan
相关产品推荐
相关产品推荐

