CODEWITHSUNDEEP
pythonarrays
Avocado
Avocado

Reputation: 97

Finding an element in a list of lists using recursion

Given the following array,

l = [
    [0, 0, 0, 0, 0],
    [0, 2, 1, 1, 0],
    [0, 1, 0, 0, 0],
    [0, 1, 1, 3, 0],
    [0, 0, 0, 0, 0]
    ]

I am asked to define a recursive function that outputs "yay" every time we find a certain element in this 2D array.

def f(element, lst):
    if not lst:
        return 0
    if len(lst[0])==0:
        return f(element,lst[1:])
    if lst[0][0]==2:
        print("yay")
        return f(element,lst[0][1:])
    return f(element, lst[0][1:])

f(2, l)

I should be getting "yay" printed once. Instead I get the following:

Traceback (most recent call last):
  File "finder.py", line 37, in <module>
    f(2, l)
  File "finder.py", line 35, in f
    return f(element, lst[0][1:])
  File "finder.py", line 30, in f
    if len(lst[0])==0:
TypeError: object of type 'int' has no len()

Normally you can get the len() of a sublist, but not in the case where you check inside a function.

How can I check for an element in a 2D list using recursion?

Upvotes: 0

Views: 2208

Answers (3)

slybloty
slybloty

Reputation: 6516

When you do this:

return f(element,lst[0][1:])

lst[0][1:] cuts down your list of list into just a list. You get:

[0, 0, 0, 0]

That's why len(lst[0]) fails because lst[0] = 0, an int, therefore you can't get len() from it.

You have to rethink your process.

Part II:

What you're looking for will end up with a pretty ugly approach. Keep in mind you have to navigate both sides of your array. A nested loop can handle that nicely, unlike recursion.

Python has easier ways to do what you want, such as:

[print('yay') for i in l for j in i if j == element]

Upvotes: 1

Nick Vitha
Nick Vitha

Reputation: 476

When debugging, I usually find it very helpful to print out the values to see where they're erroring out. In this case (after fixing your assignment for l since you seemed to have copied it wrong):

l = [[0, 0, 0, 0, 0],
    [0, 2, 1, 1, 0],
    [0, 1, 0, 0, 0],
    [0, 1, 1, 3, 0],
    [0, 0, 0, 0, 0]]


def f(element, lst):
    print("Element: " + str(element))
    print("List: " + str(lst))
    if not lst:
        return 0
    if len(lst[0])==0:
        return f(element,lst[1:])
    if lst[0][0]==2:
        print("yay")
        return f(element,lst[0][1:])
    return f(element, lst[0][1:])

f(2, l)

Which leads to:

Element: 2
List: [[0, 0, 0, 0, 0], [0, 2, 1, 1, 0], [0, 1, 0, 0, 0], [0, 1, 1, 3, 0], [0, 0, 0, 0, 0]]
Element: 2
List: [0, 0, 0, 0]
Traceback (most recent call last):
  File "test.py", line 20, in <module>
    f(2, l)
  File "test.py", line 18, in f
    return f(element, lst[0][1:])
  File "test.py", line 13, in f
    if len(lst[0])==0:
TypeError: object of type 'int' has no len()

It is erroring out on this line if len(lst[0])==0: because you're trying to take the len() of whatever object is in the 0th place of your list, which is a number.

As an example, this is almost exactly what is happening:

>>> len(0)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: object of type 'int' has no len()

@slybloty's answer is why you're only getting a list.

Upvotes: 1

Picachieu
Picachieu

Reputation: 3782

The declaration for your list really only creates one list of integers.

l = [0, 0, 0, 0, 0]
    [0, 2, 1, 1, 0]
    [0, 1, 0, 0, 0]
    [0, 1, 1, 3, 0]
    [0, 0, 0, 0, 0]

Python assigns l to [0, 0, 0, 0, 0] and doesn't care about the next 4 lines. Because of that, this line:

if len(lst[0])==0:

attempts to find the length of l[0], which is an integer.

Simply change your declaration for l to this:

l = [[0, 0, 0, 0, 0],
    [0, 2, 1, 1, 0],
    [0, 1, 0, 0, 0],
    [0, 1, 1, 3, 0],
    [0, 0, 0, 0, 0]]

Upvotes: 0

Related Questions