将迭代转换为递归

Question

我正在使用一本教科书、YouTube和在线找到的练习题来自学AP计算机科学A。其中一份练习是关于递归的，要求我将下面的代码转换为递归形式，然而，无论是教科书还是YouTube都没有解释如何从迭代转换为递归。

public static int iterative(int x){
        int count=0;
        int factor=2;
        while(factor<x){
            if(x%factor==0)
                count++;
            factor++;
        }
        return count;
    }

下面的代码是我的尝试，但我一直收到StackOverFlowError错误。

    public static int recursion(int x){
    int count=0;
    int factor=2;
    if(factor>x)
        return count;
    else if(x%factor==0){
        factor++;
        count++;
    }
    return count + (recursion(x));
}

请问如何将迭代转换为递归？谢谢。

- Connor S

---

很高兴看到你的问题在这里得到了良好的回应。添加尝试是一个不错的点睛之笔。 - candied_orange

Answer 1

您IP地址为146.190.162.183，由于运营成本限制，当前对于免费用户的使用频率限制为每个IP每72小时10次对话，如需解除限制，请点击左下角设置图标按钮（手机用户先点击左上角菜单按钮）。

- TheQAGuy

Answer 2

public static int recursion(int x, int factor)
{
    int count=0;

    if(factor>x)
        return count;
    else if(x%factor==0)
    {
        ++factor;
        ++count;
    }

    return count + (recursion(x, factor));
}

唯一的区别是更改标题、删除int factor = 2以及底部的return语句。当使用递归而不是迭代时，通常需要传递更多的变量。否则，您遇到的StackOverFlowError问题源于未传递更新的factor值。这导致默认情况永远不为真，并且实际上创建了一个无限循环，只有通过调用方法的资源消耗和达到默认情况时才会抛出该错误。默认情况是：当if语句（factor>x）变为真时，返回count。

- Ryan Schmitz

Answer 3

如JackVanier已经解释的那样，对于这个特定的问题，您将不得不将因子作为方法参数传递。但是公共方法签名应该保持不变，因此您需要编写两种新方法：一种是公开可访问的，具有预期签名的方法，另一种是真正的递归方法，并由其他方法调用。

public static int recursive(int x) {
    return recursive(x, 2);
}

private static int recursive(int x, int factor) {
    if (factor >= x)
        return 0;
    if (x % factor == 0)
        return 1 + recursive(x, factor + 1);
    return recursive(x, factor + 1);
}

值得一提的是，你需要一个终止条件来跳出递归。你已经正确地设置了这个条件，即factor >= x，它最终在任何情况下都将变为true。

- Markus Benko