Recursion Analysis

Note for the reader: A lot of assumptions were made regarding the runtime of functions involving lists and strings. The actual runtime of these functions may even vary between different versions of python and vary even more when implemented on different programming languages. Runtimes for these were labeled as generic functions up until keeping them that way would complicate the result.

Review of Recursion

A recursive function is a function defined using itself. It is often a technique used when a problem can be solved by solving itself with a different input.

Let's look at an application using the Factorial Function. The factorial of \(n\) is defined as the product of all positive integers less than or equal to \(n\):

\[ n! = n \times (n-1) \times (n-2) \times \ldots \times 2 \times 1 \]

Notice how the factors after \(n\) can be rewritten as \((n-1)!\), and thus:

\[ n! = n \times (n-1)! \]

Which is now a function defined by the result of the same function with a smaller input and we can now write this as a recursive function:

def factorial (n):
  return n * factorial(n-1)
  
print(factorial(10)) # Print out 10!

Wait a minute, the code doesn't work?! We may have forgotten something. Our recursive function will continue to call itself indefinitely. Thus, we need to introduce a stop condition or what we call the base case. For the factorial function this is when \(n\) reaches \(1\) and the only positive integer less than or equal to it is itself. Using this, we can now properly end the recursion and actually compute the factorial:

def factorial (n):
  if n > 1:
    return n * factorial(n-1)
  return 1  # No need for 'else' statement

print(factorial(10)) # Print out 10!

Time Complexity

Recurrence Relation

Similar to how we define the function with itself, the running time, \(T(n)\), of a recursive function or algorithm is defined with itself as well. This is called a recurrence relation. As an example, let's try and formulate the recurrence relation of the factorial function defined above:
\[ T(n) = \begin{cases} T(n-1) + c_1 & n > 1 \\ c_2 & n \leq 1 \\ \end{cases} \]
When \(n > 1\), \(T(n)\) is equal to the runtime of factorial(n-1) plus the constant runtime of the other operations which are the multiplication, evaluation of the conditional, and calling and returning between functions which is lumped into a constant \(c_1\). Then, the runtime is also constant for the base case. Using the recurrence relation, there are several ways to get the time complexity.

Substitution Method

For this method, we look for a pattern when we try to expand the recurrence relation and try to rewrite the recurrence relation without the \(T(n-1)\) term. Let's try expanding the recurrence relation for the factorial function above:

\begin{aligned} T(n) = T(n-1) + c_1, & \quad \rm starting \space point \\ T(n) = [T(n-2) + c_1] + c_1, & \quad {\rm expanding \space} T(n-1) \\ T(n) = T(n-2) + 2c_1, & \quad {\rm combining \space} c_1 {\rm \space terms} \\ T(n) = [T(n-3) + c_1] + 2c_1, & \quad {\rm expanding \space} T(n-2) \\ T(n) = T(n-3) + 3c_1, & \quad {\rm combining \space} c_1 {\rm \space terms} \\ T(n) = T(n-4) + 4c_1, & \quad {\rm expanding \space} T(n-3) \\ T(n) = T(n-5) + 5c_1, & \quad {\rm expanding \space} T(n-4) \\ \end{aligned}

Notice that whatever is subtracted to the \(n\) term inside the recursive call is multiplied to the \(c_1\) term. We can substitute \(k\) in lieu of this constant, and thus we can rewrite the recurrence relation as:

\[ T(n) = T(n-k) + kc_1\]

Note that this can be proven through induction but that is left as an exercise for some other time. Next, recall that when \(n=1\), \(T(n)\) simplifies to \(c_2\). So if we let \(k=n-1\):

\[ T(n) = T(n-(n-1)) + (n-1)c_1 = T(1) + (n-1)c_1 \]
\[ T(n) = c_2 + (n-1)c_1 \]

Lastly, we get the asymptotic \(O(n)\):

\[ O(T(n)) = O(c_2 + nc_1 - c_1) = n \]

Recursion Tree Method

This is a more visual approach wherein we look at a recursive algorithm as a tree that branches out depending on the recurrence relation. Let us consider the recursive function below, binary(n), which prints all the n-digit binary numbers:

def binary(n, b=""):
  if n > 0:
    binary(n-1, b + "0")
    binary(n-1, b + "1")
  else:
    print(b)

Note that all n-digit binary numbers are composed of a n-1-digit number appended with either 1 or 0. This is equivalent to the two recursive calls binary (n-1, b + "0") and binary(n-1, b + "1"). The argument b acts as a temporary storage

The recurrence relation of the function can be expressed as:
\[ T(n) = \begin{cases} 2\times T(n-1) + f(n) & n > 0 \\ g(x) & n \leq 0 \\ \end{cases} \]

where \(f(n)\) is the runtime of all other non-recursive instructions (i.e. evaluating the conditional, concatenation strings) and \(g(n)\) is the runtime of the base case (i.e. printing a string with x characters). The substitution method is still applicable but this section is not about that method so that can be done at another time.

A recursion tree is basically a graphical way of expanding the recurrence relation:

In the final form of the tree, only the \(f\) and \(g\) terms remain since all the recursive calls have been 'expanded'. To get the time complexity from the recursion tree, we just need to add all of the terms, which looks easier said than done at this point.

I would help to put labels depending on how deep a node is in the recursion tree like so:

This way, we can first determine the total runtime per level, which should be easier, before getting the total runtime. For level \(0\), we get that the total runtime is:

\[ T_{0} = f(n)\]

For the succeeding level \(1\) we get:

\[ T_{1} = 2\times f(n-1)\]

Then for level \(2\):

\[ T_{2} = 4\times f(n-2)\]

We should probably notice a pattern for the per-level subtotal runtime:

\[ T_{k} = 2^{k}\times f(n-k)\]

Which we can confirm by plugging in \(k = 3\) and verifying the result from the tree. At this point, it would be pretty difficult to proceed without knowing the actual expression for \(f\). For the purposes of this discussion, we assume that \(f(n) = c\) or a constant operation. Thus, we can compute the total runtime as:

\[ T(n) = \left[\sum_{k = 0}^{d-1} \left( 2^{k}\times c \right) \right] + \left[2^{d} \times g(x)\right] \]

Notice that we have a special case for the last level \(\left(d\right)\) which is multiplied to \(g(n)\) instead. This \(d\) is also referred to as the depth of the recursion which is sometiems used outside of complexity analysis as well.

Finding \(d\) can also be done in multiple ways. One of the simplest ways is to deduce it based on our observations of the recurrence tree as well. The total runtime for level \(d-1\) based on our equation above is:

\[ T_{d-1} = 2^{d-1}\times f(n-(d-1))\]

But, from the tree itself, we know that level \(d-1\) is made up of \(f(1)\) terms only. Thus:

\[ n-(d-1) = 1 \rightarrow d = n \]

Substituting this back to \(T(n)\) we get:

\[ T(n) = \left[ \left(2^{n} -1 \right) \times c \right] + \left[ 2^{n} \times g(x) \right] \]

Note that:
\[ \sum_{k = 0}^{n-1} \left( 2^{k}\times c \right) = \left(2^{n} -1 \right) \times c \]

Assuming \(g(x)\) is linear or \(O(g(x)) = n\), the worst case time complexity of binary(n) would be:

\[ O(T(n)) = O(2^{n} - 1 + 2^{n} \times n) = n 2^{n} \]

Auxiliary Space Complexity

Auxiliary space or also known as stack depth is the additional program stack memory needed by the function or algorithm denoted as \(M(n)\). Auxiliary space complexity describes the growth rate of the needed auxiliary space of the program or algorithm. Similar to time complexity, the various asymptotic notations are considered for this (\(\Omega\), \(\Theta\), big-\(O\)) and the analysis is similar as well.

So far, you may have only encountered programs and algorithms which require a constant amount of space to store temporary variables and counters. Thus, the space complexities of these functions are most likely constant or \(\Theta(M(n)) = \Theta(1)\). However, for recursive functions, the function itself is called multiple times, and thus multiple copies of the function are stored in the program stack. As an example, below is a visualization of how the program stack fills up when we run factorial(5):

With factorial(5) the factorial is called \(5\) times, and we can even predict that calling factorial(n) would mean factorial would be called \(n\) times. Since the function itself has a constant space complexity, we can say that the auxiliary space complexity is linear with respect to \(n\) or \(O(M(n)) = n\)

However, simply counting the number function calls isn't exactly correct. Let's look at the visualization of the program stack when we call binary(3):

As you can see, not all the function calls appear at the stack at the same time and this is true for most recursive functions. When binary(0) is reached, the function returns and frees up some space before binary(1) makes another function call. Thus, we can generalize that the functions in a 'path' from the topmost level (binary(n)) to the deepest level (binary(0)) would be the most memory needed by a recursive function as shown here:

\(c_{1}\) is the memory needed to store the function itself in memory and \(c_{2}\) is the memory needed to store one character in a string which is used as a function argument. Knowing that there are at most \(d\) functions in the call stack, the total memory needed can be computed as:

\[ M(n) = d\times c_{1} + \left[\sum_{k = 0}^{d} \left( k \times c_2 \right) \right] = \]

We already know that \(d = n\) and that the second term is just the sum of integers from \(0\) to \(n\). Thus, the space complexity of binary(n) is:

\[ O(M(n)) = O\left(n + \frac{n(n+1)}{2}\right) = O(n^2) \]

Recursion vs Iteration

Comparing Complexities

Program stack limitations put recursive functions at a disadvantage. Consider an iterative version of factorial(n) below:

def factorial_i(n):
  f = 1
  for i in range(n):
    f *= i+1
  return f

print(factorial_i(10)) # Print out 10!
print(factorial(10))   # Original result

The iterative version features a for loop with iterations equal to \(n\) so this version would also have a linear or \(O(n)\) time complexity. However, the iterative function only has a constant space complexity which makes it far more superior to the recursive version.

So recursion made it worse? For making a function that calculates the factorial of a number, that would be a yes. However, this would not be true for all recursive functions. Suppose we want to implement binary(n) in an iterative way:

def binary_i(n):    # O(n) = O(n * len(all))
  all = [""]
  for i in range(n):  # O(n) = O(n * len(t))
    t = []
    for b in all:       # O(n) = O(len(all))
      t.append(b + "0")   # O(n) = O(f(t, b)) = O(1)
      t.append(b + "1")   # O(n) = O(f(t, b)) = O(1)
    all = t             # O(T(n)) = O(len(t))

  for a in all:       # O(n) = O(len(all) * n)
    print(a)            # O(n) = O(len(a)) = O(n)

binary_i(3)

Assuming the array all would contain all the binary numbers with i digits during the end of each iteration, the inner for loop would then append either 1 or 0 to generate all the i+1-digit binary numbers for the i+1th iteration, making it function similarly to our previous recursive implementation. You can see in the comments the time complexity analysis of each line.

Iterative time complexity

Starting with the innermost append commands, these are actually two commands in a single line where the runtime can be temporarily labeled as f(t, b). The loop containing this iterates depending on the number of elements in all. Assuming that f(t, b) is constant or O(1), the inner loop would then have a complexity dependent on the length of all or O(len(all)). The all = t command copies the contents of t to all and would scale linearly with the lenght of t so that line is O(len(t)). This brings the time complexity of the outerloop to be O(n * len(all)) considering that the len(t) and len(all) are equal after every loop iteration. Meanwhile, at the end of the function is a loop that prints all the results. Assuming the runtime of the print operation takes longer when the printed string gets longer, this loop overall would have a O(len(all) * len(a)) time complexity. However, we know we are printing n-digit binary numbers so len(a) = n which means the loop is O(n*len(all)). We know all would contain, in the final loop iteration, \(2^{n}\) elements since that is how many n-digit binary numbers exist.

So, (tl;dr) binary_i(n) is also \(O(n2^{n})\) like the original recursive binary(n).

So which is actually better?

Looking at the space complexity, binary_i(n) uses a temporary list t to store the i-digit numbers at the end of each loop. At the last iteration, t would contain \(2^{n-1}\) elements with each element being an n-1-digit number which means a \(O(M(n))= O(n2^{n})\) of additional space on the last iteration. If we just needed to print these numbers, then the original binary(n) with a quadractic or \(O(n^2)\) memory complexity is significantly better.

Backtracking

So it looks like the recursive binary(n) function was able to utilize the way the program stack works to actually use less memory than needed compared to an iterative approach. This was done through what is commonly referred to as backtracking. Backtracking is being able to undo your last action and do something else instead.

For the binary(n) function, we can consider adding a 1 or a 0 to be one action. The function first adds only 0's to generate the first n-digit number (00...00). When the final binary() function call terminates, the previous function call resumes, effectively causing a backtracks. This removes the last 0 and adds 1 instead (00...01). This would then terminate the last 2 function calls making the program backtrack twice, add a 1 instead, and the process repeats for the last digit as well.

Backtracking effectively modifies a currently existing 'solution' to look for another 'solution' instead of creating another 'solution' from scratch, or, in the case of binary_i(n), storing all the partial solutions in a list which increased space complexity. Because of the program stack, an 'action' is automatically undone when a function terminates and a different 'action' or function call can be made to explore another 'solution'.

Code Readability

While recursive functions seem very complex, they could potentially be the simpler choice in the correct applications. Sometimes, recursive functions can even 'translate' more easily to spoken language.

Consider binary(n) and binary_i(n). In binary(n), knowing that adding either 1 or 0 at the end of all n-1 digit numbers would result to all the n-digit numbers and that can be precisely seen in the code. On the other hand, binary_i(n) essentially does the same but with extra steps like temporary storage and nested for loops. While this may not be the best iterative implementation of the binary(n) function, needing to come up with a different approach is still an additional challenge.

Summary

Recursive functions are functions which call themselves and are especially helpful when a problem can be solved with a smaller version of itself. Getting the time complexity of a recursive function always starts with the recurrence relation which would probably have the form:

\[ T(n) = \begin{cases} T(h_{1}(n)) + T(h_{2}(n)) + \ldots + f(n) & n > y \\ g(x) & n \leq y \\ \end{cases} \]

where \(h_{i}(n)\) would describe how the input \(n\) is modified for each recursive call in the function (i.e. for binary(n) there were two recursive calls that modified the input the same way: \(h_{1}(n) = h_{2}(n) = n-1\)), \(f(n)\) describes the runtime of the non-recursive function calls and commands, \(g(x)\) is the runtime of the base case which could be a function of different paramaters, and \(y\) indicates when the base case occurs. The recurrence relation can be solved in multiple ways:

A. Substitution Method

1. Expand the recurrence relation to find a pattern which can generalize the equation with a variable (usually \(k\)).
2. Find an expression for \(k\) using the base case.
3. Substitute the expression found to the general equation in step 1 and simplify.

B. Recursion Tree Method

1. Generate the recursion tree by expanding the recurrence relation.
2. Formulate an expression for the total runtime per level of the tree.
3. Find the depth of the recursion tree.
4. Use the depth and runtime per level to create an expression for the total runtime.

Recursion uses additional space since functions do not finish until the base case is reached. Space complexity is computed similarly to time complexity using the recursion tree method where the memory needed for each function call is considered instead of the runtime. However, only the 'deepest' path from the initial function call to one of the base cases is considered since memory is freed up when a function terminates.

Additional space used by recursion may even be beneficial when used correctly for the right application. Even though there are some additional considerations when using recursive functions, they would often be the best solution to several problems that are can be broken down to simpler versions of themselves.

References

• Cormen, T., Leiserson, C., Rivest, R. and Stein, C., 2009. Introduction to Algorithms. Cambridge (Inglaterra): Mit Press.