Week 7: Selected Summary - Recursion Post from Week 4/5

In week 4 of CSC148, we broached the topic of recursion. Recursive functions are functions that call themselves. They have a conditional structure that specifies a base case (or cases): a condition (or conditions) that will stop the function from making calls to itself.  The also have a general case, which specifies the method in which recursive sub-calls will be combined. Essentially, the general case is the part where the function calls itself. It is important that you designate a base case, or the function call will reach a maximum recursion depth, and result in a stack overflow.

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?’

Although I understand the concept of recursion, I am finding it difficult to actually put it into practice. Specifically, I have difficulties selecting and coding the base case and the general case of a recursive function. Parsing and developing recursive functions is something that will take some time to get the hang of. Hopefully I will be able to wrap my head recursion and get a strong handle of this very essential concept.

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!