返回语句中的堆栈溢出错误

Question

当我提交到画布但在Visual Studio Code中运行正常时出现堆栈溢出错误，任何人都知道问题是什么？

这是错误：

Exception in thread "main" java.lang.StackOverflowError
    at Phi.gcd(Phi.java:14

这是作业：

Euler的totient函数，也称为φ（n），测量n的相对素数小于n的正整数的数量。如果它们的gcd是1，则两个数字是相对素数。例如：φ（9）= 6因为1,2,4,5,7和8是9的相对素数。关于欧拉函数的更多信息可以在这里找到维基页面。

n Relatively Prime    φ(n)
2 1   1
3 1,2 2
4 1,3 2
5 1,2,3,4 4
6 1,5 2
7 1,2,3,4,5,6 6
8 1,3,5,7 4
9 1,2,4,5,7,8 6
10    1,3,7,9 4

编写一个函数int phi(int n)，它将整数n作为输入并返回φ（n），并且提示用户输入整数main()的i调用函数φ（i），并打印结果。输入i的上限是250000。

用于计算φ（n）的闭合公式是：其中p1，p2，...，pm是除数n的素数。

程序的输出应该看起来和功能类似于下面显示的示例。

Enter a positive integer n: 8
Phi(n): 4

这是我的代码：

import java.util.Scanner;

public class Phi {

    static int gcd(int a, int b)
    {
        if (a == 0 || b == 0)
            return 0;

        if (a == b)
            return a;

        if (a > b)
            return gcd(a-b, b);
        return gcd(a, b-a);
    }

    static int phi(int n) {
        int count=0;
        for(int i = 1; i < n; ++i) {
            if(gcd(n, i) == 1) {
                count++;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        System.out.print("Enter a positive integer n: ");;
        int n = in.nextInt();
        System.out.printf("Phi(%d): %d\n", n, phi(n));
    }

}

Answer 1

这是因为您的递归GCD方法非常缓慢地收敛到GCD的值。例如，如果传递250000和1，则您的方法将使用250000个堆栈帧，比大多数JVM为您分配的帧数多。

一种解决方案是用迭代重写Euclid的GCD算法。另一种解决方案是使用更快的算法：

int gcd(int a, int b) {
    return (b != 0) ? gcd(b, a % b) : a;
}