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?

Your method says it returns an ArrayList but it doesn't yet. Let's change it to modify an ArrayList instead:

When you call yourself recursively pass the list along. When you print, also add the factor to the list. When it's all done the list will contain the same factors you printed.

A good question is never answered. It is not a bolt to be tightened into place but a seed to be planted and to bear more seed toward the hope of greening the landscape of the idea. John Ciardi

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.

Cheers,

Tom Blough<br /> <blockquote><font size="1" face="Verdana, Arial">quote:</font><hr>Cum catapultae proscriptae erunt tum soli proscripti catapultas habebunt.<hr></blockquote>

Stan James
(instanceof Sidekick)
Ranch Hand

Joined: Jan 29, 2003
Posts: 8791

posted

0

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.

Originally posted by Arjunkumar Shastry: I was unaware that Integer.MAX_VALUE is a prime number.

If I remember correctly from about 16 years ago, (2^n - 1) is often a prime number: 3, 7, 31, 127 (?). Since Integer.MAX_VALUE is (2^31 - 1), it stands a decent chance of being prime.

Note: I didn't check any of my math, and it's very late.

Arjunkumar Shastry
Ranch Hand

Joined: Feb 28, 2005
Posts: 986

posted

0

I just dded little code to test how many are primes are of form 2^n -1 1 true 3 true 7 true 15 false 31 true 63 false 127 true 255 false 511 false 1023 false 2047 false 4095 false 8191 true 16383 false 32767 false 65535 false 131071 true 262143 false 524287 true 1048575 false 2097151 false 4194303 false 8388607 false 16777215 false 33554431 false 67108863 false 134217727 false 268435455 false 536870911 false 1073741823 false 2147483647 true Outof 31,only 9 are primes ! Unfair

Arjunkumar Shastry
Ranch Hand

Joined: Feb 28, 2005
Posts: 986

posted

0

It seems like when n is prime,2^n -1 is also prime. Thanks