Оптимизация хвостовых вызовов в C#

Question

У меня есть очень рекурсивная функция, которая должна теоретически работать хорошо даже с большими входами. Проблема во время написания я забыл, что C# не очень хорошо оптимизирует оптимизацию хвоста, если вообще, так что я получаю StackOverflowException s для любого сложного ввода. Основная структура метода состоит из двух больших методов, каждый из которых вызывает другой.

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

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

Оба IsSimple и ProcessExpansion имеют относительно неподвижную глубину стека - единственная проблема состоит в рекурсии между Simplify и Expand. Как вы собираетесь уменьшить глубину стека здесь?

Я думал о возвращении делегатов, которые рассчитывали бы результат, но это кажется излишним - должен быть более простой способ. Это моя мысль о решении (это не очень полированный, потому что я продолжаю думать, что я должен делать что-то ужасно неправильно здесь):

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)); 
} 

Так что мои два вопроса:

1. Что это что ужасно плохо с этим решением?
2. Можете ли вы подумать о лучшем?

Answer 1

Разве это не просто

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

?