Tail Recursion: basic

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

Question 1

What is tail call optimization? What is the benefit to using it?

Tail call optimization is a compiler/interpreter optimization that makes memory usage more efficient for recursion. Normally, each recursive call requires a new frame, and each frame needs to stick around until all of the recursive calls are done. With tail call optimization, once we move on to the next recursive call, the old frame gets discarded, leaving only one frame in memory at a time.

Question 2

What is a tail context, in terms of Scheme? Why are tail contexts important for tail call optimization?

A tail context is a location in a Scheme function that the interpreter can identify as tail recursive. A Scheme function needs to be written in a particular way in order for the interpreter to realize that it should perform tail call optimization. The following are tail contexts:

The last sub-expression in the body of a lambda
The 2nd and 3rd sub-expression in an if
All non-predicate sub-expressions in a cond
The last sub-expression in and or or
The last sub-expression in a begin

Question 3

Which of the following Scheme functions are tail recursive?

(define (one x)
    (if (= x 0)
        1
        (* x (one (- x 1)))))

(define (two x so-far)
    (if (= x 0)
        so-far
        (two (- x 1) (* so-far x))))

(define (three fn x)
    (cond ((null? x) #t)
          ((not (fn (car x))) #f)
          (else (three fn (cdr x)))))

(define (four fn x)
    (if (null? x)
        #t
        (and (four fn (cdr x)) (fn x))))

one: not tail recursive
two: tail recursive
three: tail recursive
four: not tail recursive

Code-Writing question

Question 4

Write a function reverse that is tail recursive. It should take a list lst and return the reverse of that list.

(define (reverse lst)
    ; YOUR CODE HERE
    )

scm> (reverse '(1 2 3 4))
(4 3 2 1)
scm> (reverse nil)
()

Hint: You should use a helper function.

(define (reverse lst)
    (define (reverse-help lst so-far)
        (if (null? lst)
            so-far
            (reverse-help (cdr lst) (cons (car lst) so-far))))
    (reverse-help lst nil))

Question 5

Write a function reduce that is tail recursive. It should take a list lst, combiner function, and a start value, and reduce all the elements in the list using the combiner, beginnning at start.

(define (reduce combiner lst start)
    ; YOUR CODE HERE
    )

scm> (reduce + '(1 2 3 4) 0)
10
scm> (reduce - '(1 2 3 4) 0)
-10
scm> (reduce + '(1 2 3 4) 10)
20
scm> (reduce * '(1 2 3 4) 1)
24

(define (reduce combiner lst start)
    (if (null? lst)
        start
        (reduce combiner (cdr lst) (combiner start (car lst)))))

Question 6

Write a function all that is tail recursive. It should take a list lst and a function pred, and return true (#t) only if all the elements in the list satisfy the predicate.

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

scm> (all '(1 2 3 4) even?)
#f
scm> (all '(1 3 5) odd?)
#t

(define (all lst pred)
    (if (null? lst)
        #t
        (and (pred (car lst)) (all (cdr lst) pred))))

Question 7

Write a function count that is tail recursive. It should take a list lst and an item, and return the number of times that item occurs in the list.

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

scm> (count '(1 2 3 4) 3)
1
scm> (count '(2 3) 5)
0
scm> (count '(2 2 4 2 3) 2)
3

(define (count lst item)
    (define (count-help lst num)
        (cond ((null? lst) num)
              ((eq? (car lst) item) (count-help (cdr lst) (+ num 1)))
              (else (count-help (cdr lst) num))))
    (count-help lst 0))

Tail Recursion: basic-level questions