Tail Recursion: exam-level questions

If you need help reviewing Tail Recursion, take a look at these resources:

• Albert's and Robert's slides

Each question has a "Toggle Solution" button -- click it to reveal that question's solution.

Conceptual Questions

Which of the following Scheme functions are tail recursive?

(define (one x y)
    (if (or (= x 0) (= y 0) (= x y))
        1
        (if (< x y)
            (one x (- y x))
            (if (> x y)
                (one (- x y) y)))))

(define (two x)
    (if (or (= x 0) (= x 1))
        x
        (+ (two (- x 1)) (two (- x 2)))))

(define (three n curr next)
    (if (= n 0)
        curr
        (three (- n 1) next (+ curr next))))

(define (four n total)
    (cond ((= n 0) 0)
          ((even? n) (four (- n 1) total))
          (else (four (- n 2) (+ total n)))))

Code-Writing questions

Question 1

Write a function map that is tail recursive. It should take in a list lst and a function fn, and apply the function onto every element in the list.

(define (map fn lst)
    ; YOUR CODE HERE
    )

scm> (map (lambda (x) (* x x)) '(1 2 3 4))
(1 4 9 16)

You should use a helper function. Also, the built-in append function, which concatenates two lists together, should prove useful.

(define (map fn lst)
    (define (map-help lst so-far)
        (if (null? lst)
            so-far
            (map-help (cdr lst)
                      (append so-far (list (fn (car lst)))))))
    (map-help lst nil))

Question 2

Write a function filter that is tail recursive. It should take in a list lst and a function pred, and keep only the elements in the list that satisfy the predicate.

(define (filter pred lst)
    ; YOUR CODE HERE
    )

scm> (filter even? '(1 2 3 4))
(2 4)

Hint: You should use a helper. Also, the built-in append function, which concatenates two lists together, should prove useful.

(define (filter pred lst)
    (define (filter-help lst so-far)
        (cond ((null? lst) so-far)
              ((pred (car lst))
                    (filter-help (cdr lst)
                                 (append so-far (list (car lst)))))
              (else (filter-help (cdr lst) so-far))))
    (filter-help lst nil))

Question 3

Write a function insert that is tail recursive. It should take in a list lst, an item, and an index, and insert the item into the list at the given index.

(define (insert lst item index)
    ; YOUR CODE HERE
    )

scm> (insert '(1 2 3 4) 100 2)
(1 2 100 3 4)
scm> (insert nil 10 4)
(10)

You should use a helper. Also, the built-in append function, which concatenates two lists together, should prove useful.

(define (insert lst item index)
    (define (insert-help lst index so-far)
        (if (or (null? lst) (= index 0))
            (append so-far
                    (cons item lst))
            (insert-help (cdr lst)
                         (- index 1)
                         (append so-far (list (car lst))))))
    (insert-help lst index nil))

Question 4

Write a function remove that is tail recursive. It should take in a list lst and an item, and remove the first occurence of item in the list. If item item doesn't occur, just return the original list.

(define (remove lst item)
    ; YOUR CODE HERE
    )

scm> (remove '(1 2 3 4) 3))
(1 2 4)
scm> (remove '(1 3 5) 6)
(1 3 5)
scm> (remove nil 100)
()

Hint: You should use a helper. Also, the built-in append function, which concatenates two lists together, should prove useful.

(define (remove lst item)
    (define (remove-help lst so-far)
        (cond ((null? lst) so-far)
              ((eq? (car lst) item) (append so-far (cdr lst)))
              (else (remove-help (cdr lst)
                                 (append so-far (list (car lst)))))))
    (remove-help lst nil))

Question 5

Write a function pop that is tail recursive. It should take in a list lst and an index, and remove the item in the list at the given index. If the index is out of bounds, just return the original list.

(define (pop lst index)
    ; YOUR CODE HERE
    )

scm> (pop '(1 2 3 4) 2))
(1 2 4)
scm> (pop '(1 3 5) 2)
(1 3)
scm> (pop nil 8)
()

Hint: You should use a helper. Also, the built-in append function, which concatenates two lists together, should prove useful.

(define (pop lst index)
    (define (pop-help lst index so-far)
        (cond ((null? lst) so-far)
              ((= index 0) (append so-far (cdr lst)))
              (else (pop-help (cdr lst)
                              (- index 1)
                              (append so-far (list (car lst)))))))
    (pop-help lst index nil))