Win a copy of Murach's MySQL this week in the JDBC and Relational Databases forum!
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Jeanne Boyarsky
• Ron McLeod
• Paul Clapham
• Liutauras Vilda
Sheriffs:
• paul wheaton
• Rob Spoor
• Devaka Cooray
Saloon Keepers:
• Stephan van Hulst
• Tim Holloway
• Carey Brown
• Frits Walraven
• Tim Moores
Bartenders:
• Mikalai Zaikin

# Recursive method to print prime factorization of a number

Ranch Hand
Posts: 57
• Number of slices to send:
Optional 'thank-you' note:
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!

Ranch Hand
Posts: 1183
• Number of slices to send:
Optional 'thank-you' note:
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..

author & internet detective
Posts: 41849
904
• Number of slices to send:
Optional 'thank-you' note:
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
Ranch Hand
Posts: 1183
• Number of slices to send:
Optional 'thank-you' note:

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
Posts: 57
• Number of slices to send:
Optional 'thank-you' note:
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?

Marshal
Posts: 79006
375
• Number of slices to send:
Optional 'thank-you' note:
Maybe recursion vs iteration is more difficult than we usually discuss here. It might be a bit late, but I shall move this thread.

Master Rancher
Posts: 4754
68
• Number of slices to send:
Optional 'thank-you' note:

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
Posts: 57
• Number of slices to send:
Optional 'thank-you' note:
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!