Week Seven - Recursion

Week Seven - Recursion

Recursion is very powerful programming technique, in recursive functions, the function will call on itself in its function definition (recursive call). Since the function has to stop and return at some point (or else, if the function just keeps calling on itself, a RuntimeError will occur saying maximum recursion depth exceeded ), that point where the function itself is no longer being called is know as the base case. In this sense, recursion is very similar to induction in mathematics.
Recursion works well often when a big problem can be broken into the small version of the same problem. For example, in A1 the way to move cheeses using 3 stools is a recursive function because as long as n is greater than one you will be doing the same moving strategy: first move n-1 cheese to the intermediate and everything to destination. You will be keep calling this function until you get to the case n = 1, where there is only one cheese, then you will simply move this cheese from the source to destination. Recursion is also extremely useful when you want to do operation on a nested list or any other recursive data structure (consist smaller instance of themselves), i.e Trees, LinkedList. In class we did the example that returns the sum of a nested list, the same task can possibly be achieved without recursion, but the code would be much more complicated to write. Recursive structure is also possible to optimize efficiency, for example in the week six lab, we implemented the class Queue using the recursive structure LinkedList. When the Queue is implemented correctly, as described in the handout, when run the testqueue.py it will take the same time no matter how many element is in Queue.  However, when we implemented the class using list, the run time growths and more elements are added.
I also want to also say that although recursion is a powerful method, it should be avoid in some cases:
consider the following methods:
def sum_up_to1(n):
    """
    return the sum from 0 up to n using for loop
    """
    sum = 0
    for i in range (n+1):
        sum += i
    return sum
        
def sum_up_to2(n):
    """
    return the sum from 0 up to n using recursion
    """    
    if n == 1:
        return n
    return n + sum_up_to2(n-1)
I used a timer to test the efficiency of those two functions. To add up to 500, the first method took 0.0s while the second one took  0.000999927520751953s. One thing really interesting is when I did sum_up_to2(1000) it raised a RuntimeError saying the maximum recursion depth exceeded in comparison, while sum_up_to1 still took 0 second. I think it is because you need to call on the function too many times to get to the base case, and the computer just ran out of space. So, if there is not a nested structure and loops can be easily applied, you might not want to use recursion, as it might takes much longer as shown in the example above