Week 7: Recursion

What is recursion you might ask. Well, to think about it visually, if you place a mirror in front of another mirror, both facing eachother, you would get an infinite amount of reflections. The reflection of one mirror, essentially reflects itself, reflecting itself, reflecting itself and so on... If we take that logic, and use it with computer science and math, we can do all sorts of wonderful things.

Let's say we wanted to write a function to evaluate the factorial of a given number:

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)

When you give an n value, it will start to check if it is 0, otherwise known as the base case, where it returns a static value and not a recursive one. If  is not 0, it will multiply it by the factorial function of n - 1. What this does is repeatedly do the function to retrieve values until we hit the base case. In this case, we ca determine 4! = 4 * 3! = 4 * 3 * 2! = 4 * 3* 2 * 1! = 4 * 3 * 2 * 1 * 1 = 24. You have to make sure you have the base case or else the function will recurs infinitely.

So now that I've briefly talked about what recursion is and an example of how it works I guess I can get to my experience with it. I first encountered recursion in my grade 11 computer science class where we were learning C++. Every student had to pick a topic in computer science and give a brief talk on what it is and how to do it. Of course most people pick a topic that suits there likes and is easy for them. We had some simple topics like reading/writing to a file, creating a GUI, I did some game design and graphics. And then easily the smartest kid in the class goes up, and talks about recursion and trees. Every student is both amazed and completely confused at the topic. Barely anyone can code it from nothing or even comprehend it. Heck, I could barely even understand what he was saying. He goes to talk about the practicality of it and its uses, I'm just sitting there thinking that any example he was doing could be done in another way. He asks us to code a function to find the greatest common divisor of two numbers. I figure yeah I could easily do this, and I wrote something similar to this, only with C++ syntax instead:

def GCD(x, y):

    num = []

    for n in range(1,max(x,y)+1):

        if x % n == 0 and y % n == 0:

            num.append(n)

    return max(num)

I figure "yeah, I did that fast, and it looks efficient, there's no way you can do this better." Then he shows this:

def GCD_recurs(x, y):

    if (0 == x % y):

        return y

    return GCD_recurs(y, x%y) 

HOW'D HE DO THAT! That was genius. I would have never thought of that. Since that moment. Recursion has always puzzled me on how to know what to do. I still have trouble, in class and in the assignments on knowing what to recurs. 

So that is my experience with recursion, a both lovely and infuriating topic, I both hope to use it forever and never use it again.