Russian Dolls Performing Recursion
Programmers often mention recursion but less often discuss the tradeoff. Some things are better handled without recursion while others are particularly suited for it.
A simple explanation of recursion is where you write a method that continually calls itself until it reaches a base case and exits. I won’t go into writing code as you can get the examples from Wikipedia’s resursion page. This technique allows for compact code and has been a key component of some powerful algorithms. Its particularly useful for traversing tree data structures, for example. But it has a down side – memory resources.
The best demonstration I’ve seen to explain recursion was from a lecturer named Julian Dermoudy at the University of Tasmania (who is also now the head of school) in a first year programming unit called Programming and Problem Solving. He uses a set of russian dolls. The first time the recursive method is run the doll unpacks its first layer and then checks to see if it meets the base case. If the base case isn’t met the doll unpacks itself another layer and then checks again to see if the base case is met. This continues until the base case is met, at which time the doll (representative of a recursive method) systematically puts itself back together retracking its recursive calls in reverse order. Finally the russian doll is back in one piece and the method call is complete.
Why is this a potential memory issue? Each time the recursive call is made (as each doll is unpacked in the example) this has to be dealt with in memory and when the base case is met the entire process is reversed until the doll is back together. This isn’t a bad thing but it needs consideration.
Sometimes a problem is just better achieved using a non-recursive solution. The trick is not only in being able to achieve the magic of recursive solutions but in knowing when they are better used or better avoided.
Russian dolls, on the other hand, have always struck me as slightly creepy. I can’t explain why.
