Recursive to Tail recursive

Question

I am writing a traversal to find the longest path within a road. The magic part of this code is the segment.Next refers to LINQ that has specific logic applied to it like not revisiting already visited nodes. Therefore, don't point out the flaws in the travsel as thats out of scope.

What I am trying to do is reduce the number of calls on stack because sometimes the path can be a 5000 long. I know I have to make this recursive call tail recursive.

public static IEnumerable<Segment> FindLongestPath(Segment segment)
{
    var rv = new List<Segment> {segment};
    var longestPathLength = 0;
    var longestNextPaths = Enumerable.Empty<Segment>();

    foreach (var n in segment.Next)
    {
        var paths = FindLongestPath(n);
        var length = paths.Sum(p => p.LengthMeters);
        if (length > longestPathLength)
        {
            longestPathLength = length;
            longestNextPaths = paths;
        }
    }

    rv.AddRange(longestNextPaths);

    return rv;
}

How can I make this recursive call be tail recursive? I know I probably have to maintain the IEnumerable<Segment> as I travel but I am just not wrapping my head around it.

Answer 1

The answer from spender is the practical way to solve this problem without recursion: use an explicit stack or queue as a helper.

The original question and spender, in a comment, wonder how to do this algorithm in tail recursion style and continuation passing style, respectively. (CPS is a style of programming in which every call is a tail call.)

To give you the flavour of how a CPS version of this algorithm would look, let me (1) simplify the problem considerably, and (2) write the solution in ML, not C#. The simplified problem is:

• The function children takes a node and produces a stack of child nodes.
• The function cost gives the cost of traversing a single node.
• The problem given is to find the cost of the maximum cost path.

First, a straightforward non-CPS solution in ML:

let rec maximum_path_cost node =
  let rec aux nodes max =
    match nodes with
    | [] -> max
    | head :: tail -> 
       let c = maximum_path_cost head in
       let new_max = if c > max then c else max in
       aux tail new_max
  in
  (cost node) + (aux (children node) 0)

Briefly: we simulate a loop with a recursive auxiliary function that accumulates the maximum seen so far. The loop condition is "is the list empty?" If yes, then the result is the maximum seen so far; if not, then we compute the cost of the current item (the head of the list), compare it to the max, and run the loop on the tail.

Note that aux is tail recursive, but maximum_path_cost is not.

In continuation passing style, maximum_path_cost takes a continuation -- in this case, a function that takes an int -- and is required to call that function with its result, rather than returning. We'll make aux do the same.

For simplicity, we will not transform cost and children into CPS.

let rec maximum_path_cost node continuation =
  let rec aux nodes max aux_continuation =
    match nodes with
    | [] -> aux_continuation max
    | head :: tail ->
       let mpcc c = 
         let new_max = if c > max then c else max in
         aux tail new_max aux_continuation
       in
       maximum_path_cost head mpcc
  in
  let ac result =
    continuation ((cost node) + result) 
  in
    aux (children node) 0 ac

I know it is hard to wrap your brain around it, but if you read through it, it should make sense. The first thing we do is call aux with the children and a current max of zero; what is the continuation of the first call to aux? To add its result to the cost of the head, and pass that along to the continuation of maximum_path_cost. When do we do that? When we've run down the entire list of child nodes and have none left.

Translating this into C# and making C# guarantee tail recursion is left as an exercise. :)

Answer 2

Doing this with tail recursion is going to be tricky because you'll need to hand around continuations as delegates in order to do the post-recursion processing. The code will look pretty nasty to anyone who isn't versed in the functional style.

It seems like your prime motivation here is not to blow the call-stack. You can reduce your "brain-burn" by taking a non-recursive approach. Using an explicit Queue<T>/Stack<T> (depending on whether you want to traverse depth or breadth first), rather than the implicit stack you get from non-tail-recursive method calls means that your stack is limited only by available memory.

This should get you started down that road:

public static IEnumerable<Segment> FindLongestPath(Segment segment)
{
    var queue = new Queue<Segment>(); //or a Stack<Segment> with Push and Pop
    queue.Enqueue(segment);

    while(queue.Any())
    {
        var currentSegment = queue.Dequeue();
        foreach(var seg in currentSegment.Next)
        {
            queue.Enqueue(seg);
        }
        //process currentSegment
    }
}