aspose file tools*
The moose likes Java in General and the fly likes Recursive method to print prime factorization of a number Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Java in General
Bookmark "Recursive method to print prime factorization of a number" Watch "Recursive method to print prime factorization of a number" New topic
Author

Recursive method to print prime factorization of a number

leroy tsruya
Ranch Hand

Joined: Sep 24, 2009
Posts: 57
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:

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
Ranch Hand

Joined: Feb 23, 2009
Posts: 1183
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..


JDBCSupport - An easy to use, light-weight JDBC framework -
Jeanne Boyarsky
internet detective
Marshal

Joined: May 26, 2003
Posts: 30537
    
150

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 .


[Blog] [JavaRanch FAQ] [How To Ask Questions The Smart Way] [Book Promos]
Blogging on Certs: SCEA Part 1, Part 2 & 3, Core Spring 3, OCAJP, OCPJP beta, TOGAF part 1 and part 2
Sebastian Janisch
Ranch Hand

Joined: Feb 23, 2009
Posts: 1183
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
Ranch Hand

Joined: Sep 24, 2009
Posts: 57
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
Sheriff

Joined: Oct 13, 2005
Posts: 38865
    
  23
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
Ranch Hand

Joined: Mar 05, 2008
Posts: 3014
    
  10
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
Ranch Hand

Joined: Sep 24, 2009
Posts: 57
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!
 
jQuery in Action, 2nd edition
 
subject: Recursive method to print prime factorization of a number