trying to break out of for loop but keeps going back into it and performing recursive call

Question

I just discovered the project euler website, I have done challenges 1 and 2 and have just started number 3 in java... here is my code so far:

import java.util.ArrayList;

public class IntegerFactorise {

    private static int value = 13195;
    private static ArrayList<Integer> primeFactors = new ArrayList<Integer>();
    private static int maxPrime = 0;

    /**
     * Check whether a give number is prime or not
     * return boolean
     */
    public static boolean isPrimeNumber(double num) {
        for(int i = 2; i < num; i++) {
            if(num % i == 0) {
                return false;
            }
        }

        return true;
    }

    /*Multiply all of the prime factors in the list of prime factors*/
    public static int multiplyPrimeFactors() {
        int ans = 1;
        for(Integer i : primeFactors) {
            ans *= i;
        }

        return ans;
    }

    /*Find the maximum prime number in the list of prime numbers*/
    public static void findMaxPrime() {
        int max = 0;
        for(Integer i : primeFactors) {
            if(i > max) {
                max = i;
            }
        }

        maxPrime = max;;
    }

    /**
     * Find all of the prime factors for a number given the first
     * prime factor
     */
    public static boolean findPrimeFactors(int num) {
        for(int i = 2; i <= num; i++) {
            if(isPrimeNumber(i) && num % i == 0 && i == num) {
                //could not possibly go further
                primeFactors.add(num);
                break;
            }
            else if(isPrimeNumber(i) && num % i == 0) {
                primeFactors.add(i);
                findPrimeFactors(num / i);
            }
        }

        int sumOfPrimes = multiplyPrimeFactors();
        if(sumOfPrimes == value) {
            return true;
        }
        else {
            return false;
        }   
    }

    /*start here*/
    public static void main(String[] args) {
        boolean found = false;
        for(int i = 2; i < value; i++) {
            if(isPrimeNumber(i) && value % i == 0) {
                primeFactors.add(i);
                found = findPrimeFactors(value / i);
                if(found == true) {
                    findMaxPrime();
                    System.out.println(maxPrime);
                    break;
                }
            }
        }
    }

}

I am not using the large number they ask me to use yet, I am testing my code with some smaller numbers, with 13195 (their example) i get down to 29 in this bit of my code:

else if(isPrimeNumber(i) && num % i == 0) {
                    primeFactors.add(i);
                    findPrimeFactors(num / i);
                }
            }

            int sumOfPrimes = multiplyPrimeFactors();
            if(sumOfPrimes == value) {
                return true;
            }

It gets to the break statement then finally the check and then the return statement. I am expecting the program to go back to the main method after my return statement, but it jumps up to:

findPrimeFactors(num / i);

and tries to finish the iteration...I guess my understanding is a flawed here, could someone explain to me why it is behaving like this? I can't wait to finish it of :) I'll find a more efficient way of doing it after I know I can get this inefficient one working.

Answer 1

You are using recursion, which means that a function will call itself.

So, if we trace what your function calls are when you call return, we will have something like that:

IntegerFactorise.main()
|-> IntegerFactorise.findPrimeFactors(2639)
    |-> IntegerFactorise.findPrimeFactors(377)
        |-> IntegerFactorise.findPrimeFactors(29) -> return true;

So, when you return in the last findPrimeFactors(), you will only return from this call, not from all the stack of calls, and the execution of the previous findPrimeFactors() will continue just after the point where you called findPrimeFactors().

If you want to return from all the stack of calls, you have to modify your code to do something like that:

        else if(isPrimeNumber(i) && num % i == 0) {
            primeFactors.add(i);
            return findPrimeFactors(num / i);
        }

So that when the last findPrimeFactors() returns, all the previous findPrimeFactors() which called it will return too.

Answer 2

I think the problem is that you are ignoring the return value from your recursive call to findPrimeFactors().

Let's walk through this. We start with the initial call to findPrimeFactors that happens in main. We then enter the for loop as it's the first thing in that method. Now let's say at some point we get into the else statement and thus recursively call frindPrimeFactors(num / i). This will suspend the looping, but as this recursive call starts to run you enter the for loop again (remember, the previous loop is merely paused and not finished looping yet). This time around you encounter the break, which allows this recursive call to finish out, returning true of false. When that happens you are now back to the original loop. At this point the original loop continues even if the recursive call returned true. So, you might try something like this:

if (findPrimeFactors(num / i))
    return true;

I'm assuming that you need to continue looping if the recursive call returned false. If you should always finish looping upon return (whether true or false) then try this:

return findPrimeFactors(num / i);