在我的比较中超出了最大递归深度

Question

我目前正在阅读算法导论 (CLRS)。在尝试解决练习 2.3-4 时，即通过递归排序 A[:n-1] 来编写 A 的插入排序。我已经为此编写了一个代码，我将在下面显示我生成随机数列表并尝试对其进行排序的代码，它适用于列表中的特定数量的项目但是当我将它增加到一千个时我得到一个错误，说最大递归深度超过了比较，通过在线检查我注意到有一种方法可以将递归深度增加到某个值，但我不确定这是否是好的做法或者我应该以某种方式改进我的代码。任何帮助，将不胜感激。谢谢

import random
numlist = []
for i in range(1000):
    numlist.append(i)
random.shuffle(numlist)

def rec_ins_sort(L):
    if(len(L) == 1):
        return L
    else:
        step = rec_ins_sort(L[:len(L)-1])
        return insert(L[len(L)-1], step)

def insert(a, inp_list):
    inp_list.append(a)
    i = len(inp_list) - 2
    while(i > 0 and inp_list[i] > a):
        inp_list[i+1] = inp_list[i]
        i -= 1
    inp_list[i+1] = a
    return inp_list

Answer 1

but I am not sure if that is good practice or I should improve my code in some way.

递归线性（或超线性）输入的大小的算法是通常不是一个好主意，除非编程语言支持 尾调用优化 (TCO)（Python 不支持）并且程序是 尾递归。在这种情况下，调用堆栈根本不会增长，因为最后一个调用帧被覆盖了。

例如，

MergeSort 是一种在 O(log n) 中递归的算法，其中 n 输入的大小。因此，调用堆栈不会增长太多：如果列表有 1'073'741'824 个元素，调用堆栈将增长约 30 级深。

用于插入排序。我真的没有看到让它在 O(log n) 中递归的优雅方法，所以你最好根本不要使用递归：你可以在这里简单地使用迭代：

def rec_ins_sort(L):
    iflen(L) < 1:
        return L
    else:
        R = []
        for l in L:
            R = insert(l,R)
        return R

def insert(a, inp_list):
    inp_list.append(a)
    i = len(inp_list) - 2
    while(i > 0 and inp_list[i] > a):
        inp_list[i+1] = inp_list[i]
        i -= 1
    inp_list[i+1] = a
    return inp_list

据说构建新列表等不是很有效，或者使该算法比严格需要的慢。

所以总结一下：你最好不要在 Python 中构造输入大小递归（超）线性的算法。在那种情况下，您最好将其转换为迭代方法。

在我的比较中超出了最大递归深度

Maximum recursion depth exceeded in my comparison

python

algorithm

recursion

insertion-sort