题
我想要一个函数,它将返回给出的列表的反向 - 使用递归。我怎么能这样做?
解决方案
将列表的第一个元素附加到反向子列表:
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]
使用Divide&征服战略。 D& C算法是递归算法。 要使用D& C解决这个问题,有两个步骤:
- 弄清楚基本情况。这应该是最简单的情况。
- 将问题分开或减少,直至成为基本案例。 醇>
步骤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算法
这个反转到位。 (当然迭代版本会更好,但它必须是递归的,不是吗?)
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)
不隶属于 StackOverflow