我該如何重寫這種遞歸方法？

這是一個簡單的程序，用於計算列表中元素數大於或等於x且小於y的元素數。我該如何重寫這種遞歸方法？

def NumRange(a,x,y): 
    count = 0 
    for num in a: 
     if(num>=x and num<=y): 
      count+=1 
    return count 

NumRange([1,3,5,7,9,11],3,9) 
# => 4

如何重寫這個方法是遞歸的？我知道我可能需要在此方法中添加一個參數，但我不知道該怎麼做。

來源

2016-12-04 Justin

你使用的是Python 2還是Python 3？ –

這不是一個遞歸的好例子。 – Maroun

@EliSadoff Python 2 – Justin

-1

def NumRange(a, x, y): 
    if not a: 
     return 0 
    if a[0] >= x and a[0] <= y: 
     return 1 + NumRange(a[1:], x, y) 
    return NumRange(a[1:], x, y)

首先您需要定義邊緣條件：如果列表爲空，則返回0。如果條件不滿足，則通過遞歸調用函數繼續測試其他候選項。因此，如果滿足，則返回非零的東西。您將a[1:]傳遞給列表的「尾部」（列表中沒有第一個元素）。

來源

2016-12-04 16:27:38 ForceBru

這是遞歸一個偉大的候選人，在Python 2，你可以做這樣的

def NumRange(a, x, y): 
    hd, tl = a[0], a[1:] 
    if tl == []: 
     return 1 if hd >= x and hd <= y else 0 
    else: 
     return (1 if hd >= x and hd <= y else 0) + NumRange(tl, x, y)

這是尾遞歸的爲好。

來源

2016-12-04 16:29:30

這實際上是*非常*不適合遞歸。 – Maroun

@MarounMaroun這是如何遞歸的不好的候選人？列表明智的操作適用於遞歸，特別是如果它在功能上完成。 –

切片會創建新的列表，因此您的實現需要耗盡內存，因爲它會爲每個遞歸級別創建一個新列表。就目前來看，這個實現的內存複雜度爲n^2，而在問題的迭代情況下則爲n。 – Dunes

>>> def NumRangeRec(a,x,y): 
...  if not a: 
...   return 0 
...  elif a[0] >= x and a[0] <= y: 
...   return 1 + NumRangeRec(a[1:],x,y) 
...  else: 
...   return NumRangeRec(a[1:],x,y) 
... 
>>> NumRangeRec([1,3,5,7,9,11],3,9) 
4

來源

2016-12-04 16:33:51

你可以這樣說：

def NumRangeRec(a,x,y): 
    if not a: # checks if the list is empty 
     return 0 
    incr = int(x <= a[0] and a[0] <= y) # acts as the increment 
    return NumRangeRec(a[1:], x, y) + incr # pass the tail of the list to the recursive call

這裏，根據條件的結果增量（incr）設置爲0或1。您可以使用int(some boolean)將布爾結果轉換爲0或1。

（從技術上講，因爲TRUE和FALSE是1和0在Python你不一定需要這個。但是，在Python 2 True和False可以因此使用int(..)讓您在安全方面進行重新分配。）

來源

2016-12-04 16:34:21 Keiwan

一個可能的解決方案：

def NumRange(a, x, y): 
    # Base case 
    if not a: 
     return 0 

    if x <= a[0] <= y: 
     return 1 + NumRange(a[1:], x, y) 
    else: 
     return NumRange(a[1:], x, y)

來源

2016-12-04 16:36:02

你應該考慮使用的蓄電池爲tail call優化。在下面，你可以看到@ Keiwan的答案使用了一些很好的功能，比如解構分配。

def NumRange(a,x,y): 
    def rec (a, acc) : 
    if not a: # base case - if the list if empty return the accumulated result 
     return acc 

    head, tail = a[0], a[1:] # destructure list to the first item and all the rest 

    incr = int(x <= head and head <= y) # acts as the increment 
    return rec(tail, acc + incr) # recursively process rest of the list 

    return rec(a, 0) # pass the list and an empty accumulator to the implementation

來源

2016-12-04 17:23:35

如上所述，由於切片清單會創建一個新的副本。所有上述方法都是飢餓的記憶。

下面是一個使用一個索引參數而不切片列表

def NumRange(a,x,y,ix=0): 
    if ix == len(a): 
     return 0 

    return (a[ix]>=x and a[ix]<=y) + NumRange(a, x,y, ix+1)

來源

2016-12-08 02:43:16 yuval

這裏是另一個變型中，在一個單一的線上的存儲效率和簡潔的解決方案。它依賴python的conditional evaluation order

def NumRange(a,x,y,ix=0): 
    return (ix != len(a)) and ((x<= a[ix] <=y) + NumRange(a, x,y, ix+1))

來源

2016-12-08 02:59:32 yuval

我該如何重寫這種遞歸方法？

回答

相關問題