**ICOM 4035 – Data Structures**

**Fall 2007**

**Laboratory 5: Recursion**

**1.
****Objectives**

- Understand the concept of recursion.
- Compare recursion with iteration.
- 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.

To download the source files click here.