這個代碼是否使用遞歸？（快速排序）

Question

即時通訊不熟悉遞歸的概念，我不知道這些代碼是否遞歸或使用遞歸。

def quickSort(alist): 
    quickSortHelper(alist,0,len(alist)-1) 

def quickSortHelper(alist,first,last): 
    if first<last: 

     splitpoint = partition(alist,first,last) 

     quickSortHelper(alist,first,splitpoint-1) 
     quickSortHelper(alist,splitpoint+1,last) 


def partition(alist,first,last): 
    pivotvalue = alist[first] 

    leftmark = first+1 
    rightmark = last 

    done = False 
    while not done: 

     while leftmark <= rightmark and \ 
       alist[leftmark] <= pivotvalue: 
      leftmark = leftmark + 1 

     while alist[rightmark] >= pivotvalue and \ 
       rightmark >= leftmark: 
      rightmark = rightmark -1 

     if rightmark < leftmark: 
      done = True 
     else: 
      temp = alist[leftmark] 
      alist[leftmark] = alist[rightmark] 
      alist[rightmark] = temp 

    temp = alist[first] 
    alist[first] = alist[rightmark] 
    alist[rightmark] = temp 


    return rightmark 

如果包含它，指出它在哪裏會非常有幫助。

Answer 1

遞歸函數的定義是在自身內部自我調用的函數。

此外，這是否在你的代碼的唯一功能是第二個：

def quickSortHelper(alist,first,last): 
    if first<last: 

     splitpoint = partition(alist,first,last) 

     quickSortHelper(alist,first,splitpoint-1) # Calls itself here 
     quickSortHelper(alist,splitpoint+1,last) # and here 

所以，第二個功能是recursive;另外兩個不是。

---

注意：@Sean在下面的評論中說過，我給出的遞歸定義是一個非常簡化的定義。還有其他的代碼結構（例如兩個或多個方法交替地調用另一個）可以分類爲使用遞歸。有關遞歸的完整概述，請參閱上面給出的鏈接。