More Talk About Recursion!

From the beginning of the csc148 class, we have already been told the importance of recursion. Knowing recursion and analyzing recursion is a important step in programming. However, recursion in the most time is extremely hard to track all the stuff. And I want to show some ways to fully understand the recursion and my experience about learning the recursion.

First of all, one powerful tool to understand recursion is drawing the recursion tree. (Actually I learn this stuff from a book called Introduction of Algorithms,And this is an extremely good book that tells you everything you need about understanding algorithm) A recursion tree is just like the picture the professor draw during the lecture. Take the hanoi tower as an example, the top node is the root of the tree and also the first time we call the method. Then the tree will be constantly adding the left nodes until it meet the base case, which means there are only one cheese left and it will execute the first step.Then the left most node will quit and you will get into the right node of the previous left node. That's sort of how I figure out the recursion in a tree model.

Another tool I guess is the visualizer. And actually it will give you more understanding about how computer works. For example, after visualizing one simple recursion function, you may notice that the recursion is actually based on the stack ADT. That's why when we sometimes forget to write the base case for the recursion, we will get stack overflow error.

My advice about learning and understanding the recursion is that don't rush and work step by step. The recursion is actually simple and it is so similar to one proof method in math, which is the Proof by Induction. I find it helpful if you can completely understand the Induction first.