Week 7: Running with Recursion

The goal of this week is to provide an intro into recursion: this includes what it is, when we use it and why we use it.  We will look at what recursion is first.  Recursion is a programming technique in which a function or method repeatedly calls itself in its body so that it can break down a large, complex task into smaller, simpler instances of the same task.    We will introduce two ways to understand recursion.  One is by its components.

(1)    Base Case:  This component determines if the recursive function is given a trivial task to complete.  If the task is trivial, then the function will not call itself.  If a function is given a complex task, then this component lets it know when it should stop calling itself.

(2)    Recursive Step:  This component is where function calls itself.  Every time the function calls itself, it gives a portion of a complex task to another instance of itself to complete.  The function continues dividing the work until it reaches the base case.

(3)     Work:  This component uses the solution from a simpler instance of the task to help it complete a current, more complex instance of the same task.

We can illustrate what the components look like with an example.  Assume that we have to return every number in a possibly nested list in a new empty list.  Then the recursive function, with every one of the components commented in the body of the code, looks like:

def collect_num(L: list) -> list:

            ‘’’

            Return a new list in which every element of new list is a number in L.

            L.

            ‘’’

            new_L = []

            for x in L:

                        if isinstance(x, int) or isinstance(x, float):

                                    new_L.append(x)

# The base case is the if statement.  If x is a number, then the function can append it to new_L without any additional work.

                       

                        elif isinstance(x, list):

                                    new_L = new_L + collect_num(x)

# The recursive step is collect_num(x).  This step executes if x is a list because there exists a chance that there are numbers in x.

# The work component is when new_L is concatenated with the return value of collect_num(x).

           

            return new_L

In addition to understanding recursion by its components, another way to understand it is by comparing its design to that of a mathematical proof by induction.  Mathematical statements that are provable by induction are generally in the form of for every n that is an element of the set of natural numbers, S(n) where the proof of S(1) is called the base case.  We can think of the base case in induction as parallel to that of the base case in recursion because of their easiness to work out.  To us as human beings, the base case in induction is generally the most trivial instance of the statement to prove.  To the recursive function, the base case represents the most trivial task that it can complete.  Likewise, the inductive step of mathematical induction also has its parallel in recursion.  When we assume that for every k that is an element of the set of natural numbers, S(k) is true, we use that assumption to prove that S(k + 1) is true.  Similarly, when the recursive function has a solution for a simpler instance of a task, it uses that solution to complete a more complex instance of the same task.  As a result, there are two possible ways to understand recursion; one is through an analysis of its components and another is through its comparison to that of a mathematical proof by induction.

        The reason why we use recursion is that it is a more efficient for completing complex tasks.  The alternative to a recursive function is a function that only uses iteration.  Iteration with for loops and while loops is best for functions that complete simpler tasks.  For example, assume that we have to multiply the elements in a list of numbers.  Compare the function that only uses iteration to the function that uses recursion:

def multiply_elements(L: list) -> None:

            ‘’’

            Return the result of every element in L multiplied with each other.

            ‘’’

           

            m = 1

           

            for x in L:

                        m = m * x

           

            return m

def recursive_multiply(L: list) -> None:

            ‘’’

            Return the result of every element in L multiplied with each other.

            ‘’’

            if len(L) == 0:

                        return 1

            return L[0] * recursive_multiply(L[1:])

Recursion for this task is unnecessary because the task is already at its most trivial form.  For the task of collecting every number in a possibly nested list however, recursion is the most natural solution.  In that scenario, an iterative solution will most likely result in a hideously complicated function.  Therefore, as a general rule of thumb, recursion should be used in complex tasks that can be broken down into simpler instances of the same task.  If the task is already at its simplest form, then iteration is the best solution.