Week 5: Tracing a recursive function

Like with many other things, it takes time and practice to master recursion. Thankfully we have a technique at our disposal which makes learning recursion easier. This technique is referred to as “recursive tracing”.

Tracing a call to a recursive function is a great way to understand how the recursive function behaves, and inevitably when errors crop up, it’s also a good way to troubleshoot and fix bugs.

Winding and unwinding recursion

When tracing most recursive functions, there are 2 phases that occur one after the other.

First we have the winding phase, which occurs at every level of recursion. It occurs every time subsequent calls to a recursive function (usually the same function) are made. The winding phase will continue until it reaches a dead end, a point which is referred to as the “base case”. The base case is a condition in which further recursive calls are not necessary.

The unwinding phase occurs when the base case condition has been satisfied. It is at this point the recursive process travels back up the recursive levels and returns some final value.

Winding and unwinding is not something native to only recursive functions. We’ve seen this occur with many ordinary functions. Suppose that a function a() makes a call to function b(), which inturn makes a call to function c(). Once function c() has done it’s job, what happens next? It goes back to b() and then a(). So we can think of going from a() → b() → c() as the winding and back from c() → b() → a() as the unwinding.

How to trace a recursive function

Let’s say that we wanted to implement a recursive function called check_for_occurance that checks for the occurrence of some object within a list and returns a boolean value. Object and list are arguments of our function.

Here’s the code for our function:

def check_for_occurance(obj, lst):

   '''(Obj, list) -> Bool

   

   Return True if obj exists in lst (the 1st occurrence of obj), otherwise return False.

   

   >>> check_for_occurance(1, [0])

   False

   >>> check_for_occurance(1, [0, [1]])

   True

   '''

   

   index = 0

   

   # Base case: Is obj in lst?

   found_obj = obj in lst

   

   while not found_obj and index < len(lst):

       

       # General case: Iterate through lst and recurse on item that is itself a list

       if isinstance(lst[index], list):

           found_obj = check_for_occurance(obj, lst[index])

       index += 1

       

   return found_obj

Note: In our implementation we rely on the python ‘in’ operator to do a check for an item in a list. However, it does so only on the first level of a parent list. It ignores nested child lists.

To understand how check_for_instance works, we begin by tracing a simple example and then work our way up to a more complex example.

Simple tracing example

check_for_occurance(1, [0]) → False

In the simple example we see that the list has only one level and therefore does not require any recursive calls. Also, we can see that the integer 1 is not in the list so the function returns False.

Slightly more complicated tracing example

check_for_occurance(1, [0, [1]]) → check_for_occurance(1, [1]) → True

In the slightly more complicated example, the list has two levels. The first level does not contain a 1, but it does contain another child list (the second level) so we need to make a recursive call on the child list. Lo and behold the child list does contain a 1 so we expect to have True returned.

So to conclude then, by tracing out the recursive calls to check_for_occurance we’re able to see what is happening at each of level of it’s recursion and what the return value should be.