Teaser Image

qnoid

Markos Charatzas - Edinburgh, UK

``````/**
* 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 :)