Week 7 - Recursion
Learning the concept of recursion was quite new for me.
Python is really the first programming language that I was introduced with. It has very simple syntax and the learning curve was quite fast until I reached recursion. It stopped me right in my path. Usually I learn well alone, and I have learned most of Python and applying it through the book "How to Think Like a Computer Scientist". The idea of recursion is not new. It's structure makes sense intuitively but it does seem to lack something that makes is flow in my mind.
From CSC108, we have simply learned to do things step by step. Make a function that performs this, then make another function that do that. If needed, we can make helper functions that makes us accomplish what we need by calling it in another function. However, recursion seems to by pass the step by step format by simply encompassing all the steps into one step, by recursively calling the function itself with simply one line of code. As written in the book, you will need to perform mental abstraction, or take a leap of faith in believing that the base case will work. However, I found taking the leap of faith to be quite difficult. I often find myself tracing the whole code line by line, as I usually do with code in CSC108. However, this step by step method can be very exhausting. Nonetheless, I did manage to find a solution this week to finally mange to learn the idea of recursion - at least I hope so.
After lab 7 and 8 - linkedlist, I found a basic technique of using recursion and coding recursion when needed. That is, to follow the basic format of recursion. I use my own sort of algorithm for recursion.
1. Identification
- Recursive structures are fairly easy to identify, sub-problems have the same structure as the overall great problem. So this was quite simple (Examples are fractals or Trees)
2. Coding recursion using the basic idea of:
a) Base case - this line will do something for the base case (summing the lowest leaves of a Tree)
b) Recursive call - This line will make the recursive call if the current arguments are not the base case
3. Believe - I find that the leap of faith is very important. There is no need to trace every recursive call - it is simply annoying and can lead to mistakes. Just take in mind that your base case code will handle the smallest problem, and your identification in step 1 + recursive call in 2b) will handle the rest because if you correctly performed step 1 then your recursive call will work. Every recursive call is the same even if the arguments change because that is what recursion is all about. Using the solution of the smallest problem to solve the biggest problem because they are essentially the same problem.
Recursion is a brilliant idea and it makes coding incredibly efficient. I have often wondered what makes computers incredibly efficient at performing tasks that humans find incredibly difficult. Now I believe I have found one piece that explains the differences between humans and computers. Computers are exceptional at performing the same task over and over again with no mistakes, while humans are not. However, humans are able to adapt different strategies for different problems. In real life, no situation is the same, and thus we will rarely find recursive structures in nature. However, when we categorize the world and store its information into data that have the same structure, computers can use recursion to complete these repetitive, long tasks.
