Skip to main content

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.

Comments

Post a Comment

Popular posts from this blog

Top 5 Books for Language-Specific Interview Questions

Shrunk and White of Programming When you put down that you know a certain programming language or languages on your resume, you are setting certain expectations for the interviewer. I would strongly caution against putting down "expert" in a language unless you invented or are one of the language's maintainers. You are giving your interviewer the license to quiz you on programming language lore. There are a handful of concepts that are considered "standard" knowledge for each language which go broadly beyond syntax and general semantics. These concepts commonly involve major pitfalls in a given language and the idiomatic technique for negotiating these pitfalls and writing efficient and maintainable code. Note, although the concepts are considered idiomatic, you can seldom infer them from knowledge of syntax and semantics alone. The tricky part here is that most courses that teach a particular programming language do not cover these idiomatic techniques and eve…

Complexity Analysis for Interviews, Part 1

This is part 1 of a two part series. Skip over to part 2 you'd like . For coding interviews, we are interested in gauging the asymptotic efficiency of algorithms both in terms of running time and space. The formal study of analysis of algorithms is called complexity theory, a rich field with fascinating and complicated math. For interviews, we only need a few basic concepts. Asymptotic efficiency is concerned with how the running time or memory requirements of an algorithm grows with the input size, so it is intimately concerned with how well algorithms scale to larger inputs. This is important in Computer Science and in practice because whereas some algorithms work well enough for small inputs of say < 10 inputs, the running time and space grows far faster than the input size and thus large inputs of say 10s to millions of inputs becomes impractical (usually meaning taking hours or even years of execution time). Consider sorting. Say for the sake of argument that sorting alg…

Interview Gotchas

It's a challenge to outperform all the other candidates in a competitive tech job only, but there is hope. You can improve your performance with practice and watching out for these gotchas: Make absolutely sure you are solving the right problem: I ran into this the other day. It is entirely a communication issue. When doing an initial screen over the phone, this problem is compounded. For example, maybe an interviewee is hacking out a function that returns the k highest priced products when the interviewer is expecting the kth highest priced product. One can squander a lot of time due to these misunderstandings. A good interviewer will try to guide you back to the right path, but you can't expect this. Be sure to ask questions. Confirm that the input and output are exactly what you expect. Use examples.Don't ever give an interviewer the impression that you are avoiding writing real code. This is an impression thing. This is a coding interview so you should be expecting to…