# Tail Recursion: basic-level questions

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

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))))``````
1. `one`: not tail recursive
2. `two`: tail recursive
3. `three`: tail recursive
4. `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)
)

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

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

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

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))``````