Generally we don't use recursion unless its must as debugging recursive code takes time.I was thinking about the method which should return the prime factors of a natural number.For 100,it will be 2,2,5,5.Recursion is a natural choice as we find the factors similarly on a paper.
Now in this recursive method I want to return the factors,it has found out for number n,Any idea how to do this?
The most obvious way, as Stan pointed out, would be to pass the List/ArrayList (in addition to the reduced number) into the recursive so that each factor can be added as it's found.
Is there a way to get around this? How about this: Have the method instantiate the ArrayList iff the number that was passed in is prime. Then it can just return the ArrayList and each instance of the method can add its factor to the ArrayList on the way out (i.e. between the recursive call and returing). One advantage to this is that the client object doesn't have to be responsible for instantiating the ArrayList.
I haven't tried running or even compiling this code, but...
(You don't need the isPrime() call with the n%i test, because if i wasn't prime then a factor of i would have caused the loop to terminate in an earlier iteration.
Speaking of isPrime(), I wouldn't use that in printFactors() because of the repeated use of the for loop in the two methods. I'd just use the for(int i...) loop to determine primality (primeness? primularity? primosity?) in printFactors() and act accordingly (either instantiate the ArrayList or make the recursive call). Taking it even farther, I'd make public a static ArrayList getFactors(int n) as one method. Then, if needed isPrime() for other reasons, have isPrime(int n) call getFactors(n) to (silently) get the factors and return true iff the returned ArrayList has a size() == 1. Then have a third method printFactors(int n) that calls getFactors(n) and then prints the returned elements of the returned ArrayList.
But that's just me.
Ryan [ April 07, 2005: Message edited by: Ryan McGuire ]
why should debugging recursive code take any more time than debugging iterative code? is it perhaps because you're just not as familiar with recursive code? there's a good cure for that: get familiar with it!
the suggestions in this thread seem good. another suggestion: often it's a good idea to have a "core" method that's doing the actual recursing, perhaps passing along a collection (or some other variable) for accumulating the results as they're found. then have a "driver" method that gets the recursor started, passing in an empty collection (or whatever) as a way of saying "you haven't found any results yet". when the recursor finally returns its results, typically the "driver" would just pass these along to whatever method called it - to the rest of the world your "driver" is the whole method, and the recursor can be kept private.
this way the list of parameters to the recursor can be made "messy", to include whatever is needed in the recursion, but the list of parameters and return values for the "driver" can be kept neat for general use.
While the Sieve of Erastosthenes is much faster for factoring small values of primes (up to Integer.MAX_VALUE), you can speed your code up quite a bit. You are alreadying testing up to n^0.5, but once you begin identifying the prime factors, you only need to check by using the found primes as divisors.
You'll agree that once you've determined that the number is divisible by 2, then there is not need to check 4, 6, 8.... Simililary, once 3 is determnied to be a prime factor, there is no need to check 6, 9, 12....
So therefore if I want to find the prime factors of 100, I only need to check the known primes of less than 100^0.5 or 2, 3, 5, 7. If 100 was not divisible by 2, 3, 5, or 7, then it would be prime.
Tom Blough<br /> <blockquote><font size="1" face="Verdana, Arial">quote:</font><hr>Cum catapultae proscriptae erunt tum soli proscripti catapultas habebunt.<hr></blockquote>
Joined: Jan 29, 2003
Ryan and M Beck are both right - I did a sloppy thing making the client pass in the list. In real life I'd make a public method that creates the list, calls the signature I showed on a private recursive method, then returns the list. I seem to do this fairly often becuase the recursive method needs some information like recursion depth to format a nice outline or something.