Pythonで再帰を使用してリストを逆にするにはどうすればよいですか？
https://stackoverflow.com/questions/216119
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
指定されたリストの逆を返す関数が必要です-再帰を使用します。どうすればいいですか？
解決
リストの最初の要素を逆サブリストに追加します：
mylist = [1, 2, 3, 4, 5]
backwards = lambda l: (backwards (l[1:]) + l[:1] if l else [])
print backwards (mylist)
他のヒント
もう少し明示的に：
def rev(l):
if len(l) == 0: return []
return [l[-1]] + rev(l[:-1])
これは次のようになります：
def rev(l):
if not l: return []
return [l[-1]] + rev(l[:-1])
次のようになります：
def rev(l):
return [l[-1]] + rev(l[:-1]) if l else []
別の回答と同じです。
末尾再帰/ CPSスタイル（Pythonはとにかく最適化しない）：
def rev(l, k):
if len(l) == 0: return k([])
def b(res):
return k([l[-1]] + res)
return rev(l[:-1],b)
>>> rev([1, 2, 3, 4, 5], lambda x: x)
[5, 4, 3, 2, 1]
これは有用な回答ではないことは承知しています（この質問は既に回答済みですが）が、実際のコードではそうしないでください。 Pythonは末尾呼び出しを最適化できず、関数呼び出しが遅く、再帰の深さが固定されているため、代わりに繰り返し実行する理由が少なくとも3つあります。
トリックは、再帰後 参加することです：
def backwards(l):
if not l:
return
x, y = l[0], l[1:]
return backwards(y) + [x]
def revList(alist):
if len(alist) == 1:
return alist #base case
else:
return revList(alist[1:]) + [alist[0]]
print revList([1,2,3,4])
#prints [4,3,2,1]
除算＆amp;を使用します戦略を征服する。 D＆amp; Cアルゴリズムは再帰的なアルゴリズムです。 D＆amp; Cを使用してこの問題を解決するには、2つの手順があります。
- 基本ケースを把握します。これは、可能な限り単純なケースでなければなりません。
- 問題がベースケースになるまで、問題を分割または削減します。
ステップ1：基本ケースを把握します。あなたができる最も簡単なリストは何ですか 取得する？要素が0または1のリストを取得する場合、簡単に要約できます。
if len(l) == 0: #base case
return []
ステップ2：再帰ごとに空のリストに近づける必要があります 電話
recursive(l) #recursion case
たとえば
l = [1,2,4,6]
def recursive(l):
if len(l) == 0:
return [] # base case
else:
return [l.pop()] + recursive(l) # recusrive case
print recursive(l)
>[6,4,2,1]
出典：Grokking Algorithms
これはその逆です。 （もちろん、反復バージョンの方が良いでしょうが、再帰的でなければなりませんよね？）
def reverse(l, first=0, last=-1):
if first >= len(l)/2: return
l[first], l[last] = l[last], l[first]
reverse(l, first+1, last-1)
mylist = [1,2,3,4,5]
print mylist
reverse(mylist)
print mylist
def reverse(q):
if len(q) != 0:
temp = q.pop(0)
reverse(q)
q.append(temp)
return q
よりシンプルに見える：
def reverse (n):
if not n: return []
return [n.pop()]+reverse(n)
最初の要素を取得し、リストの残りを再帰的に逆にし、リストの最後に最初の要素を追加します。
def reverseList(listName,newList = None):
if newList == None:
newList = []
if len(listName)>0:
newList.append((listName.pop()))
return reverseList(listName, newList)
else:
return newList
print reverseList（[1,2,3,4]） [4,3,2,1]
Mutableのデフォルト引数と再帰の使用：
def hello(x,d=[]):
d.append(x[-1])
if len(x)<=1:
s="".join(d)
print(s)
else:
return hello(x[:-1])
hello("word")
追加情報
x[-1] # last item in the array
x[-2:] # last two items in the array
x[:-2] # everything except the last two items
再帰部分は hello（x [：-1]）で、 x [：-1]
理由：
a = [1,2,3,4,5]
a = [a[i] for i in xrange(len(a)-1, -1, -1)] # now a is reversed!
これはネストされたリストも逆にします！
A = [1, 2, [31, 32], 4, [51, [521, [12, 25, [4, 78, 45], 456, [444, 111]],522], 53], 6]
def reverseList(L):
# Empty list
if len(L) == 0:
return
# List with one element
if len(L) == 1:
# Check if that's a list
if isinstance(L[0], list):
return [reverseList(L[0])]
else:
return L
# List has more elements
else:
# Get the reversed version of first list as well as the first element
return reverseList(L[1:]) + reverseList(L[:1])
print A
print reverseList(A)
