## 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

- Find the smallest element in the list
- To insert an element into a sorted list in order

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.