ICOM 4035 – Data Structures

Fall 2007

Laboratory 5: Recursion

1.    Objectives

1. Understand the concept of recursion.
2. Compare recursion with iteration.
3. Implement recursion algorithms.

2.    Overview

This laboratory will focus on the concept of recursion. Recursion is a technique used commonly on advanced data structures to iterate it in an easier manner. It involves the step a function calling itself over and over until a base condition is met. For example let us consider the factorial function which returns the product of n*(n-1)*(n-2)*…*1.

Iterative form:

int Factorial(int n) throws InvalidParameterException

{

if(n < 0)

throw new InvalidParameterException(“Factorial():  n must be positive.”);

if(n == 0)

{

return 1;

}

int factorial = 1;

for(int i = 2; i <= n; ++i)

{

factorial *= i;

}

return factorial;

}

Recursive form:

int Factorial(int n) throws InvalidParameterException

{

if(n < 0)

throw new InvalidParameterException(“Factorial(): n must be positive.”);

if(n == 0 || n == 1)

{

return 1;

}

return n*Factorial(n – 1);

}

Both solutions as you can observe are O(n), however in this case the recursive form is slower do to some issues regarding the activation record of a function. The activation record is a space in memory (stack) which is reserved to store important information about the process being run. Among this information one can find the return address of the function (where the next line is located after the functions ends) along with the function parameters.

Each time a function is called an activation record is created thus making the recursion solutions less efficient than iterative solutions, due to speed and the chance of causing a StackOverflowError which occurs when the the JVM runs out of memory. For this reason recursion is commonly used for problems that are too complex to formulate an iterative solution to it.

3.    Practice

For this laboratory you are asked to implement a method which appends data to a single linked list (LinkedList.java) using recursion. Next run the MainTester.java file which has two more testers inside, an iterative tester and a recursive tester. Observe how the execution time of both solutions varies for the same number of elements. Now change the parameters inside the loops of LoopTester.java and RecursionTester.java from 1000 to 10000 and run MainTester.java again to see what happens. If a StackOverflowException occurs catch it and run the test again. Compare the results.