Wow! It's already the seventh week of the winter term.. how is everyone?
I have midterms in the coming week so I am hard at work. Writing tests are personally not my forte so I tend to double up the effort on assignments and even more so for test preparation.
Before I start this week's SLOG off, I have written a mid-week post on
Object Oriented Programming (OOP) to discuss it in more detail since I had mistakenly not done so for the first assigned topic. Please give that a read if you have the time to and share your thoughts.
Seven weeks into the course, I'm finally comfortable with recursion to talk about it in depth, so let's get started!
How do we use recursion?
When solving a problem by repetitively using the same trick to get closer and closer to the final answer, we are using recursion.
Here is a real-life example of where recursion can be seen:
Imagine you've discovered a small diamond at the beach while going for a walk. Being the super clever person you are, you wonder if there are more undiscovered diamonds around this area. Using a metal detector and a shovel, you dig around the area, trying to uncover more. If there are no diamonds, you look around with the metal detector again and try the next spot. THIS is the example of recursion! You are repetitively doing the same task (shoveling and using the metal detector) in an attempt to get closer to the answer (the precious diamonds). Congratulations if this real-life recursion actually works out for you!
Programming example of recursion:
Perhaps you have a program that runs at different speeds depending on variable X and you'd like your program to run more efficiently. By using different cases of value X and running your program, you could deduce which case will be the most efficient. To do this, simply observe the amount of time it took each case to complete and trace the X value that completed your program in the shortest time. Although this sounds simple on paper, you are recursively calling your program for these different cases until you find the most optimal solution.
Here is a related example of another 148 student testing his functions for different run times:
http://berkeycolortran.wordpress.com/2014/02/15/week-6/
We should do so similarly as we want our program to run optimally by recursively testing various cases of X.
Define a stopping point!
When it comes to coding recursion, it's important to let our program know - "OK, that's enough!". It is super important to find a point where the program will finally stop recursively calling itself, otherwise it will continue on until our computers are out of memory. Some simple stopping points come from using for-loops over an iterable object such as lists, dictionaries and tuples or using conditions such that when the recursive function reaches the condition, it will stop rather than trying to call itself until our computers are out of memory.
A little technical example
As always, it's important to share some code as well. Simply talking about recursion without code isn't very helpful, especially to people who are new to it.
Let's define a function that will count the number of alphabetical objects in a nested list and let's define our list to be:
nested_list = [ 'race', 1, 'car', 2, 3, '4', ['hello!'], [1, ['ace', ['diamonds', 5]]]]
This should return a count of 4. Note that 'hello!' is not an alphabetical object since it has an exclamation mark (!) within the string. 'race', 'car', 'ace', 'diamonds' are all alphabetical.
def count_alpha(x: list) -> int:
"""
Precondition: Items in x must be nested lists or string, integer and float objects.
Returns the number of alphabetical objects inside a list.
"""
count = [ ]
def helper(x: list):
for items in x:
if isinstance(items, list):
helper(items)
else:
if str(items).isalpha():
count.append(1)
helper(x)
return len(count)
Here is what this example does:
- First we defined an empty list count as part of the outer function.
- We have defined an inner function 'helper(x)' so that when we recall our function, count does not get reset to an empty list.
- For the body of helper(x), we utilize a for-loop so the program will stop after it iterates over all the items in list x; as stated above, it's important to define a stopping point for recursive functions.
- The for-loop then iterates over x and if the items inside x happen to be a list, helper(items) is called which will loop through the items within the nested list.
- Finally, if the for-loop happens to iterate through an object that is not a list, it will check if the object is alphabetical with the built-in isalpha().
If this returns True, 1 is appended to count and the function will continue this pattern until the for-loop is completed.
- len(count) is then returned, giving us our final answer.
Let's check our answer in Python Shell!
>>> nested_list = [ 'race', 1, 'car', 2, 3, '4', ['hello!'], [1, ['ace', ['diamonds', 5]]]]
>>> count_alpha(nested_list)
4
Voila!
Learning Recursion
Lastly but most importantly, I wanted to mention that learning recursion can be made MANY times easier by tracing your program on pencil and paper! I have done this for my labs, my assignments and for study material which helped me more than just reading about recursion or playing with recursive functions in Python. Tracing will provide tons of insight and is priceless for anyone interested in recursive functions. Using a visualizer helps as well but pencil and paper has personally been my saving grace.
Thanks for reading my lengthy but hopefully interesting SLOG post on recursion.
I have midterms to study for but do not fret, for I will be back with another post soon! :)
Wish me luck and see you readers later.
