How To Think Of… Recursion
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 :)