How do I reverse a list using recursion in Python?

Question

I want to have a function that will return the reverse of a list that it is given -- using recursion. How can I do that?

Answer 1

Append the first element of the list to a reversed sublist:

mylist = [1, 2, 3, 4, 5]
backwards = lambda l: (backwards (l[1:]) + l[:1] if l else []) 
print backwards (mylist)

Answer 2

A bit more explicit:

def rev(l):
    if len(l) == 0: return []
    return [l[-1]] + rev(l[:-1])

---

This turns into:

def rev(l):
    if not l: return []
    return [l[-1]] + rev(l[:-1])

Which turns into:

def rev(l):
    return [l[-1]] + rev(l[:-1]) if l else []

Which is the same as another answer.

---

Tail recursive / CPS style (which python doesn't optimize for anyway):

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]

Answer 3

I know it's not a helpful answer (though this question has been already answered), but in any real code, please don't do that. Python cannot optimize tail-calls, has slow function calls and has a fixed recursion depth, so there are at least 3 reasons why to do it iteratively instead.

Answer 4

The trick is to join after recursing:

def backwards(l):
  if not l:
    return
  x, y = l[0], l[1:]
  return backwards(y) + [x]

Answer 5

Use the Divide & conquer strategy. D&C algorithms are recursive algorithms. To solve this problem using D&C, there are two steps:

1. Figure out the base case. This should be the simplest possible case.
2. Divide or decrease your problem until it becomes the base case.

Step 1: Figure out the base case. What’s the simplest list you could get? If you get an list with 0 or 1 element, that’s pretty easy to sum up.

if len(l) == 0:  #base case
    return []

Step 2: You need to move closer to an empty list with every recursive call

recursive(l)    #recursion case

for example

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]

Source : Grokking Algorithms

Answer 6

This one reverses in place. (Of course an iterative version would be better, but it has to be recursive, hasn't it?)

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

Answer 7

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]

Answer 8

A recursive function to reverse a list.

def reverseList(lst):
    #your code here
    if not lst:
        return []
    return [lst[-1]] + reverseList(lst[:-1])


print(reverseList([1, 2, 3, 4, 5]))

Answer 9

def reverse(q):
    if len(q) != 0:
        temp = q.pop(0)
        reverse(q)
        q.append(temp)
    return q

Answer 10

looks simpler:

    def reverse (n):
        if not n: return []
        return [n.pop()]+reverse(n)

Answer 11

Take the first element, reverse the rest of the list recursively, and append the first element at the end of the list.

Answer 12

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]

Answer 13

Using Mutable default argument and recursion :

def hello(x,d=[]):
    d.append(x[-1])
    if len(x)<=1:
        s="".join(d)
        print(s)

    else:
        return hello(x[:-1])

hello("word")

additional info

x[-1]    # last item in the array
x[-2:]   # last two items in the array
x[:-2]   # everything except the last two items

Recursion part is hello(x[:-1]) where its calling hello function again after x[:-1]

Answer 14

This will reverse a nested lists also!

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)

Padmal's BLOG

Answer 15

You can reduce the recursion depth by half by swapping the first and last elements at once and calling rev recursively on the middle of the list:

lks=[2,7,3,1,9,6,5]
def rev(lks):
    if len(lks)<2:
        return lks
    return [lks[-1]]+rev(lks[1:-1])+[lks[0]]
print(rev(lks))

Answer 16

The answer you're looking for is inside the function. The rest of the stuff is just to see (or if you want to compare) the time taken by the different algorithms.

import time
import sys

sys.setrecursionlimit(10**6)


def reverse(ls1):
    if len(ls1) <= 1:
        return ls1
    else:
        ls1[0], ls1[-1] = ls1[-1], ls1[0]
        return [ls1[0]] + reverse(ls1[1:-1]) + [ls1[-1]]


ls = [*range(2000)]
start_time = time.time()
print(reverse(ls))
stop_time = time.time()
print(f"Total time taken: {(stop_time - start_time) * 1000} msec.")

Answer 17

Why not:

a = [1,2,3,4,5]
a = [a[i] for i in xrange(len(a)-1, -1, -1)] # now a is reversed!

Answer 18

if it is a list of numbers easiest way to reverse it would be. This would also work for strings but not recommended.

l1=[1,2,3,4]
l1 = np.array(l1)
assert l1[::-1]==[4,3,2,1]

if you do not want to keep it as a numpy array then you can pass it into a list as

l1 = [*l1]

again I do not recommend it for list of strings but you could if you really wanted to.

Answer 19

def reverse_array(arr, index):
    if index == len(arr):
        return

    if type(arr[index]) == type([]):
        reverse_array(arr[index], 0)

    current = arr[index]
    reverse_array(arr, index + 1)
    arr[len(arr) - 1 - index] = current
    return arr

if __name__ == '__main__':
    print(reverse_array([[4, 5, 6, [4, 4, [5, 6, 7], 8], 8, 7]], 0))

Answer 20

def disp_array_reverse(inp, idx=0):
    if idx >= len(inp):
        return
    disp_array_reverse(inp, idx+1)
    print(inp[idx])