再帰関数を数えるには？

Question

以下のコードはPythonのquicksortです。 アルゴリズムで比較演算が何回実行されたのかを数えます。

私はcount = 0を割り当てますが、再帰のため0にリセットされます。

def QuickSort(lst): 
    if len(lst) > 1: 
     pivot_idx = len(lst) // 2 
     smaller_nums, larger_nums = [], [] 

     for idx, num in enumerate(lst): 
      if idx != pivot_idx: 
       if num < lst[pivot_idx]: 
        smaller_nums.append(num) 

       else: 
        larger_nums.append(num) 

     QuickSort(smaller_nums) 
     QuickSort(larger_nums) 
     lst[:] = smaller_nums + [lst[pivot_idx]] + larger_nums 

    return lst 

Answer 1

パスを：、私はそれが間違っていたと思ったので、

def QuickSort(lst, count=0): 
    if len(lst) > 1: 
     pivot_idx = len(lst) // 2 
     smaller_nums, larger_nums = [], [] 

     for idx, num in enumerate(lst): 
      if idx != pivot_idx: 
       if num < lst[pivot_idx]: 
        smaller_nums.append(num) 

       else: 
        larger_nums.append(num) 

     count = QuickSort(smaller_nums, count+1)[1] 
     count = QuickSort(larger_nums, count+1)[1] 
     lst[:] = smaller_nums + [lst[pivot_idx]] + larger_nums 


    return (lst,count) 

Answer 2

グローバル変数としてカウントを割り当て、ゼロに設定します。つまり、関数の定義外にcount=0を設定し、比較するたびにインクリメントします。パラメータとして再帰的

Answer 3

編集は、私はこの答えを消去しましたが、私は示唆したように、それはすべての

後に正しかったと思います関数がステートレスであれば、より良いと思う： あなたは1番目と呼び出し回数を返すことができる：

def QuickSort(lst, ncalls=0): 
    ncalls += 1 

    if len(lst) > 1: 
    pivot_idx = len(lst) // 2 
    smaller_nums, larger_nums = [], [] 

    for idx, num in enumerate(lst): 
     if idx != pivot_idx: 
      if num < lst[pivot_idx]: 
       smaller_nums.append(num) 

      else: 
       larger_nums.append(num) 
    lst1, ncalls = QuickSort(smaller_nums, ncalls) 
    lst1, ncalls = QuickSort(larger_nums, ncalls) 
    lst[:] = smaller_nums + [lst[pivot_idx]] + larger_nums 



    return lst,ncalls 


QuickSort([1,3,52,4,6,5]) 
=> [1, 3, 4, 5, 6, 52],7