如何打破这个循环？（涉及IT技术）

Question

如何打破这个循环？（涉及IT技术）

5

我正在解决欧拉计划第5题。我没有谷歌搜索，因为那通常会导致一个有答案的 Stack Overflow 页面出现。所以，这就是我的解决方案：

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

在我的理解中，这是有道理的。然而，VS2012给出了一个StackOverFlowException异常提示，建议我确保我没有进入无限循环或使用递归。我的问题是，为什么这是一个无限循环？我有一种感觉，我完全忽略了某些愚蠢的事情。

编辑：

由于人们似乎还在发布答案，我要重申一下，我没有使用Google，因为我害怕会找到答案。我不想知道问题的答案，我只想知道为什么会出现异常。

- PiousVenom

3

即使没有无限递归，你可能仍然会出现栈溢出的情况。许多这类问题都被设计成足够大，需要你的代码能够合理地扩展。你可能只需采用非递归方法，并将其重构为循环。 - Servy

@Servy：看来我还有更多关于堆栈和它的工作方式需要学习。谢谢。 - PiousVenom

这仍然会导致堆栈溢出，但当您重新启动时，您不需要检查1的除数，所有整数已经可以被1整除了。您还可以将被除数增加2（甚至是10）。这些只是一些提示，当您切换到循环时要注意。 - Cemafor

2个回答

1

+1给Jason的回答，他清楚地解释了问题。

现在让我们来看看解决方案！我知道至少有三种方法可以从算法中删除递归：

找到一个纯迭代的算法（对于某些问题可能很困难）；
将递归算法转换为类似于循环的算法，并使用Stack<T>（或某种列表）存储等效的调用堆栈。这具有与原始算法类似的空间要求，但堆可以比堆栈更大！
一类特殊的递归算法是尾递归。这些可以轻松机械地改变以使其永远不会溢出堆栈。你很幸运，这就是你的情况！

如果一个算法的所有递归调用都是尾调用，则该算法是尾递归的，这意味着它们是返回之前执行的最后一件事。如果您不清楚，请使用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; 
}

嘿！这个函数和之前的一样，但是有一个固定的堆栈大小（没有调用，只有跳转）。有些人会说：“呃……goto语句！它们很邪恶！死吧，goto！”。我会说这是为数不多的合法用途之一。毕竟，如果你的编译器够聪明，它会自己进行尾调用优化（F#实际上做到了，C#没有，在x64上JIT可能会做到，但在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; 
}

好的！

- jods

我并不是在寻求解决问题的方案。 - PiousVenom

抱歉，我没有尝试解决欧拉计划问题，只是试图展示如何处理递归。实际上，我发布的代码100%源自您的代码，如果有任何错误仍然存在；因为我甚至没有检查行为是否正确与欧拉问题相关。至少我清楚地说明了我要写什么，所以希望您可以跳过剧透... - jods

但是即使去除递归也不是我想要的。 - PiousVenom

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- jason · Accepted Answer

当然，这种逻辑肯定会导致堆栈溢出。想一想，如果你要实现这种逻辑来解决找到1-10中最小的可整除数的问题，你至少需要2520个函数调用，根据problem statement:

2520是可以被1-10中的每个数字整除的最小数字。

对于1-20，答案显然要大得多，所以堆栈溢出也就不足为奇了。你应该找到一个非递归的解决方案。

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

不是。堆栈大小是有限制的。你做了太多的递归调用，最终超过了最大堆栈大小。

我感觉自己可能错过了一些非常愚蠢的东西。

你来到了right place。