Tail Recursion and Iteration

In the last session on linked list problems, we went over how to take a recursive function and transform the recursive call into a tail recursive one. The reason we do this is because tail recursive calls can be fairly straightforwardly optimized into a loop (and often automatically by a suitable compiler), thus removing any overhead from the recursive call. Regular recursive calls can get expensive in terms of space complexity if the recursion call stack gets deep, because the program needs to store information about the context for each recursive call. Recursion is a powerful tool of abstraction like any other. Functions on recursive data structures such as trees and linked lists lend themselves naturally to recursive solutions, and may be more readable and maintainable than their iterative counterparts. Thus, it is an important and even foundational concept to master.

General Recursion

The example we used was the reverse function which reverses a singly linked list. The straightforward recursive solution is the following:

def reverse(n):
  return append(reverse(n.next), Node(n.key))

The above gets the job done but takes O(n) allocations and traversal cost for the append for O(n^2) running time. The recursive call stack will cost O(n) for space. The recursive call to reverse is not in tail position, where tail position means that the recursive call is the last thing the recursive function does. In particular, after we do the recursive call, we'll have to construct the Node at the end and call the append function. It is because there are these two things we must do after the recursive call that this function cannot be easily transformed into a loop. This also entails the need to keep around context of the call stack, i.e., that we need to do the construct and append after the recursive call returns, which adds to the expense in terms of space.

Tail Recursion

To rewrite this function in terms of a tail call, we need to introduce one or more accumulator arguments. For the purposes of reverse, a single accumulator is sufficient, but in general, you may need more if you are keeping context for multiple recursive calls. Call this accumulator argument acc. Intuitively, our new reverse function, dubbed revTail, has two arguments, one (n from before) is the part of the list we have yet to reverse and the other, acc, is the part of the list that we've already reversed. The base case for the tail recursive function is that case where n is null, in which case we are done and just return acc, the reversed list. In the other case where n is non-null, we save the n.next in a temp variable and set the new n.next = acc. Why? Because given the front part of the list already in reverse order, we stick the current node in front of that to take one more step in reversing the whole list. Now to continue reversing the rest of the list, we past temp as the n (i.e., current node) for the next recursive call.

def revTail(n, acc):
  if (n is None): return acc
  temp = n.next
  n.next = acc
  return revTail(temp, n) 

To complete this, we need a stub function to call revTail with the appropriate initial value for acc, which would be null since when we are starting out, the part of the list that has been reversed is null.

def rev(n):
  return revTail(n, None)

Tail Call Optimization: Replacing Tail Calls with Iteration

The above tail recursive function can be mechanically converted into an iterative implementation by making the renaming of the variables implicit in the recursive call explicit:

def revIter(n):
  acc = []
  while(n is not None):
    temp = n.next
    n.next = acc
    n = temp
    tail = n
  return acc

In both the tail recursive and iterative implementations, we have an efficient implementation that takes O(n) time and O(1) space.