python递归函数深度

Question

这个程序使用插入排序递归地对列表排序。。。 有人能让我理解“isort”是如何递归工作的，以及“insert”是如何在“isort”递归之后运行的，在它完全运行一次之前，isort递归是否被挂起？你知道吗

def insertion(seq):
  isort(seq,len(seq))

def isort(seq,k):
  if k>1:
    isort(seq,k-1)
    insert(seq,k-1)

def insert(seq,k):
  pos=k
  while pos>0 and seq[pos]<seq[pos-1]:
    (seq[pos],seq[pos-1])=(seq[pos-1],seq[pos])
    pos=pos-1   

Answer 1

看看isort(seq, k)

该函数确保对最后k个元素进行排序

def isort(seq,k):
  if k>1:
    isort(seq,k-1)  
    // seq[k-1:] is sorted

    insert(seq,k-1)
    // the k'th item is now inserted in the correct place,
    // so seq[k:] is sorted

对于k=len(seq)，seq[k:]的排序很简单（这是一个空列表） 在每一步中，递归将k减少1，将seq从尾部排序到头部