Week 7: Getting back into the SLOG game

(Alternate title: Recursion is Recursion is Recursion II)

Note to TA: I would like this summary to be marked.

Reading Week went by extremely fast. Well, at least I was able to enjoy the comfort of my bed more often because I normally would have to be up at around 8am to get ready for school. With the due date of Assignment 2 (and assignments from other courses) looming, it's business as usual. We'll finish this assignment in due time, though.

How I feel at the moment

More concepts are being thrown at us week after week in CSC148. It's not at the same difficulty level as CSC108. That doesn't mean I can't look back at concepts from CSC108 (e.g. classes, Function Design Recipe) to help me understand what in the world is going on in CSC148 and, in particular, this assignment. Worksheets are being distributed each week for us to practice writing code on paper, much like CSC108. (Here's a personal action plan: I'm going to organize all my CSC148 worksheets in one place so I can look at them later. I have a bad habit of misplacing papers.)

Moving on then. In this post, I would like to summarize recursion with more detail this time.

To start this summary off, here's a dictionary definition of recursion:

It's used in linguistics too? Whoa!

In computer science, we solve complicated problems by creating methods to break down these problems into smaller problems. These methods are defined in terms of themselves. In other words, a recursive method is literally a "method within a method within a method..."

Circle of Life: Computer Science Edition

There are two easy steps to write recursive methods:

1. Identify the base case. This can be solved without recursion
2. Identify the general case. This is where the recursion takes place.

These steps somewhat remind me of proving by induction in MAT137. There, I would start with the base case, then move on to the induction step. In Python, this would take on the form of an if statement. Here's an example of a recursive function from one of the labs (with examples provided in the docstring) that contains an if statement:

def nested_concat(L):
    """ (list or str) -> str

    Return L if it's a str. Otherwise, if L is a possibly nested             list of str, return the concatenation of str elements of L. 
    
    >>> nested_concat('two')
    'two'
    >>> nested_concat(['one', 'two', 'three'])
    'onetwothree'
    """

    if isinstance(L, str): # base case; no recursion required
       return L
    else: # L is a possibly nested list of str
       return ''.join([nested_concat(x) for x in L])

In the Python shell, we would get the exact same results that we expected.

There's also a way to trace recursion on paper.

The first example involving a string, 'two', is very simple and will look like this:

nested_concat('two') --> 'two' # 'two' is a str

The second example requires some more steps:

nested_concat(['one', 'two', 'three']) --> ''.join([nested_concat(x) for x in ['one', 'two', 'three'])
--> ''.join(['one', 'two', 'three']) # traced nested_concat(str) before
--> 'onetwothree' # 'one' + 'two' + 'three'

This page, which was previously assigned as supplementary reading, can help others understand recursion and provides numerous examples, some of which involve graphics.

Jesse's post on recursion is a funny read, and he gets the point across. (That post also made me hungry.) Also, I really enjoyed reading Chris's insights on recursion. I liked his examples of recursion, and that has inspired me to create my own examples of recursive functions and other stuff to practice and get better at Python (because I'm still not very good at programming yet *cries*)!

I would like to wish the best of luck on A2! Also, feedback is greatly appreciated.

Thank you so much for reading! Cheers!