CODEWITHSUNDEEP
c#tail-recursiontail-call-optimization
configurator
configurator

Reputation: 41616

Optimizing tail-calls in C#

I've got a deeply recursive function that should in theory work well even with large inputs. The problem is at the time of writing I forgot that C# doesn't do tail-call optimization very well, if at all, so I get StackOverflowExceptions for any complex-enough input. The basic structure of the method is in two large methods, each calling the other.

public object Simplify(object param) {
    if (IsSimple(param))
        return param;
    else
        return Expand(param);
}

private object Expand(object param) {
    return Simplify(ProcessExpansion(param));
}

Both IsSimple and ProcessExpansion have a relatively fixed stack depth - the only problem is the recursion between Simplify and Expand. How would you go about reducing the stack depth here?

I was thinking of returning delegates that would calculate the result, but that seems like overkill - there must be a simpler way. This is my thought of a solution (it isn't very polished because I keep thinking I must be doing something horribly wrong here):

public object Simplify(object param) {
    object result = () => SimplifyInternal(param);
    while (result is Func<object>)
        result = ((Func<object>)result)();
    return result;
}

private object SimplifyInternal(object param) {
    if (IsSimple(param))
        return param;
    else
        return Expand(param);
}

private object Expand(object param) {
    return () => SimplifyInternal(ProcessExpansion(param));
}

So my two questions are:

  1. What is it that feels horribly wrong with this solution?
  2. Can you think of a better one?

Upvotes: 3

Views: 1320

Answers (1)

Brian
Brian

Reputation: 118855

Isn't this just

while(!IsSimple(param))
    param = ProcessExpansion(param);
return param;

?

Upvotes: 8

Related Questions