Definition of Recursion: See "Recursion".

The past few weeks of CSC148 have involved a Mid-Term, the due date of Assignment 1, some interesting labs on recursive data structures (trees, linked lists) and the beginning of Assignment 2 part 1. I think now is a good time to reflect back on one of the core concepts that has permeated all the topics of the past few weeks: Recursion.

In past weeks' SLOGs, I have discussed some of the introductory concepts of recursion - from base and recursive cases to modelling a problem recursively. In what follows, I will seek to elaborate more on this latter topic as well as some applications of recursion that I found interesting.

The tour of four stools in our Tours of Hanoi assignment was the first major application of recursion - besides lecture/labs - we had to do individually. The first step of the algorithm obviously recursive (it was in the assignment handout!) - we had to attain a value for 'i' which would allow the rest of the algorithm to run most effectively. I toyed with this a bit until I decided to implement this recursive algorithm in a brute force manner - I had my program shift through all legitimate 'i' values until an optimal one was found. The recursive call here was simple: it was written write in the formula!

Next we had the actual four peg algorithm itself. With the value of 'i' selected, these 3 recursive calls worked to shift the blocks of cheese to the destination. Here is where I saw the key to the entire algorithm: the three peg algorithm was simply a sub-part of the four peg algorithm. Once I moved n-i cheeses to an intermediate stool, I called the three peg algorithm to do the work of bringing the i cheeses to the destination. In essence, I thought of it as 'recursion within 'recursion'. "Recurception" if you will ;)

Though this seems overwhelming for an introductory recursion assignment, struggling through it really helped to see the way recursion provided a neat and intuitive solution to an otherwise difficult problem.

Alas, my thirst for more recursive insights was not quenched and immediately began thinking of other problems that could have very elegant recursive solutions. What came to mind was the fundamental theorem of arithmetic: that every integer greater than 1 can be written as a unique factorization of prime numbers. I decided to put my recursive knowledge to the test and design an algorithm to produce the prime factors of some n.

First I wrote a function to generate prime numbers from 1 to n and then I began work on the recursive function. The algorithm is rather simple and elegant with recursion: Loop through the list of generated primes and if a prime divides n, add it to the list of factors and then recursively call the algorithm to generate the prime factors of what is left when that prime factor divides n. And so, a list of prime factors for some n are generated.

This algorithm really helped to affirm my grasp of the recursion learned so far: You choose your base case and recursive call - trace a few simple cases and then hope for the best! Of course, a great deal of thought needs to go into choosing your recursive calls but once you have it for one, you may assume it will work for the cases that will follow - a lot like inductive reasoning!