Hi!
I currently try to understand recursion on made up example. Imagine you have a briefcase, which can be opened by the key. The key is in the big box, which can contain other smaller boxes, which key might be in.
So in my example boxes are lists. The recursion appears when we find the smaller box - we search it for the key. The problem is that my function can find the key if it is actually in the box and can't go back if there is nothing like 'key'.
Unfortunately, i could not understand how to go back if there is no key in the smaller box. Can you help me solve this puzzle? By the way, have a nice day! Here is the code (big box consists in the way when the key can be found and returned):
box = ['socks', 'papers', ['jewelry', 'flashlight', 'key'], 'dishes', 'souvernirs', 'posters']
def look_for_key(box):
for item in box:
if isinstance(item, list) == True:
look_for_key(item)
elif item == 'key':
print('found the key')
key = item
return key
print(look_for_key(box))
CodePudding user response:
Integrating the above comments:
box = ['socks', 'papers', ['jewelry', 'flashlight', 'key'], 'dishes', 'souvernirs', 'posters']
def look_for_key(box):
for item in box:
if isinstance(item, list) == True:
in_box = look_for_key(item)
if in_box is not None:
return in_box
elif item == 'key':
print('found the key')
return item
# not found
return None
print(look_for_key(box))
which prints:
found the key
key
If the key is deleted from the box, executing the code prints:
None
CodePudding user response:
This is a typical text book tree recursion question. What you want is to traverse a hieratical data structure called tree. A typical solution is mapping a function over the tree:
from functools import reduce
def look_for_key(tree):
def look_inner(sub_tree):
if isinstance(sub_tree, list):
return look_for_key(sub_tree)
elif sub_tree == 'key':
return sub_tree
else:
return ''
return reduce(lambda left_branch, right_branch: look_inner(left_branch) look_inner(right_branch), tree, '')
box = ['socks', 'papers', ['jewelry', 'flashlight', 'key'], 'dishes', 'souvernirs', 'posters']
look_for_key(box)
# ==> 'key'
To make it explicit I use tree
, sub_tree
, left_branch
, right_branch
as variable names instead of box
, inner_box
and so on as in your example. Notice how the function look_for_key
is mapped over each left_branch
and right_branch
of the sub_tree
s in the tree
. The result is then summarized using reduce
(A classic map-reduce procedure).
To be more clear, you can omit the reduce
part and keep only the map
part:
def look_for_key(tree):
def look_inner(sub_tree):
if isinstance(sub_tree, list):
return look_for_key(sub_tree)
elif sub_tree == 'key':
return sub_tree
else:
return None
return list(map(look_inner, tree))
look_for_key(box)
# ==> [None, None, [None, None, 'key'], None, None, None]
This does not generate your intended format of the result. But it helps to understand how the recursion works. map
just adds an abstract layer to recursively look for keys into sub trees which is equivalent to the syntactic sugar of for
loop provided by python. That is not important. The essential thing is decomposing the tree properly (deduction) and set-up proper base condition to return the result.
If it is still not clear how recursion exactly works in this case, you can get rid of all abstractions and syntactic sugars and just build a native recursion from scratch:
def look_for_key(box):
if box == []:
return []
elif not isinstance(box, list) and box == 'key':
print('found the key')
return [box]
elif not isinstance(box, list) and box != 'key':
return []
else:
return look_for_key(box[0]) look_for_key(box[1:])
look_for_key(box)
# ==> found the key
# ==> ['key']
Here all three fundamental elements of recursion:
- base cases
- deduction
- reclusive calls
are explicitly displayed. You can also see from this example clearly that there is no miracle of going out of an inner box (or sub-tree). To look into every possible corner inside the box (or tree), you just repeatedly split it to two parts in every smaller box (or sub tree). Then you properly combine your results at each level (so called fold or reduce or accumulate), here using
, then recursive calls will take care of it and help to return to the top level.
The native recursion solution is also able to find out multiple keys, because it travers over the whole tree and accumulates all matches and lazily returns to top level:
box = ['a','key','c', ['e', ['f','key']]]
look_for_key(box)
# ==> found the key
# ==> found the key
# ==> ['key', 'key']