In the last week, we learned about recursion, recursive functions, and how to trace the action of a recursive function.

Recursive functions are functions which use themselves within their own definition.  At first it was a bit of a weird concept to wrap my head around.  If someone were to ask for a definition of a word, and you used that word, it wouldn't help them at all, but with recursive functions they can actually work.

The key to how recursive functions work is the base case.  We have been working with functions that deal with nested lists (lists inside lists), where the base case is anything that isn't a list.  The code written splits the cases into 2 options: if it encounters a list it uses itself on the list and returns an output (for example, tracking the items in the list), and if it encounters anything else it does something (usually returns a number, like 0 or 1).  This non-list item is the base case for functions dealing with lists.

What helped me understand how recursion works was actually tracing the action of the function.  To trace how the function works, you start with the base case, a non-list.  The function acts on the base case to do something, and then returns that.  Then you go onto the next simplest case, a list of depth 1.  When the function acts on the list, it calls itself on each item of the list.  Since all the items are the base case, it performs its action on each of them, which then allows it to give an output for that list.  Then if we look at the next simplest case, a list of depth 2, we see that once we enter the list, the remaining items are either lists of depth 1 and non-lists, both of which we know the output for since we already traced them.  This can continue to infinitely complicated levels, or infinitely nested lists, because we can always trace them down to a base case, and then work backwards to get the output. 

Talking about how recursion works can be very abstract and confusing.  I'm sure my description of how it works has been vague and hard to follow, but that was how I felt while learning it.  The act of tracing through how the function works was the key to understanding recursion.  Simply walking through the steps from the base case upwards will demonstrate how the function works, and facilitate understanding.