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 to this, but I do not know what to do next. I do recursion for exams. If anyone could help, I would be grateful.

Answer 1

Your simple case is fine, if the list length is 1 (or less), just return the list. In fact, we can simply check if the pool is empty ( if not lst ). If the list is larger, you need to think about how to simplify the problem in the recursive case. In words, you can formulate it this way: If the list is longer than 1, give me the last element of this list, expanded by the list that I get when I cancel this list without the last element in it. The last list is one less than the original list, so 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

Version written using fold idea

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

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

Now the fold function (strictly speaking, the left fold). This is a function in its own right and can be used for many things (see Link), the python equivalent will probably be reduce . Note that it takes a function f and applies this function to the list header and the variable acc (short for battery)

 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 the inverse that is recursive (since fold is recursive)

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

Thus, the code embodies the idea of ​​a recursive function. For example, if we wanted to recursively summarize 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 defined the right fold, then:

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

Then calling foldr(cons, [], xs) returns a list identical to the first.

Answer 4

Think about what you are trying to achieve for each recursive call. The link that is mentioned in your comment shows a really good illustration of how you sum the 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 get a reverse list? It probably looks something like this:

 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([]))))) 

Then it more accurately shows what you want to achieve. In the end, this is what you get.

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

Answer 5

Base case: you do not have a list, so you want to return an empty list.

A recursive case is what you do, so you want to add the last element to the recursive call in 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 is the driver I wrote:

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

This returns:

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

This will work with all repetitions.