recursion with a list in python

user_12186414 0
Viewed 779

I just started learning python and there are some recursion questions that I can't seem to figure out. The most annoying one is this: I need to build a function ind(e,L) where e is an int and L is a list.

By entering e if it is in the list the output needs to be its index For example:

ind(42,[0,14,52,42,15]) -> 3

This is the code I wrote this far but the index I get is always 0. Can someone please explain to me what I am doing wrong? 

def location(e,L):
    if L == []:
        return False
    elif e == L[0]:
        A = L[:-1].index(e)
        return A
    else:
        return location(e,L[1:])

print(location(14,[1,2,14,1]))

thanks :)

recursion python-3.x list python
5 Answers

You only return if e is at index 0 (you can skip the L[:-1]... term, it is always 0) and propagate that unchanged. Instead of returning the meaningless index, return the number of recursions. The simplest way is to add 1 whenever the function recurses.

def location(element, sequence):
    if not sequence:
        # e is not in the list at all
        # it is not meaningful to return an index
        raise IndexError
    elif element == sequence[0]:
        # we already know where e is
        # since we checked it explicitly
        return 0
    else:
        # keep searching in the remainder,
        # but increment recursion level by 1
        return 1 + location(element, sequence[1:])
user_53499160

I'm pretty new as well, but I think this should do the trick...


def function(e,L):
    try:
        x = 0
        for val in L:
            if e == val:
                return(x)
            else: x = x+1
    except:
        print('List provided does not contain any values')

x will count through the values and return when the index equals a value in the list. It will also return multiple matches, which might be helpful.

user_85483820

One thing to notice is that the time complexity and the space complexity of your code is O(n^2). Because L[1:] creates a new list every time! It is O(n) operation in terms of time and space.

One proper Pythonic way of doing it is:

def location(e, L):
    n = len(L)

    def _location(start):
        if start == n:
            raise IndexError

        if L[start] == e:
            return start

        return _location(start + 1)

    return _location(0)

print(location(14, [1, 2, 14, 1]))

Output:

2

Time Complexity: O(n)

Space Complexity: O(n) (Due to recursion.)

user_50998030

My solution is a bit different. I start looking for e from the right end of L. If found, then the index is simply the length of L minus 1 (since Python indexes start with 0).

This implementation does not require you to make any variable to store the index, which I think is neat.

def location(e, L):
    if L:
        if L[-1] == e:
            return len(L)-1
        else:
            return location(e, L[:-1])
    return False

Test:

>>> L = [0,14,52,42,15]
>>> location(42, L)
3
user_31900760

Shorter recursive solution:

def ind(a, b):
   def _ind(a, b):
     return False if not b else (b[0] == a or 1+_ind(a, b[1:]))
   return _ind(a, b) - 1

print(ind(42,[0,14,52,42,15]))

Output:

3

If you do not mind offsetting by one:

def ind(a, b):
  return False if not b else (b[0] == a or 1+ind(a, b[1:]))

>>>ind(42,[0,14,52,42,15]) - 1

Or, using a default parameter:

def ind(a, b, c = 0):
   return False if not b else (c if b[0] == a else ind(a, b[1:], c+1))

>>>ind(42,[0,14,52,42,15])
user_73267380
Related