My summary of Recursion!

For this week's blog post I'll be talking about recursion. During the past couple of weeks we've been learning about recursion and discussing different ways on how to implement it. We've learnt how to trace recursive functions, write some basic functions that use recursion, as well as use it within tree structures. I'll first be talking about what recursion is, some examples of ways we've used it within this course, and my experience dealing with it in the course.

In computer science, recursion is a way of thinking in which you break up a larger problem into smaller instances of itself. You will have 1) a base case, something you can easily solve without recursion and 2) a set of rules which reduce all other possible cases towards the base case, which is the recursive portion of the code.

An example would be:

def get_max(l):
    """(int or arbitrarily nested list of int) -> int
   
    Return the maximum element within l.

    >>>get_max(1)
    1
    >>>get_max([1,[2,3]])
    3
    """
    if isinstance(l, list):
        return  max([get_max(x) for x in l])
    else:
        return l

For the first example in the doctest, we see that it is only an integer, so it goes to the else condition and returns its value immediately. This is the base case that doesn't require recursion. For the second example, we see that it is actually a nested list and so therefore it would use the recursion part of the code. It would generate a list in which it would call get_max on each element within the list and then eventually get the maximum value of all of those integers.

-> max([1, get_max([2,3])])
->max([1,3])
->3

In this course, one example of a structure that we've used in this course using recursion is the tree! A tree is essentially a set of nodes can be connected with each other by edges, which connects the parent and child node. An important node is the node at the top of a tree which is called the root. You can access the nodes at the very bottom by recursively calling the children of each node and then calling the children of that node and so on until you get to the very bottom, as each child will have the exact same structure as its parent.

During this course I found recursion to be bit challenging to grasp at first. When we traced the code I was able to understand it as well, but when it actually got to writing the code, I struggled. I didn't really know what I was really doing by constantly calling the function over and over and it often resulted in an infinite loop. When I actually started to think about what I was actually doing by calling it (which is to eventually get smaller and smaller to a particular base case), it started to make a lot more sense.

So that's my post for this week! Hopefully you readers can take something away from my summary on recursion!