CSci 1301: Problem Set 11 (Tail-recursion)

Due: Thursday, December 9th at 11:59pm by e-mail.

As always, please include a contract, a purpose, examples, and tests for each function.

Problem 1 (8 points)

Define tail-recursive functions to

In comments briefly explain what makes your functions tail-recursive. The functions may take extra parameters (compared to their non-tail-recursive versions).

Problem 2 (5 points): a tail-recursive implementation of map

Write map-tail: a tail-recursive version of map. map-tail takes a list, a function applicable to list elements, and an accumulator list (i.e. the list of results). Just as a regular map, it returns a list of results of applying the function to each element of the list.

Define a function map1 that takes a list and a function and calls map-tail with the list, the function, and the initial value of the accumulator list. map1 should work exactly as the pre-defined map. Test your function to make sure that this is the case.

This is how map is implemented in Scheme/Racket.

CSci 1301 course web site.

The views and opinions expressed in this page are strictly those of the page author. The contents of this page have not been reviewed or approved by the University of Minnesota.