Stack overflow error in return statement

Question

Getting a stack overflow error when i submit to canvas but it runs fine in Visual Studio Code, anyone know what the issue is?

Here is the error:

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

Here is the assignment:

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

And here is my code:

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

This is because your recursive GCD method converges to the value of GCD very slowly. For example, if you pass 250000 and 1, your method would use 250000 stack frames, more than most JVMs would allocate for you.

One solution is to rewrite Euclid's GCD algorithm with iterations. Another solution is to use a faster algorithm:

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