Tinsology

For some reason whenever I see someone post code that cycles through an array or does something repeatedly, that code takes the form of some kind of loop. I admit that I’m guilty of this as well, but when I think about why I’m cannot come up with a reason. I’m comfortable with the alternative (recursion) and in many cases I have to think harder about a problem to formulate the solution in a loop rather than recursion.

For those of you who have not been schooled in the arts of recursion, in simple terms it involves a function calling itself or recursing until it finds a solution. A basic recursion has two portions: the base case, and the recursive case. The base case establishes a condition for returning, without it the recursion would be infinite. The recursive case is the case where the function needs to be called an additional time. To demonstrate this lets say we have an array of ten integers numbered 1 through 10 in order. I’ll write two functions for finding a value within that array, one using a loop and the other using recursion. Assume our array is called myArray and is already initialized.

<?php
function find($value)
{
     foreach($myArray as $x)
     {
          if($x == $value)
               return true;
     }
return false;
}
?>

<?php
function find($value, $position = 0)
{
     //this is an error case
     if($position > 9)
          return false;
     //this is our base case
     if($myArray[$position] == $value)
          return true;
     //this is our recursive case
     return find($value, $position + 1);
}
?>

A few things to take note of: First, our recursive version of the find function has a type of case I didn’t mention, an error case. Not every recursion will have an error case, but it must exist in case the value we are searching for does not exist in the array. Otherwise we would end up indexing outside of our array. A second thing to note is that the recursive version of the find function has a second parameter to keep track of the position in the array. The foreach loop in the loop version does not appear to have a value to keep track of our position but it still exists. Foreach is a shortcut syntax, the position is still being tracked but the programmer does not have to be aware of it (which is good in some cases, and bad in others).

Typically in recursive functions like the one above you want to be able to call it without having to give additional inputs for the recursion. This is possible in the case above because in PHP there exists default values. Above I default the variable position to 0 so even if that parameter isn’t given in the call the search will start at 0. In other languages this may not be possible, but there are alternatives. In java for instance there are no default values so we must rely on another feature: polymorphism. In java functions are identified by their signature, not their name. I can define a method foo that takes as input an integer and another method foo that takes as input a string. I’ll use this feature to implement the same recursive function in java.

public class RecursionTest {

     private int[] myArray; 

     public static void main(String[] args)
     {
          //assume myArray is initialized
          find(5);
     }

     private boolean find(int value)
     {
          return find(value, 0);
     }

     private boolean find(int value, int position)
     {
          //error case
          if(position > 9)
               return false;
          //base case
          if(myArray[position] == value)
               return true;
          //recursive case
          return find(value, position + 1);
     }
}

You may be asking “What’s the point of all this recursion stuff when the loop accomplishes the same thing?”. I have two answers. The first is performance and the second is modeling your problem. When you use a loop to solve a problem, any variables you create are allocated in the heap. Alternatively with recursion, your function calls are all placed in the stack.

Typically stack allocations are cleaner than heap allocations. The stack basically keeps track of function calls and their inputs. When a function is called it and its inputs are placed on the stack. When that function returns it and its inputs are removed from the stack. In this case all of the memory allocation occurs in sequence, the system doesn’t have to worry about searching for free space on the stack and the programmer doesn’t have to worry about making sure that information is deleted from the stack (in a non-garbage collected language I mean).

In the heap on the other hand, the runtime system must find memory large enough for your data to fit in, which could lead to fragmentation. When the data is no longer needed the memory must be marked as free.

Does this mean that loops are inferior to recursion? No. There are cases were a loop would perform better than a recursion.

Now, on to my second point: modeling your problem. Once you get comfortable with recursion you will find that there are some things that seem much simpler to code without loops. Recursion also forces you to create a function or method for a certain task rather than just throwing a loop into your code, which can lead to massive blobs of unorganized code. If you have trouble with organizing your code try recursion for a while and I guarantee you’ll produce code that is easier to deal with.

For the time being I’m going to set out to solve more problems with recursion rather than loops, just for the sake of being an outcast.

P.S. the title is a blue oyster cult reference and I don’t know why.