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

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 2

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 3

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

Answer 4

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 5

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 6

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 7

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 8

looks simpler:

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

Answer 9

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 10

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 11

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 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

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 14

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

Answer 15

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 16

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 17

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 18

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 19

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 20

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