# How To Think Of... Recursion

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