Bradley Dean

Performance Penatly of Recusive Calls

The 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.

public long RussianMultiplication(long val1, long val2)
{
     long val2_first = 0;
     while (val1 != 1)
     {
          // divide val1 by half until it reaches 1
          val1 = Num1(val1);

          // multiple val2 by 2 until
          val2 = val2 * 2;

          // record the first instance of val2 being multiplied
          if (val2_first == 0)
          {
               val2_first = val2;
          }
     }

     // multiple the first value of val2 and the last value of val2
     return val2_first + val2;
}

private long Num1(long val)
{
     if (val == 1)
     {
          return 1;
     }
     else
     {
          return Math.Abs(val / 2);
     }
}

The second version is the same as the above, but uses no recursion at all:

public long RussianMultiplication(long val1, long val2)
{

long val2_first = 0;
while (val1 != 1)
{

// divide val1 by half until it reaches 1
val1 = Math.Abs(val1 / 2);

// multiple val2 by 2 until
val2 = val2 * 2;

// record the first instance of val2 being multiplied
if (val2_first == 0)
{
val2_first = val2;
}

}

// multiple the first value of val2 and the last value of val2
return val2_first + val2;

}

And the final version is done with full recursion. This is simply the first full (C#) recursion example from the comments on DailyWTF:

public long RussianMultiplication(long val1, long val2)
{

if (val1 < 2)
return (val1 == 1 ? val2 : 0);
if (val1 % 2 == 1)
return val2 + RussianMultiplication(val1 / 2, val2 * 2);
return RussianMultiplication(val1 / 2, val2 * 2);

}

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.