これは、要素がxより大きいか等しい場合にリスト内の要素の数を数えるための簡単なプログラムです。このメソッドを再帰的に書き換えるにはどうすればよいですか？
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
再帰的にこのメソッドを書き換えるにはどうすればよいですか？私は、この方法でもう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を返します。条件が満たされない場合、関数を再帰的に呼び出すことによって他の候補のテストを続行します。したがって、がであれば、0以外の何かを返します。 a[1:]とリストの最初の要素がないリストの 'tail'を渡します。
これは、あなたがこの
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)
これは、同様にテール再帰的であるようにそれを行うことができますPythonの2で、再帰のための偉大な候補です。
>>> 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
あなたはこのようにそれを行うことができます。
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あなたは、必ずしもこれを必要としないPythonで1と0からである。しかし、Pythonの2にTrueとFalseがint(..)が安全側にあなたを置く使っので再割り当てすることができます。）
可能な解決策：
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)
あなたは、アキュムレータを使用して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
上記のように、リストをスライスすると新しいコピーが作成されるため、上記の方法はすべてメモリが空いています。ここ
ここリスト
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)
をスライスせずにインデックス引数を使用してメモリ効率的かつ簡潔な解決策は、別の変異体は、単一のラインです。それは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))
Python 2またはPython 3を使用していますか？ –
これは再帰の良い例ではありません。 – Maroun
@EliSadoff Python 2 – Justin