you may ask yourself what the hell is this recursion he talks about? Well Recursion is a method of solving problems that involves breaking a problem down into smaller and smaller increments (subproblems) until you get to a small enough task that it can be to accomplished. Recursion involves a function calling itself. As opposed to iteration using for or while loops. You’re probably now thinking when would I use recursion? While it may not seem like much off the bat, recursion allows us to write efficient algorithms with much less code to solve problems that may otherwise be very difficult to program or even impossible. There are 3 rules of recursive functions:
- A recursive function must have a base case (when to stop)
- A recursive function must change its state and move toward the base case. (series of simplifications)
- A recursive function must call itself, recursively
In simpler terms recursion is “defining a problem in terms of itself”. Recursive calls solve smaller problems of the same “flavour” and then combine those solutions to get the solution to the main problem.
For example lets consider at taking the sum of a list of integers.
def sum_list(lst: list)-> int: """ >>>sum_list([1,3,5,7,9]) 25 """ total = 0 for i in lst: total += i return total
I’ve broken down the step the non-recursive algorithm performs
total= (1+(3+(5+(7+9)))) total= (1+(3+(5+16))) total= (1+(3+21)) total= (1+24) total= 25 Now I can solve the same problem with a recursive algorithm.
def sum_list(numlst: list)-> int: """ >>> sum_list([1,3,5,7,9]) 25 """ #base case one item in the list if len(numlst) == 0: return numlst else: return numlst + sum_list(numlst[1:]) """ Now I can get really fancy on you and make it even more elegant looking using list comprehension! #AlphaStatus """ def sum_list(lst: int)-> int: """ >>>sum_list([1,3,5,7,9]) 25 """ return sum([sum_list(i) if isinstance(i, list) else i for i in lst])
We didn’t need recursion for that did we? But we could use it anyways! It’s important to remember that recursion is simply a different method to coding an algorithm. Some functions don’t even need recursion, such as this one above. However, with that being said a recursive approach comes in very handy (is useful) for a programmer who need to develop much more complex problems like the 4 stool Tower of Hanoi I wrote the algorithm for a few weeks ago. Some programmers may choose a recursive approach because it is just easier for them to understand, while some algorithms just go hand in hand with recursion because of the way they are designed such as traversing a tree like structure which we learned about in class last week. Recursion is a very puzzling concept to understood at first it took me hours of practice coding to finally feel comfortable implementing it.
“The human cost of writing, and maintaining, an algorithm that is naturally recursive in an iterative form is far higher than any cost a particular compiler or interpreter might add for running recursive functions.” – Danny Heap
Professor Heap taught he that you gotta just trust the recursive calls works after tracing the simple cases. I would say the hardest part of the problem is recognizing a recursive pattern. The wonderful thing it is that you can use it in almost any language!
its been another great week in the life of a Computer Science Major! Stay Hungry, Stay Foolish!
yours truly, – “CodeShark”