How to Convert Recursion to Tail Recursion

Question

Is it always possible to convert a recursion into a tail recursive one?

I am having a hard time converting the following Python function into a tail-recursive one.

def BreakWords(glob):
  """Break a string of characters, glob, into a list of words.

  Args:
    glob: A string of characters to be broken into words if possible.

  Returns:
    List of words if glob can be broken down. List can be empty if glob is ''.
    None if no such break is possible.
  """
  # Base case.
  if len(glob) == 0:
    return []

  # Find a partition.
  for i in xrange(1, len(glob) + 1):
    left = glob[:i]
    if IsWord(left):
      right = glob[i:]
      remaining_words = BreakWords(right)
      if remaining_words is not None:
        return [left] + remaining_words

  return None

Answer 1

I'n not sure if is always the case, but most of recursive functions can be implemented as tail recursives. Besides Tail Recursion is different from Tail Recursion optimization.

Differences Tail Recursion and "Regular" ones

There are two elements that must be present in a recursive function:

1. The recursive call
2. A place to keep count of the return values.

A "regular" recursive function keeps (2) in the stack frame.

The return values in regular recursive function are composed of two types of values:

• Other return values
• Result of the owns function computation

Let's see a example:

def factorial(n):
    if n == 1 return 1
    return n * factorial(n-1)

The frame f(5) "stores" the result of it's own computation (5) and the value of f(4), for example. If i call factorial(5), just before the stack calls begin to colapse, i have:

 [Stack_f(5): return 5 * [Stack_f(4): 4 * [Stack_f(3): 3 * ... [1[1]]

Notice that each stack stores, besides the values i mentioned, the whole scope of the function. So, the memory usage for a recursive function f is O(x), where x is the number of recursive calls i have to made. So, if i needb 1kb of RAM to calculate factorial(1) or factorial(2), i need ~100k to calculate factorial(100), and so on.

A Tail Recursive function put (2) in it's arguments.

In a Tail Recursion, i pass the result of the partial calculations in each recursive frame to the next one using parameters. Let's see our factorial example, Tail Recursive:

def factorial(n):
    def tail_helper(n, acc):
        if n == 1 or n == 2: return acc
        return tail_helper(n-1, acc + n)
return tail_helper(n,0)

Let's look at it's frames in factorial(4):

[Stack f(4, 5): Stack f(3, 20): [Stack f(2,60): [Stack f(1, 120): 120]]]]

See the differences? In "regular" recursive calls the return functions recursively compose the final value. In Tail Recursion they only reference the base case (last one evaluated). We call accumulator the argument that keeps track of the older values.

Recursion Templates

The regular recursive function go as follows:

def regular(n)
    base_case
    computation
    return (result of computation) combined with (regular(n towards base case))

To transform it in a Tail recursion we:

• Introduce a helper function that carries the accumulator
• run the helper function inside the main function, with the accumulator set to the base case.

Look:

def tail(n):
    def helper(n, accumulator):
        if n == base case:
            return accumulator
        computation
        accumulator = computation combined with accumulator
        return helper(n towards base case, accumulator)
    helper(n, base case)

Your example:

I did something like this:

def BreakWords(glob):
    def helper(word, glob, acc_1, acc_2):
        if len(word) == 0 and len(glob) == 0:
            if not acc_1:
                return None
            return acc
        if len(word) == 0:
            word = glob.pop[0]
            acc_2 = 0

        if IsWord(word.substring[:acc_2]):
            acc_1.append(word[:acc_2])
            return helper(word[acc_2 + 1:], glob, acc_1, acc_2 + 1)

        return helper(word[acc_2 + 1:], glob, acc_1, acc_2 + 1)

    return helper("", glob, [], 0)

In order to eliminate the for statement you made, i did my recursive helper function with 2 accumulators. One to store the results, and one to store the position i'm currently trying.

Tail Call optimization

Since no state is being stored on the Non-Border-Cases of the Tail Call stacks, they aren't so important. Some languages/interpreters then substitute the old stack with the new one. So, with no stack frames constraining the number of calls, the Tail Calls behave just like a for-loop.

But unfortunately for you Python isn't one of these cases. You'll get a RunTimeError when the stack gets bigger than 1000. Mr. Guido thinks that the clarity lost to debugging purposes due to Tail Call Optimization (caused by the frames thrown awy) is more important than the feature. That's a shame. Python has so many cool functional stuff, and tail recursion would be great on top of it :/