CODEWITHSUNDEEP
pythonalgorithmrecursion
Corey
Corey

Reputation: 310

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

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)

Upvotes: 1

Views: 864

Answers (3)

iAmServer
iAmServer

Reputation: 39

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)

Upvotes: 0

Cameron Hyde
Cameron Hyde

Reputation: 118

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

Upvotes: 0

iz_
iz_

Reputation: 16623

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

Upvotes: 1

Related Questions