return 语句中的堆栈溢出错误

Question

提交到 canvas 时出现堆栈溢出错误，但它在 Visual Studio 代码中运行良好，有人知道问题出在哪里吗？

这里是错误：

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

这是作业：

Euler's totient function, otherwise known as φ(n), measures the number of positive integers relatively prime to n that are less than n. Two numbers are relatively prime if their gcd is 1. For example: φ(9) = 6 because 1, 2, 4, 5, 7, and 8 are relatively prime to 9. More information about Euler's totient function can be found at this Wiki page.
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
Write a function int phi(int n) that takes an integer n as an input and returns φ(n), and a main() that prompts a user for an integer i, calls the function φ(i), and prints the result. The upper limit for the input i is 250000.

The closed form formula for computing φ(n) is: where p1, p2, ..., pm are prime numbers that divide the number n.

The output of your program should look and function like the examples shown below.
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;
}

return 语句中的堆栈溢出错误

Stack overflow error in return statement

java

stack-overflow