Recursive call inside a for loop in python doesn't exit where expected

Question

I don't understand why a recursive function inside a for loop doesn't exit the function at the base case.

I am reading grokking algorithms and trying to implement an example for understanding.

box = [
    [["key"], []],
    [[], []],
    [[], []]
   ]
def find_key(box):
  for item in box:
    print(item)
    if item == "key":
      print("found")
      return
    elif type(item) == type([]):
      print("looking in next box")
      find_key(item)
find_key(box)

I would expect that once the key is found, the function is exited, but it continues to look through the rest of the list.

This might also be my lack of understanding of what return does especially related to recursive calls. I can get my expected behavior using

import sys
def find_key(box):

    for item in box:
        if item == "key":
            print("found")
            sys.exit()
        elif type(item) == type([]):
            print("looking in next box")
            find_key(item)

find_key(box)

iz_ · Accepted Answer · 2019-01-31 03:04:35Z

1

You are only exiting the last recursive call, not all of them. Try this:

box = [
    [["key"], []],
    [[], []],
    [[], []]
   ]

def find_key(box):
  for item in box:
    print(item)
    if item == "key":
      print("found")
      return
    elif type(item) == type([]):
      print("looking in next box")
      return find_key(item) # <-- add a `return`

find_key(box)
# [['key'], []]
# looking in next box
# ['key']
# looking in next box
# key
# found

By the way, isinstance is a bit better than equating types. You can use:

isinstance(item, list)

instead of type(item) == type([]).

answered Jan 31, 2019 at 3:04

iz_

16.7k4 gold badges29 silver badges43 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Corey Over a year ago

If I move the key anywhere outside of the place it is in currently, it isn't found with these changes. box = [ [[], ["key"]], [[], []], [[], []] ]

Cameron Hyde · Accepted Answer · 2019-01-31 03:32:08Z

0

Your problem is that you are returning from the function, but not all of the functions. Since you are building a recursive function, there are multiple iterations of the functions in effect at one time (since one calls another before returning itself).

You need to re-write the function to catch and return from each function call. I adapted the following from this post: Python: How to search a nested list using recursion

def find_key(box):
for item in box:
    if type(item) is list:
        if find_key(item):
            return "found"
    if item == "key":
        print("found")
        return "found"
return

answered Jan 31, 2019 at 3:32

Cameron Hyde

1287 bronze badges

Comments

iAmServer · Accepted Answer · 2019-01-31 04:26:56Z

0

Add return, exit the loop when key is found

box = [
    [["key"], []],
    [[], []],
    [[], []]
   ]

def find_key(box):
  for item in box:
    print(item)
    if item == "key":
      print("found")
      return
    elif type(item) == type([]):
      print("looking in next box")
      return

find_key(box)

edited Jan 31, 2019 at 4:26

answered Jan 31, 2019 at 3:09

iAmServer

498 bronze badges

1 Comment

Sharad Over a year ago

Please add some comments explaining how this fixes the problem.

Collectives™ on Stack Overflow

Recursive call inside a for loop in python doesn't exit where expected

3 Answers 3

1 Comment

Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related