This recent post on The DailyWTF has brought in many comments with people providing code samples in many different languages. The post, Programming Praxis: Russian Peasant Multiplication, offers a simple coding challenge.
The challenge screams for recursion and many of the answers in the comments went this route. Of course, when we talk recursion we always have to qualify it as saying there is a performance penalty for using recursion.
Using this Russian Multiplication challenge as an example, I’ve done some testing to see how much the penalty is.
I have three versions of the code:
The first version is the solution I came up with before reading the comments in on the DailyWTF. It uses recursion inside of an enclosure class to ease readability.
The second version is the same as the above, but uses no recursion at all:
And the final version is done with full recursion. This is simply the first full (C#) recursion example from the comments on DailyWTF:
Let’s call the three examples Partial Recursion, No Recursion, and Full Recursion. To test them I put them each in a class in a C# console app and ran each through a loop having them multiple 1 x 999,999 through 999×999 x 1.
Over 5 runs, here are the averages:
Partial Recursion: 43 ms No Recursion: 584 ms Full Recursion: 218 ms
Using No Recursion as a baseline, that shows a performance increase, not a performance decrease! Full Recursion only takes 37% of the time as No Recursion. Partial Recursion only takes 7% of the time.
While I’m happy to see my solution as the quickest, I have to admit that I’m a little surprised by the results. I’m tempted to dig into this further with some code analyzers.
However, I think the point is that there is no hard and fast rule about recursion. You can not rule out recursion because of a fear of a “performance penalty”. There is nothing that can replace testing the code and seeing the results.