Week 7: Recursion

For most of the course, we've been covering the concept of recursion, which in a nutshell is the process of calling a method within its own definition.  There's a saying that "in order to understand recursion, you have to first understand recursion," which definitely sounds confusing and maybe even impossible at first.  A recursive method consists of two basic parts: the recursive call and a base case to prevent methods from executing indefinitely; a structure to handle recursion usually takes the form of a simple if-else statement.

For example, a recursive function might look something like this:

    def count(n):

        "Return the depth of n."

        return 1+ max([count(i) for i in n] + [0]) if isinstance(n, list) else 0

In this case, count calls on itself every time the argument is a list and returns 0 otherwise (base case), so for the end result count will return how many lists are in n.

Recursion is an extremely useful technique for programmers to use if they're looking to break the problem up into smaller, similar pieces.  Since programming is naturally supposed to be "lazy," this helps programmers save time and space by reusing a method to get a result.  A recent example I found that demonstrated the importance of recursion the most was A1.  Thinking back to the tour_move method, I realized that with recursion, the method contained around only 10 lines of code and could handle almost any number of cheeses.  It's fascinating to think how the problem presented in A1 could be broken up into smaller parts and as a result be solved quickly in just 10 lines.

We've learned about linked lists in class, which also ties in quite nicely with recursion.  Although I had trouble with writing methods for linked lists using recursion in Lab 6, I grasped the concept and hope to improve on my understanding of recursion in the future.