Week 5: Tracing 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 of the 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?’