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 :)