計算一個數字的出現次數在列表中使用遞歸

鑑於int數組，計算遞歸的次數，值11只出現在陣列中的數量。我們將使用只考慮從給定索引開始的數組部分的約定。這樣，遞歸調用可以傳遞索引+1來向下移動數組。

我需要遞歸做到這一點。我在這方面頗爲新穎，但我在技術上使其發揮作用。我有以下幾點：

def array11(arr, index, cnt=0, num=0): 
    if(cnt==len(arr)-index): 
     print("yay!!! number 11 appears %d times"%num) 
     return 
    elif(arr[index:][cnt]==11): 
     num+=1 
     cnt+=1 
     array11(arr,index,cnt,num) 
    else: 
     cnt+=1 
     array11(arr,index,cnt,num)

但我覺得我這樣做是出於某種原因加上了「CNT」和「民」使用默認值參數一種廉價的方式。我只是不知道如何通過沒有計數器的「arr」數組！

所以這個東西可以接受嗎？你會以同樣的方式做到嗎？

由於事先

來源

2014-07-11 RRR

這幾乎肯定是基於觀點的，因爲它是有效的代碼，可能更適合代碼評審。也就是說，數組不是遞歸數據類型（與單向鏈表相對），所以這看起來像是一個非常自然的解決方案，給定數據類型。另外，它是尾遞歸的，所以它可以編譯成循環，這很好。 –

+1在提問前進行嘗試。我編輯了你的頭銜以反映手頭的問題。 – timgeb

沒問題，謝謝輸入Joshua – RRR

你通常回報的總數：

def array11(arr, index): 
    if index == len(arr): 
     return 0 
    return (arr[index] == 11) + array11(arr, index + 1)

我使用這裏一點Python的把戲，bool是int和True一個子類是等於1。這樣，加起來布爾值（或布爾值和整數）會導致布爾值被解釋爲整數。

然後，您可以使用print，然後返回array11()的最外層呼叫。

來源

2014-07-11 17:06:16

但OP的尾遞歸：| –

那另外不鏈？ array11（[11,2,3]，0）'會產生1 + array11（[11,2,3]，1）' - >'1 + 0 + array11（[11,2,3]，2 ）' - >'1 + 0 + 0 + array11（[11,2,3]，3）' - >'1 + 0 + 0 + 0' ='1'對不對？ –

+1但你可能想扔括號在你的布爾表達式存在，使你做 – scohe001

這是完全可以接受的，儘管不進行尾遞歸的乾淨方式。你正在做的是使用累加器來跟蹤你的計數，這允許你有尾遞歸（更有效的遞歸類型）。但是，正如BlackVegetable指出的那樣，Python不允許您獲得尾遞歸的好處，但是理解使用累加器與自頂向下方法之間的區別，正如Martijn Pieter的回答中所顯示的那樣，肯定值得注意。

來源

2014-07-11 17:05:41

使用累加器不是特別*不潔*;可能更乾淨的是調用像array11（arr，index，cnt + 1，num + 1）'而不是修改cnt和num，然後進行調用。 –

@JoshuaTaylor當然，意味着更多的代碼本身。他可以使用不同的累加器。現在你對OP問題的評論確實是對的:) –

尾遞歸調用在Python IIRC中沒有優化。 – BlackVegetable

在Python 3也可以是因爲這是簡潔：

arr = [11, 0, 4, 7, 2, 11, 6, 11, 12] 

def count11(arr): 
    if not arr: 
     return 0 
    first, *rest = arr 
    return (1 if first == 11 else 0) + count11(rest) 

count11(arr) # 3

列表切片可能不是很有效，但是因爲我們在Python談論遞歸，在假定的表現是不是一個因素。

來源

2014-07-11 17:30:22

計算一個數字的出現次數在列表中使用遞歸

回答

相關問題