Recursive method to print prime factorization of a number

[leroy tsruya]

Hi all.
I tried to write a recursive method to get the prime factorization of a given number.
This is what i have (notice the method uses the isPrime method:

 

import java.util.Scanner;

public class RecursivePrimeFactors {

	public static void main(String[] args){
		Scanner input = new Scanner(System.in);
		System.out.println("Enter a number");
		int num = input.nextInt();
		printPrimeFactors(num);
	}
	private static void printPrimeFactors(int num){
		if(isPrime(num)){
			System.out.print(" " + num);
		}
		else{
			int divider = 2;
			boolean found = false;
			while(!found){
				if(num % divider ==0){
					printPrimeFactors(divider);
					printPrimeFactors(num / divider);
					found = true;
				}
				else divider++;
			}
		}
	}


	private static boolean isPrime(int num){
		for(int i = 2; i <= num/2; i++)
		{
			if(num % i == 0 ){
				return false;
			}
		}
		return true;
	}
}

   

The program works.
My question, is it the correct way to do it? or is it a better way to do it? (it must be recursive).
Thanks!

[Sebastian Janisch]

Hey,

first of all, in most cases it really doesn't make sense to use an recursive approach over an iterative one. The reason is simple. Even though it is a more elegant approach, you always have the risk of running into an StackOverflowError. Also, with every subsequent recursion, another frame goes on the stack, which is not really a performance hit.

As for your code. Recursive methods generally have a break condition which - once met - returns a value, and if not met jumps into another recursion. I found a loop in your code and I'm asking myself if it really has to be there ? Since the idea of the recursive approach is not to use loops..

[Jeanne Boyarsky]

Sebastian,
sometimes a recursive approach is clearer. Especially when doing tree navigation.


Leroy,
What you have is fine. One more advanced technique is called "tail end recursion." If this the recursive call is the last thing in the method, the stack isn't needed. Tail end recursion doesn't apply here as there are two recursive calls. I'm just mentioning it for the sake of learning something .

[Sebastian Janisch]

Jeanne Boyarsky wrote:Sebastian,
sometimes a recursive approach is clearer. Especially when doing tree navigation.

true. The only occasion when I used recursion was when navigating in directory structures and delete a directory with all it's subdirectories. :-)

[leroy tsruya]

Thanks for your replays!
That was my problem, the while loop.
I try to rewrite my method without this while loop, but i cannot.
any suggestions?

[Campbell Ritchie]

Maybe recursion vs iteration is more difficult than we usually discuss here. It might be a bit late, but I shall move this thread.

[Mike Simmons]

leroy tsruya wrote:My question, is it the correct way to do it? or is it a better way to do it? (it must be recursive).

That's a correct way to do it. It produces the correct results, and it's recursive, so it fulfills the requirements. There are a number of ways it could be improved on, making it faster and/or shorter and/or easier to understand. It depends how much time you want to put into it.

Sebastian Janisch wrote:I found a loop in your code and I'm asking myself if it really has to be there ? Since the idea of the recursive approach is not to use loops..

That's kind of an extreme approach to recursion. It's true that you can eliminate pretty much any loop using recursive techniques, but that doesn't make it desirable in all cases. Some loops make sense to eliminate, and others, no. I think it would be poor advice to expect the elimination of all loops in this code. Though it might be an interesting educational experience. As long as it's not presented as expected general practice whenever "recursion" is mentioned.

Going back though...

Sebastian Janisch wrote:first of all, in most cases it really doesn't make sense to use an recursive approach over an iterative one. The reason is simple. Even though it is a more elegant approach, you always have the risk of running into an StackOverflowError. Also, with every subsequent recursion, another frame goes on the stack, which is not really a performance hit.

If you view recursive code as something where you're expected to eliminate all loops, then yes, stack overflow would be a major problem. But if we back off from this extreme approach... recursive code is code that, at some point, calls itself. That's it. That doesn't have to be the only way to repeat an action. It's entirely acceptable to mix loops with recursive techniques.

In the case of finding prime factors, it makes perfect sense to use a recursive call every time a new factor is identified. The stack will only ever get as deep as the number of factors, plus one or two. No problem - even really big numbers don't have that many factors. But if you try to write the code so that ever loop is eliminated with recursion, well, yes, in that case you'd probably have a new stack frame for every new repetition of the "if (num % divider ==0)" test. Not good, since that code will get called a lot. Eliminating all loops is possible, but would give horrible performance.

leroy tsruya wrote:I try to rewrite my method without this while loop, but i cannot.
any suggestions?

I suggest you don't bother. Unless your instructor is requiring you to do it, as part of the assignment. Or if you really want to see how recursion can be taken to extremes, out of morbid curiosity. Let us know if either is the case for you, and we can provide some guidance.

However, other (much more useful) improvements are possible. For example, why does the isPrime() loop terminate at num/2? How was that number determined? Do you really need to go that high? If you think about it, there's a much lower limit that you could use.

Also, I see two while loops, and it seems to me they're doing very similar work, even repeating identical work in some cases. I'm pretty sure it's possible to remove the isPrime() method entirely, if you rearrange your code a bit. (The new lower limit I just talked bout would still be used - you'd just move it into the printPrimeFactors() method.) The result can be both faster and simpler than what you have above.

[leroy tsruya]

Thanks a lot Mike Simmons for your answer!
very informative and helpful.
the loop in the isPrime method could go up to sqare root of the number, thanks for noting.
anyway, yeah, the code is working, but i kind of very weak with recursion, and i wanted to see some other approaches to solve it, or some explantion on how to do it better, faster.
Thanks!