Reversing a list using recursion in python

Question

def revlist(lst):
    if len(lst) == 1:
        return lst
    else:
        return lst[(len(lst) - 1)

I have come as far as this but I don't know what to do next. I'm practicing recursion for my exams. If anyone could help I'd be grateful.

Answer 1

Your simple case is fine, if the length of the list is 1 (or smaller), simply return the list. In fact, we can simply check whether the list is empty (by issueing if not lst). If the list is larger, you have to think about how to simplify the problem in the recursive case. In words, you can formulate it like this: If the list is longer than 1, give me the last element of that list extended by the list I get when I reverse the given list without the last element in it. The latter list is one smaller than the original list, thus the problem is simplified.

In code:

def reverse(lst):
    if not lst: # this will be true if lst == []
        return lst
    return lst[-1:] + reverse(lst[:-1]) # recursive case

# Demo
print(reverse([1,2,3,4,5])) # [5, 4, 3, 2, 1]

Answer 2

another way

def revlist(lst):
    if len(lst) == 0:
        return ([])
    else:
        return (revlist(lst[1:]) + [lst[0]] )

Answer 3

Think of what you are trying to achieve for every recursive call. The link that thefourtheye mentions in his comment shows a really good illustration of how you sum a list with recursion:

listSum([1, 3, 4, 5, 6]) = 1 + listSum([3, 4, 5, 6])
                         = 1 + (3 + listSum([4, 5, 6]))
                         = 1 + (3 + (4 + listSum([5, 6])))
                         = 1 + (3 + (4 + (5 + listSum([6]))))
                         = 1 + (3 + (4 + (5 + (6 + listSum([])))))

Using this as a base point, how would you then achieve a reversed list? It would probably look something like:

revlist([1, 3, 4, 5, 6]) = [6] + revlist([1, 3, 4, 5])
                         = [6] + ([5] + revlist([1, 3, 4]))
                         = etc etc
                         = [6] + ([5] + ([4] + ([3] + ([1] + revlist([])))))

This then shows more concisely what you want to achieve. In the end, this is what you would get.

def revlist(lst):
    if not lst:
        return []
    else:
        return lst[-1:] + revlist(lst[:-1])

Answer 4

A version written using the idea of a fold

We need a function that we will call cons (this comes from lisp/scheme etc). It takes an element and a list and adds that element to the head (start) of the list. Note that in python this is not efficient.

def cons(x,xs):
  return [x] + xs

Now the function fold (strictly speaking a left fold). This is a function in it's own right and can be used for many things (see the link) the python equivalent would probably be reduce. Note that it takes a function f and applies this function to the head of the list and the variable acc (short for accumulator)

def foldl(f,acc,xs):
  if not xs:         
    return acc
  head, *tail = xs
  return foldl(f, f(head,acc), tail)

Now we can write a version of reverse that is recursive (because fold is recursive)

def reverse(xs):
  return foldl(cons, [], xs)

So a fold embodies the idea of a recursive function. For example if we wanted to recursively sum a list of numbers we could define it as:

from operator import add # this is just '+' as a function
def sum(xs):
  return foldl(add, 0, xs)

If we were to define a right fold, as follows:

def foldr(f,acc,xs):
  if not xs:         
    return acc
  head, *tail = xs
  return f(head, foldr(f, acc, tail))

Then calling the foldr(cons, [], xs) will return a list identical to the initial one.

Answer 5

Base case is you don't have a list, so you want to return the empty list.

Recursive case is that you do, so you want to prepend the last element to the recursive call on the rest of the list.

def revlist(lst):
    if not lst:
        return lst
    # Create a list containing only the last element
    last = [lst[-1]]
    # Rest contains all elements up to the last element in `lst`
    rest = lst[:-1]
    # Prepend last to recursive call on `rest`
    return last + revlist(rest)

Here's a driver I wrote:

lst = [1, 2, 3, 4, 5]
print(revlist(lst))

This returned:

12:03 $ python test.py 
[5, 4, 3, 2, 1]

This will work with all iterables.