Homework6: Tail Recursion
Due: In class on Tuesday, April 26, 2014
(NO LATE SUBMISSIONS WILL BE ACCEPTED!!!)

Presentation By: TBD on April 26.

"A function call is said to be tail recursive if there is nothing to do after the function returns except return its value." -- Scott Walters For more information click here.

Implement 2 recursive functions sequential sum and the tower of hanoi. Sequential sum takes 2 integers, begin and end, and sums all values between begin and end recursively: int sum(int begin,int end). The tower of hanoi function takes a number of disks and returns the optimal number of steps to a solution. First implement the functions with standard recursion. Then convert each recursive function to a tail recursive function. (Hint: work through sequential sum implementations before tower of hanoi implementations).

You may write these functions in any language of your choice but use the same language for all implementations for comparison purposes.

Time the performance of your standard recursive functions and tail recursive functions by calling them with different sizes and discuss the performance differences. Your write up should discuss the theoretical and empirical time complexity and call complexity (number of recursive calls per N) of each algorithm, and how tail recursion helps with the call complexity.

What to hand in:

A write-up including:

1. A table/plot showing the time taken to run each function with the sizes you chose. (Please ensure that these are nicely formatted and in readable form.)
2. A description of the time and call complexities for each program.
3. A short discussion of what is gained by using tail recursive calls
4. A printout of your recursive functions. (in the appendix)

Back to CS330 Materials