CODEWITHSUNDEEP
javarecursionstack-overflowtail-recursion
Jleaton
Jleaton

Reputation: 133

Tail Recursion java

I am working on finding the largest prime factor of any given number. The code below works fine for most numbers until I input the number I want which is 600851475143. Once I do this I get stack overflow. I have been reading up on tail recursion and from what I know I should have implemented it right. Yet, I still receive the stack overflow error despite it. Where am I going wrong when it comes to implementing tail recursion?

import java.util.Scanner;
public class LargestPrimeFactor
{
    static long number;
    static long answer;

    public static void main(String[] args)
    {
        System.out.println( "Enter number to find its largest prime factor");
        Scanner input = new Scanner(System.in);
        number = input.nextLong();

        answer = largestPrime(number);
        System.out.println("The largest prime of " + number + " is " + answer);
    }

    private static long largestPrime(long n)
    {
        n = n-1;    
        if(n % 2 != 0 & number % n == 0 )
        {   
            return n;
        }
        else
        {           
            return largestPrime(n);
        }
    }
}

Upvotes: 3

Views: 2703

Answers (1)

Nir Alfasi
Nir Alfasi

Reputation: 53525

First, in the if condition you're doing & when you probably meant to do &&. And second, your implementation is incorrect. Try to run it on 18 (largest prime is 3) and see that it returns 9 which is obviously not prime.

As for the stackoverflow, since there's no condition that restrict n > 1 in some cases the calculation will continue with -1, -2, -3,... until you'll get stackoverflow...

And last, the JVM does not support tail-recursion optimization, but even if it did - you'll almost always be better with an iterative solution because unlike recursive solutions - it doesn't open a new frame on the stack for every recursive call (because there are no recursive calls - it runs in a loop).

Edit

  • To find the largest prime factor you can start with n/2 and go down (minus one each iteration).
  • The definition of a prime number p is: p > 1 and p can be divided only by itself (and 1). Use this definition and write an iterative method boolean isPrime(int num)
  • now use the previous two bullet-point and combine them to write a recursive method that finds the largest prime. I didn't want to implement it in order not to ruin your fun :)

Upvotes: 4

Related Questions