#5 Recursion

A large concept that CSC148 revolves around is that of recursion. Most of our lecture's are focused on implementing recursion in order to simplify the task we are looking at, and also to make things more efficient. By definition, recursion is to define something in terms of itself" in order to simplify a task into smaller parts to achieve a goal. In programming, recursion is implementing by creating functions that call themselves. The best way to explain recursion is through examples:

Example #1

 

Above is code for a function that finds the minimum number inside of a nested list. I will step you through a call on recursive_min([2, [1, 12]).

1. Loop over the list
2. i == 2 (not list) -> so append object to the list
3. list = [2] so far.
4. i == list so we call the function in itself (recursively)

   1. Start over again and repeat.
   2. Since there is no other nested list, this call will return the min number.
   3. the min == 1.
   4. This call returns 1, which is appended to the original list.
 
5. The original list now looks like this: [2, 1]
6. Notice, there is nothing left to loop over.
7. Return the min of the list, which is 1.

Therefore, the smallest number in the list is 1. 

Notice, we have minimized this task to a single line of code using recursion. If we were to not use recursion, well, it wouldn't look pretty.

Example #2

Instead of an example of coding, we can also explain recursion using visuals. A Tree (the ADT I talked about last week) is a recursive data structure. When I was first introduced to trees, my understanding of recursion got much clearer.

 A single Binary Tree is a tree that consists of a root and two children. However, using recursion we can extend the concept and create a larger tree that is made up of other binary nodes (as you can see below).

How is this recursion? If we look back at our definition of recursion: something "defined in itself", we can see that this tree is exactly that.
The general tree is made up of smaller sub-binary nodes that can be looked at as singular. If we attempted to traverse through this tree, we would do so in smaller steps; one binary tree at a time.

Thoughts on Recursion 

Recursion is a very abstract concept that is something that you get right away or takes time to understand. For me, it took some time for the concept to finally click. In my opinion, following Danny's advice to attempt to trace the recursion on paper and to not think about recursion in its details is vital to understanding recursion.