I happened over some having a problem with a prime factorization algorithm http://ubuntuforums.org/showthread.php?t=2062201. It inspired me to actually use my blog. Prime factorization is easy to conquer, if you just think recursively. I’m not saying this is the implementation which will give the absolute best running time, but it’s easy to wrap your head around and gives a good idea of how to use recursion. First, the code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

import java.util.ArrayList;
import java.math.BigInteger;
public class PrimeFactorization {
  private static ArrayListprimes = new ArrayList();
  public static void main(String[] args) {
      BigInteger start = new BigInteger("600851475143");
      recurse(start);
      for(int i = 0; i < primes.size(); i++)
          System.out.print(primes.get(i).toString() + ", ");
  }
  public static void recurse(BigInteger num) {
      BigInteger i = new BigInteger("2");
      //we use these as "constants" later
      final BigInteger zero = new BigInteger("0");
      final BigInteger one = new BigInteger("1");
      //base case, num = 2; reuse i on our way
      if(num.equals(i)) {
          primes.add(i);
          return;
      }
      for(; !num.mod(i).equals(zero); i = i.add(one)) {
          if(num.subtract(i).subtract(i).signum() == -1) { //this number is prime
              primes.add(num);
              return;
          }
      }
      //we found two divisors, recurse them
      recurse(i);
      recurse(num.divide(i));
  }
}

So this is pretty simple to follow. It starts with a number, then just sends it to the recursive method. If the number = 2, which is our http://en.wikipedia.org/wiki/Base_case, then it is obviously prime and we add it to our array of prime numbers. If not, we start at two for our counter and keep adding one until we get a number that evenly divides into our target number.!num.mod(i).equals(zero) Or, if we go past the mid point if(num.subtract(i).subtract(i).signum() == -1) we know it is a prime number by deductive reasoning: If you start at 2 (which when the number is divided by 2 yields half the number), then go past half the number there is no way you can even divide into the number. If it is prime, we add it to the array and return, breaking out of this recursive dive. Else, if we found two divisors, we recurse through both of them to get their prime factorizations. Because the prime factorization of any number is equal to the prime factorization of its factors. That’s all for today. Any questions or comments feel free to respond!