CODEWITHSUNDEEP
pythonlistclassrecursion
CF11
CF11

Reputation: 109

Recursive linear search for class list array python

Hi how would I do linear search using recursion instead of doing it iteratively? This is how I'm trying to do it currently. I get this error

if l[0] == key:

TypeError: 'type' object is not subscriptable TypeError: 'type' object is not subscriptable for l

@classmethod
def _linear_search_r(l,key, i=0):

    if l:  #Check if list is not empty
        if l[0] == key:
            return i 

        s = _linear_search_r(l[1:],key, (i + 1))
        if s is not False:
            i = s
            return i

    return False

Upvotes: 0

Views: 1484

Answers (2)

chepner
chepner

Reputation: 531858

There are only three cases to worry about:

  • If the input list is empty, raise an exception
  • If the "first" element of the list is a match, return the index.
  • If the "first" element of the list is not a match, make a recursive call and return its value.

I put "first" in quotes because while it is elegant to pass the tail of the input list to each recursive call, the overhead of constructing the tail makes it inefficient to do so. Instead, we just pass an incremented i along to use as an index to walk the list.

# Elegant, but inefficient
def _linear_search(l, key):
    if not l:
        raise LookupError(key)
    elif l[0] == key:
        return 0
    else:
        return 1 + _linear_search(l[1:], key)

# Clumsy, but faster
# Note: generally, you do not explicitly call this
# with an explicit value for i; it should only be
# used as a 
def _linear_search(l, key, i=0):
    if not l:
        raise LookupError(key)
    elif l[i] == key:
        return i
    else:
        return _linear_search(l, key, i+1)

# Slightly more complicated, but hides the i argument from the user
def _ls_helper(l, key, i):
        if not l:
            raise LookupError(key)
        elif l[i] == key:
            return i
        else:
            return _ls_helper(l, key, i+1)

def _linear_search(l, key):
    return _ls_helper(l, key, 0)

Upvotes: 1

ShadowRanger
ShadowRanger

Reputation: 155505

This is a class method, so the first argument it receives (which you named l) is a reference to the class itself.

If l is supposed to be an instance of said class, remove the @classmethod decorator. If l is supposed to be unrelated to the class, either change @classmethod to @staticmethod (the latter does not implicitly receive the type as the first argument) or add a cls argument in front of l.

If the goal is to process an instance attribute, then I'd suggest making the top-level function an instance method, with a recursive helper method (that's either class or static). For example:

# Public instance method that delegates to recursive class method
def linear_search(self, key):
    return self._linear_search_r(self._values, key)

@classmethod
def _linear_search_r(cls, l, key, i=0):

    if l:  #Check if list is not empty
        if l[0] == key:
            return i 

        s = cls._linear_search_r(l[1:],key, (i + 1))
        if s is not False:
            i = s
            return i

    return False

Upvotes: 2

Related Questions