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