Last week in class we had our formal introduction to recursion. At the beginning of the course, our prof showed us a sneak peak into the wonderful (with this week's experience I'd attest as mostly horrendous) world of recursion:
def sum_list(L: list) -> float:
"""
Return sum of the numbers in possibly nested list L
>>> sum_list([1, 2, 3])
6
>>> sum_list([1, [2, 3, [4]], 5])
15
"""
return sum([sum_list(x) if isinstance(x, list) else x for x in L])
That was the first time I'd come across recursion, and after some in depth tracing, I thought I'd figured it out. Through Exercise 4 this week, I've come to experience in full both the wonders and aforementioned absolute horrors of recursion.
In our exercise this week, we were asked to construct a list representation of a binary tree from a preorder list traversal and inorder list traversal (serving as the parameters to the function).
For instance, given:
preorder traversal [10, 6, 8, 12, 11, 15] and
inorder traversal [8, 6, 12, 10, 11, 15]
Our function is to take these two lists to construct:
[10, [6, [8, None, None], [12, None, None]], [11, None, [15, None, None]]]
Illustrated as follows:
From this, it's evident that preorder traversal traverses the binary tree in the sequence of node, left subtree, right subtree, and inorder traversal traverses the tree in the sequence of left subtree, node, right subtree.
There are a number of inferences that I made first considering this problem.
- The first value in preorder is the parent node of the tree, thus in inorder, all the values that preceeds the first value described in preorder will be on the left of the parent node, or in other words, they will be in the left subtree.
- You can guess that the point at which recursion should stop (even before having identified exactly how recursion should occur) is when you get to the leaves, at which point, the [1] and [2] values are None (i.e. these nodes have empty subtrees). That's a hint for the base case.
- The same kind of recursion occurs for the left subtree as well as the right subtree. There needs to be some way to connect the results of recursion from the left subtree and from the right subtree together in the end.
At the core, to the seasoned programmer, this is really all there is to it. However, since it was my first time working on recursion, this problem confused me profusely.
My first attempt yielded the following result:
def make_tree(preorder, inorder):
if inorder.index(preorder[0]) == 0:
nested_list = [preorder[0], None, None]
return nested_list
else:
tree_list = [preorder[0], make_tree(preorder[1:], inorder), make_tree(preorder[1:], inorder)]
return tree_list
>>> [10, [6, [8, None, None], [8, None, None]], [6, [8, None, None], [8, None, None]]]
As compared to the correct result:
[10, [6, [8, None, None], [12, None, None]], [11, None, [15, None, None]]]
Alright, so I got the first few values correct, but needless to say, this was incorrect. My idea here was that I noticed on the outmost layer that the first value was the value at [0] of preorder, and the second and third value were nested trees, so I knew I had to have recursion for those two parts. From what I knew of recursion, some 'work' or change has to be made to descend into the next level of recursion, and it logically made sense that the new preorder list in my next level of make_tree would take on the values after the value at [0] (since it was already written down). I didn't know what to do with inorder though, so I just left it there to test.
For the base case, based on #2 of the inferences I made above, I knew the Nonetypes had to be incorporated for those leaf values, but (in retrospect) I was still thinking in my iterative ways, so I assumed the base case to be [preorder[0], None, None]. I saw that the point at which the first element in the preorder list becomes the first element in the inorder list is the point that we've reached the leaves of the tree, hence inorder.index(preorder[0]) == 0.
Because I wasn't 100% sure about how to approach this problem, I put together what I knew and without a full understanding of what I wrote, derived my first attempt.
After having exhausted all of my available brainpower, it was time to get help. After much consultation with a friend that's a much more experienced programmer, I slowly gained intuition of how to choose a correct base case. Attempt 2 is as follows:
def make_tree(preorder,inorder):
if len(preorder) == 0 and len(inorder) == 0:
return None
elif len(preorder) == 0:
return [inorder[0],None,None]
elif len(inorder) == 0:
return [preorder[0],None,None]
else:
left = make_tree(preorder[1:inorder.index(preorder[0])], inorder[:inorder.index(preorder[0])])
right = make_tree(preorder[inorder.index(preorder[0]) + 1:], inorder[inorder.index(preorder[0]) + 1:])
return [preorder[0], left, right]
After weeding out the unnecessary elif statements, I finally arrived at the correct code.
def make_tree(preorder, inorder):
if len(preorder) == 0 and len(inorder) == 0:
return None
else:
left = make_tree(preorder[1:inorder.index(preorder[0]) + 1],
inorder[:inorder.index(preorder[0])])
right = make_tree(preorder[inorder.index(preorder[0]) + 1:],
inorder[inorder.index(preorder[0]) + 1:])
return [preorder[0], left, right]
This exercise (part a and b) took me a few hours to complete, and the biggest challenge for me was in trusting that recursion will work. This is where the magical part comes in. If you read the code, it's very intuitive. It makes sense that the same process through each of the subtrees would generate a nested result, that [preorder[0], left, right] gives exactly what it looks like will give. The difficulty in recursion lies in my inability to accept this simplicity. To understand a concept, I must see each step and understand it thoroughly, and so in completely this exercise and other recursion exercises I came across, I always had to trace through the whole code to the base case before I would believe it works.
The biggest challenge for me in the recursion I encountered in this exercise is in knowing how to incorporate the right side recursion of a tree or list with the left side. I seem to always get the left side to 'work', but I can't get my head wrapped around how I should go about the right side.
I thoroughly hope an understanding of recursion will come with practise. For now, I am just ecstatic that I got the desired result for this exercise.
