3

我有一个深度递归函数，理论上即使输入很大，它也应该能很好地工作。问题是在撰写本文时，我忘记了 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. 你能想出一个更好的吗？
4

1 回答 1

8

这不只是

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

?

于 2010-09-10T00:15:20.483 回答