As we have seen in class a recursive solution to some problems may be very efficient. On the other hand, depending on how a language implements parameter passing, there may be extra costs to recursive solutions to some problems. In this lab we will time some different recursive solutions to a simple problem, the problem of summing the elements of a numerical list. We will also see how to save the results to a file.
First, write a subroutine that takes a list of numbers as its only parameter, uses a loop to calculate the sum of the list, and returns the sum. The main program should ask for the size of the list, create a list with that many random numbers, start a timer, call the subroutine, and print the amount of time it took. Run this a few times until you find a size that takes ten seconds or so.
Next, try a simple recursive solution:
if the list has a single element, return the value of that element
otherwise, remove one element from the list,
calculate the sum of the rest of the list recursively, and
return the sum of this value plus the removed element
You can use your previous routine to check that this routine returns the correct value. Experiment with this subroutine until you find a size that takes about a second, then modify the main program so that it loops through a series of increasing sizes, timing each experiment separately. For each experiment it should write the size and number of seconds to a file. To open a file:
open TIMING, ">timefile";
This will create a file in the current directory named "timefile". TIMING is the filehandle, a way of referring to this file from now on in your program, and the ">" sign signifies that "timefile" will be an output file. If "timefile" already exists it will be set to empty. (If you wanted to add to an existing file you would use ">>", and if you wanted to read from a file you would use "<".) The file should be opened just once, so don't put this inside the loop. To print to the file, use the filehandle in the print statement:
print TIMING "$size\t$seconds\n";
where the \t inserts a tab between the numbers, and the \n ends the line. You should observe a series of rapidly increasing times that are much larger than when the subroutine used a loop. The main reason for this is that Perl copies the array that is passed to each recursive call.
The above program may have given you a warning message about "deep recusrion", so let's try to make the recursion more efficient. The recursion will be much shallower if we split the array in half, and use two recursive calls to sum the two halves of the array:
if the list has a single element, return the value of that element
otherwise, remove half the elements from the list, adding them to a new list,
calculate the sums of both halves recursively, and
return the sum of these two values
Call this subroutine from the main program in the same way the previous recursive solution was called, and write the results to a file with a different name. If you have access to a spreadsheet you should be able to copy or read the results into a new spreadsheet and plot a curve to see how the running times increase for both (or all three) experiments.