Week 7 - Recursion....wait what, again?

This week's assigned slog topic is recursion.  I'm half tempted to just refer you to different sections of week 4, but I'll re-iterate and expand on what I've already written anyway.

To start, let's review; recursion is a tool used in computer science to perform a specific task recursively, ie a function that calls on itself during it's execution.  (I'm quite sure that most recursive functions take iterable objects as an input, like lists and other list-like ADTs).

I previously likened recursion to the chain rule differentiation through a pretty complicated example, but now I realize there's a simpler example.  Consider the concept of factorials in math (!).  When you take a factorial of a number, you multiply all the integers from 0 up to that number.  This can be implemented in the following python function:

The above code is easy enough to read/understand, however the factorial function can also be implemented using recursion, like so:

Lets trace it - if you input the value n = 3, then the function will check if the value is 0, since 3 != 0, it then goes to the last line, 3 * factorial(3-1).  The factorial function here calls on itself, going through the process to see if 3-1 = 0 (it doesn't), so it proceeds to the last line again to give 3 * 2 * factorial (2-1), which then repeats again, giving 3 * 2 * 1 * factorial(1-1).  This time, however when 1-1 is inputted as n into the function, 1-1 does indeed = 0, hence returning 1.  Hence the final output for factorial(3) turns out to be 3 * 2 * 1 * 1 = 6.

List comprehensions are used a lot when we deal with recursive functions since lists can be nested.  Consider the following problem - we want to find the the max of the items in a list (that can be nested)  How would we go about this?

List comprehensions make the code for this problem relatively short:

Even though the concept of recursion is simple enough to understand its implementation can get quite complicated depending on the data structure you're working with - more complicated ADTs make it even worse.  However, I find the trick to tracing recursion is to not think too much...if that makes any sense.