Codepanda vs. Recursion

Recursion and I met several years back. We did not get a very good first impression of each other and ultimately decided it would be best to go our separate ways. Time went by and our relationship dissolved into nothing. That is until we suddenly bumped into each other in CSC148 this semester. Talk about awkward....

The problem I had with recursion was that it could not be traced like for loops or while loops. When I first encountered it, recursion was explained in an extremely confusing way. Apparently a way that humans should not learn it. Throughout the past month I attempted to relearn recursion and I think I have gotten the basic idea of it.

Recursion is basically observed as a function calling itself. You can see how this ties in with the idea of looping. Programs that are recursively implemented can often be written with regular loops. However, the power of recursion lies in the efficiency it provides for the program. Code written to solve a problem recursively will run faster than code that solves the same problem with a loop.

There are two components to the basic recursive function: the confusing, self-calling function part and the base case.

The base case is what you want the function to do when the simplest, most basic argument is passed in. For example, if you want to determine the sum of the values in a nested list, the base case would be the function's behavior when a flat list is given. If you wanted the function to calculate a number's factorial, the base case would be evaluating 1! (exclamation mark = factorial symbol, still using my indoor slogging voice).

The recursive part is used when the function is called with a more complicated argument. The function essentially breaks down the problem into smaller parts until it reaches the simplest problem which is the base case that it knows how to evaluate. Then it retraces its steps and fills in what it knows in order to give an answer to the original argument inputted.

The basic structure of recursive code is:

def function(arg):
        if base case:
                evaluate to this
        else:
                evaluate something with call to function(with_some_arg)

Whether the base case/recursive part are under the if or under the else clause is arbitrary.

The base case is very important since it tells the function when to stop recursing. Without the base case, the function will endlessly run the recursive call until python runs out of memory and leaves.

Here is a great example of a recursive function and how it works -> great example