/**
     * An integer with extended operations 
     */
    public class ForrstInteger
    {
        private final int number;
        
        /**
         * @param number
         */
        public ForrstInteger(int number)
        {
            this.number = number;
        }

        /**
         * Multiply the number that many times.
         * 
         * @param number the number to multiply
         * @param times how many times to multiply it
         * @return the total after multiplying the number or 0 if times is 0
         */
        private int multiply(int number, int times)
        {
            if(times == 0){
                return 0;
            }
            
        return number + this.multiply(number, --times);
        }
        
        /**
         * Multiplies the number by times
         * 
         * @param times how many times to multiple the number
         * @return the multiple of the number
         */
        public int multiply(int times) {
        return this.multiply(this.number, times);
        }
    }

    /**
     * Let's prove our recursion theory
     */
    @RunWith(Theories.class)
    public class ForrstNumberTest
    {
        @DataPoints
        public static final int[] numbers = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        
        @Theory
        public void multiplyByOne(int number)
        {
            int actual = new ForrstInteger(number).multiply(1); 
            
            Assert.assertEquals(number, actual);
        }
        
        @Theory
        public void multiplyByZero(int number)
        {
            int actual = new ForrstInteger(number).multiply(0); 
            
            Assert.assertEquals(0, actual);
        }
        
        @Theory
        public void multiplyByTimes(int number, int times)
        {
            System.out.print( String.format("%s * %s = ", number, multiply) );
            int actual = new ForrstInteger(number).multiply(times); 
            
            System.out.println(actual);
            Assert.assertEquals(number * times, actual);
        }
    }

Recursion seems to scare people away but if you follow these simple rules it can become your best friend. Although it does sound complicated, its sole purpose is to simplify a problem.

The most difficult thing about a recursion is to identify a problem as such. You will know you have encountered a recursion when you see a pattern being repeated again and again.

Isn’t that a loop you say? Well the main difference with a normal loop is that the result of a recursion solely depends on the outcome of the recursion itself. Confused?

Take for example multiplication. If you think about it, multiplication is a disguised addition.

2 * 4 = 2 + 2 + 2 + 2 = 8

So to come up with 8 as the result you had to follow this pattern

0 + 2 = 2
2 + 2 = 4 
4 + 2 = 6 
6 + 2 = 8 

Which means add 2 everytime, 4 times starting with 0.

Let’s take it backwards for a minute.

6 + 2 = 8 //how did you come up with 6?
4 + 2 = 6 //how did you come up with 4?
2 + 2 = 4 //how did you come up with 2?
0 + 2 = 2 //You don't have to calculate 0! (**Hint**)

The problem is that you don’t know which number to add to 2 every time since you haven’t calculated yet! So what you really have is something like this

2 + x = 8 
2 + x = 6 
2 + x = 4
2 + 0 = 2 //notice the pattern changing by adding 0 this time.

Do you notice the recursion?

2 + x

where x is the next number to add until it’s the 0 which ends the recursion. Which is your stop condition!

So in essence once you have identified a recursion problem there are 2 things you have to think.

• What is the recursion
• What is the stop condition

Failing to identify a stop condition will most likely lead to an infinite loop and a possible StackOverFlowError or OutOfMemoryException. Both pretty nasty.

Now try and identify the recursion needed to raise a number to a given integer power. (don’t bother more than an integer power, though it involves much more than that)

The first one to reply to this post with a solution (and a test to prove it!) will receive a Kudoz postcard from Edinburgh :)

Can you find any other recursions? Leave your comments below.

Update: Don’t bother with NaN or infinite values like the Math#pow(double, double), just do it for 0 to 10 like the test above. Just follow the recursion example and it’s easy to come up with it :)

Source