What is this legendary stack you speak of? Recursion is actually a method of using stacks to achieve a task. However, call stacks are stored in a computer's memory, and these stacks cannot become infinitely large, as computers do not have an indefinite amount of memory space. Thus, when a recursive function has a bug, and never reaches a base case, the computer will eventually runs out of memory and crash the program. This is called a "stack overflow".
If a task can be divided into identical, smaller sub-tasks, this is a good indication that you can perform this task by recursion.
Fortunately, I find tracing recursion (relatively) straightforward to parse. Unfortunately, I find recursive functions extremely difficult to write. In last week's lab, we were introduced to tracing recursive functions in Python. Tracing recursion mentally is a bit of a mess at times, when you're trying to determine the output of a function call.
For example:
def nested_concat(L):
"""(list or str) -> str
Return L if it’s a str, if L is a (possibly-nested) str return
concatenation of str elements of L and (possibly-nested) sublists of L.
Assume: Elements of L are either str or lists with elements that
satisfy this same assumption.
# examples omitted!
"""
if isinstance(L, str):
return L
else: # L is a possibly-nested list of str
return ’’.join([nested_concat(x) for x in L])
In this function, we pass an argument that can either be a list or a string. If the argument is a string, then then argument is returned. Else, the join function is used to concatenate all ofthe elements in the argument. The tricky part is realizing the recursive bit: essentially, the
base case is that the argument should be a single, concatenated string. The function will
mutate all of the elements, sub-elements, sub-sub-elements (and so on), until it meets this condition. I've commented the tracing of two of the example calls posted in the lab below.
1) nested concat([’how’, [’now’, ’brown’], ’cow’]) # To trace this call: nested_concat([[’how’, [’now’, ’brown’], ’cow’]]) # We notice that L is a list: thus the else condition is reached --> ’’.join([nested_concat(x) for x in [’how’, [’now’, ’brown’], ’cow’]) #We notice that there is a sublist in L, so we concatenate the elements in that list --> ’’.join([’how’, ’nowbrown’, ’cow’]) #Now L is a list of str. Let's concatenate! --> ’hownowbrowncow’ 2) nested_concat([[’how’, [’now’, ’brown’, [’cow’]], ’eh?’]]) # First, we notice that there are multiple sub-lists --> ’’.join([nested_concat(x) for x in [[’how’, [’now’, ’brown’, [’cow’]], ’eh?’]]# We identify that ['cow'] is the innermost list, and concatenate each element in that list (only 1)# The list containing ['cow'] is ['now, 'brown', ['cow']] # so we would end up with 'nowbrowncow' # The list containing 'nowbrowncow' is [['how', 'nowbrowncow', 'eh?']] --> ’’.join([’how’, ’nowbrowncow', 'eh?’] --> ’hownowbrowncoweh?’
whimsies and I were in a similar situation of understanding the conceptual ideas behind recursion, but having difficulties executing this knowledge in week 5. Hopefully, our understanding of recursion has grown over the last couple of weeks!
