Lazy Trampolining

A couple of epsiodes ago, I showed how you can avoid stack overflow in certain kinds of recursive function using a technique called trampolining. Just mentioning such a word made me feel out of breath, so I went on to develop a technique that I've called lazy trampolining, or lazy recursion.

The idea is to combine the trampoline that I created last time with an Iterator. This allows you to create functions that return a result at each iteration before recursing. Because it uses an Iterator, and Iterators are Lazy, you get to decide how long the recursion should carry on for. I'm still trying to work out how valuable this idea is, but since I've already come up with a couple of practical uses, I figured it would be worth sharing with the world.

The simplest example I've come up with so far is a Fibonacci sequence generator. You may remember that we defined one for Project Euler Problem 2 that used a while loop. Here's an equivalent generator using my Lazy Trampoline:

public static IEnumerable<int> FibonacciTerms(int a, int b)
{
   var recursiveFibonacciFunction = Trampoline.MakeLazyTrampoline((int x, int y) =>
                Trampoline.YieldAndRecurse(x + y, y, x + y)
                );

  return recursiveFibonacciFunction(a, b);
}

You can see that I'm calling the Trampoline.YieldAndRecurse method to indicate what I want to happen in the next iteration. I pass first the result from the current iteration that I want included in the output sequence, then I specify the parameters to be used for the next recursive call.

Now for a slightly longer example. I've taken the algorithm that I had for finding the largest prime factor of a number, and modified it so that it returns all the factors of the number as a sequence. In each iteration of the function, a new factor is found, and this is returned as a PrimeFactor object which contains both the prime number, and its multiplicity (how many times the factor divides into the target number).

        private static IEnumerable<PrimeFactor> PrimeFactors(long prime)
        {
            var function = Trampoline.MakeLazyTrampoline((long previousPrime, long remainder) =>
                {
                    // find next factor of number
                    long nextFactor = (previousPrime + 1).To(remainder)
                        .SkipWhile(x => remainder % x > 0)
                        .FirstOrDefault();

                    if (nextFactor == remainder)
                    {
                        return Trampoline.YieldBreak<long, long, PrimeFactor>(new PrimeFactor { Prime = remainder, Multiplicity = 1 });
                    }
                    else
                    {
                        // find its multiplicity
                        long multiplicity = Enumerable.Range(1, Int32.MaxValue)
                            .TakeWhile(x => remainder % (long)Math.Pow(nextFactor, x) == 0).Last();
                        long quotient = remainder / (long)Math.Pow(nextFactor, multiplicity);

                        PrimeFactor nextPrimeFactor = new PrimeFactor { Prime = nextFactor, Multiplicity = multiplicity };

                        if (quotient == 1)
                        {
                            return Trampoline.YieldBreak<long, long, PrimeFactor>(nextPrimeFactor);
                        }
                        else
                        {
                            return Trampoline.YieldAndRecurse<long, long, PrimeFactor>(nextPrimeFactor, nextFactor, quotient);
                        }
                    }
                }
                );

            return function(1, prime);
        }

Here I use the YieldBreak method: this is used to return one final result, and then terminate the recursion. In the code shown below, I've also included a YieldBreak method that just terminates without returning a final result.

This Lazy Trampoline technique appears to me to be a generalisation of the Unfold operation that we discussed last time. Unfold generates a sequence, but at each iteration you're only given the previous item in the sequence from which to generate the next item. With this technique, you get to decide what parameters to pass through to the next iteration.

This is what the code for the Lazy Trampoline looks like.

public static class Trampoline
{

    public static Func<T1, T2, IEnumerable<TResult>> MakeLazyTrampoline<T1, T2, TResult>(this Func<T1, T2, Bounce<T1, T2, TResult>> function)
    {
        return (T1 param1, T2 param2) => LazyTrampoline(function, param1, param2);
    }

    private static IEnumerable<TResult> LazyTrampoline<T1, T2, TResult>(Func<T1, T2, Bounce<T1, T2, TResult>> function, T1 param1, T2 param2)
    {
        T1 currentParam1 = param1;
        T2 currentParam2 = param2;

        while (true)
        {
            Bounce<T1, T2, TResult> result = function(currentParam1, currentParam2);

            if (result.HasResult)
            {
                yield return result.Result;
            }

            if (!result.Recurse)
            {
                yield break;
            }

            currentParam1 = result.Param1;
            currentParam2 = result.Param2;
        }
    }

    public static Bounce<T1, T2, TResult> YieldAndRecurse<T1, T2, TResult>(TResult result, T1 arg1, T2 arg2)
    {
        return new Bounce<T1, T2, TResult>(arg1, arg2, result);
    }

    public static Bounce<T1, T2, TResult> YieldBreak<T1, T2, TResult>()
    {
        return new Bounce<T1, T2, TResult>();
    }

    public static Bounce<T1, T2, TResult> YieldBreak<T1, T2, TResult>(TResult result)
    {
        return new Bounce<T1, T2, TResult>(result);
    }
}

As you can see, I had to be slightly creative in generating the recursive function in MakeLazyTrampoline. This is because the C# compiler won't allow you to create Iterators as lambda expressions (for very good reasons, no doubt). So I define the Iterator as its own method, then the lambda function that I actually return calls through to the Iterator to generate the sequence. As before, I've only shown the two-parameter version of the code. In the version I've included for download, there's a one-parameter version - you can easily extend it to any number of parameters.

You can download the Trampoline code, and the two examples shown above, here.

In the next episode, I'll show you how I used the Lazy Trampoline to solve Project Euler Problem 8.