5

I'm working on Project Euler number 5. I've not Googled, as that will typically lead to a SO with the answer. So, this is what I've got:

    private int Euler5(int dividend, int divisor)
    {
        if (divisor < 21)
        {
            // if it equals zero, move to the next divisor
            if (dividend % divisor == 0) 
            {
                divisor++;
                return Euler5(dividend, divisor);
            }
            else
            {
                dividend++;
                return Euler5(dividend, 1); // move to the dividend
            }
        }
        // oh hey, the divisor is above 20, so what's the dividend
        return dividend; 
    }

In my mind, this makes sense. Yet VS2012 is giving me a StackOverFlowException suggesting I make sure I'm not in an infinite loop or using recursion. My question is, why is this an infinite loop? I've a feeling I'm missing something completely silly.

EDIT

Since people seem to keep posting them, I'll reiterate the fact that I didn't use Google for fear of stumbling on the answer. I don't want the answer to the problem. I only wanted to know why I was getting the exception.

4

2 回答 2

10

当然，这种逻辑会炸毁堆栈。想一想，如果您要实现此逻辑来解决找到可被 1--10 整除的最小数字的问题，那么根据问题陈述，您将在堆栈深处至少有 2520 个调用：

2520 是可以除以 1 到 10 的每个数字而没有任何余数的最小数字。

对于 1--20，答案显然要大得多，而且你正在吹堆栈一点也不奇怪。你应该找到一个非递归的解决方案。

我的问题是，为什么这是一个无限循环？

它不是。堆栈的大小是有限的。您进行了太多递归调用并最终超出了最大堆栈大小。

我有一种感觉，我错过了一些完全愚蠢的东西。

你来对地方了。

于 2013-06-03T20:16:06.343 回答
1

杰森的回答+1，这清楚地解释了问题。

现在寻求一些解决方案！我至少知道从算法中删除递归的三种方法：

  1. 找一个纯粹的迭代算法代替（这对于某些问题可能很困难）；
  2. 使用循环将递归算法转换为类似的算法，并使用 Stack<T> （或某种列表）来存储调用堆栈的等价物。这与原始的空间需求相似，但堆可以比堆栈大得多！
  3. 一个特殊的递归算法家族是尾递归的。这些可以很容易地机械地更改为永远不会溢出堆栈。你很幸运，这是你的情况！

如果算法的所有递归调用都是尾调用，则该算法是尾递归的，这意味着它们是返回之前完成的最后一件事。如果您不清楚，请使用 Google 查找更好的示例。

通过调整参数和使用 goto 而不是真正的调用，可以轻松地转换此类算法。再看看你的例子：

private int Euler5(int dividend, int divisor)
{
    tail_call:
    if (divisor < 21)
    {
        // if it equals zero, move to the next divisor
        if (dividend % divisor == 0) 
        {
            divisor++;
            goto tail_call; // return Eular5(dividend, divisor);
        }
        else
        {
            dividend++;
            // return Eular5(dividend, 1); // move to the dividend
            divisor = 1;
            goto tail_call;
        }
    }
    // oh hey, the divisor is above 20, so what's the dividend
    return dividend; 
}

噢！嗨！它是完全相同的函数，但堆栈大小固定（没有调用，只有跳转）。现在有些人会说：“呃...... gotos！他们是邪恶的！去死去死吧！”。我会说这是为数不多的合法用途之一。毕竟，如果您的编译器足够聪明，它会自己进行尾调用优化（F# 实际上会，C# 不会，JIT 可能会在 x64 上进行，而不是在 x86 上）。

但对于那些人，我会说：看起来好一点。因为每个 if/else 分支的末尾都有一个 goto，所以我可以将它完全移到“if”之外。现在我有类似“start: if (X) { Y(); goto start; }”的东西，想想看，这只是一个“while(X) Y()”循环。所以你刚刚找到了你的函数的迭代版本：

private int Euler5(int dividend, int divisor)
{
    while (divisor < 21)
    {
        // if it equals zero, move to the next divisor
        if (dividend % divisor == 0) 
        {
            divisor++;
        }
        else
        {
            dividend++;
            divisor = 1;
        }
    }
    // oh hey, the divisor is above 20, so what's the dividend
    return dividend; 
}

好的！

于 2013-06-03T20:47:15.533 回答