CS 61A

This page is under construction!

Scheme supports optimized tail recursion, meaning that if a function is called in tail context, Scheme will close the frame that called it and simply return the value that the tail call returns. Scheme thus allows for an unbounded number of tail calls, unlike Python, which will raise a RuntimeError: 'maximum recursion depth exceeded' because all the frames stay open.

To write a tail-call optimized function in Scheme, you must make all recursive calls in a tail context.

Tail Context

An expression is in a tail context if it is the last expression to be evaluated in the frame. Thus, a call expression is a tail call if it is one of the following:

• the last sub-expression in the body of a tail-context lambda expression
• the second or third sub-expression in a tail-context if expression
• a non-predicate sub-expression in a tail-context cond expression
• the last sub-expression in a tail-context and or or expression
• the last sub-expression in a tail-context begin expression

A function is then tail recursive if the recursive call(s) is a/are tail call(s).

Test your understanding

Answer these questions for the following functions.

1. What are the tail calls?
2. Are the recursive calls tail calls?
3. Is the function tail recursive?

(define (foo x y)
    (if (> x y) 
        (foo (- x y)) 
        (+ x y)))

1. (foo (- x y)) is a tail call because it is the second subexpression in the if expresssion. (+ x y) is also a tail call because it is the third subexpression in the if expression.
2. Yes, the recursive call (foo (- x y)) is a tail call.
3. Yes, because the recursive call is a tail call.

TOGGLE SOLUTION

(define (bar x)
    (if (bar x) x
        (- (bar 9) 1))

1. (- (bar 9) 1) is a tail call because it is the third subexpression in the if expresssion.
2. The recursive calls (bar x) is not a tail call because it is the first subexpression in the if expression. The recursive call (bar 9) is also not a tail call because it is an argument of the tail call.
3. No, because the recursive calls are not tail calls.

TOGGLE SOLUTION

(define (baz x)
    (cond ((bar x) (begin (foo x x) (baz (+ x x))))
        ((baz 1) (baz 2))
        (else (and (foo x 1) #t (bar 4))))
      )

1. (baz (+ x x)) is a tail call because it is the last subexpression in a tail-context begin expression. (baz 2) is a tail call because it is a non-predicate subexpression in the cond expression. (bar 4) is a tail call because it is the last subexpression in a tail-context and expression.
2. Two of the tail calls mentioned above are recursive calls. The recursive call (baz 1) is not a tail call because it is a predicate subexpression in the cond expression.
3. No, even though there are two recursive tail calls, there is a recursive call that is not a tail call.

TOGGLE SOLUTION

Writing tail recursive functions

Often, you may find it easier to first come up with an iterative solution in Python and convert it into a tail recursive Scheme solution. For example, let’s try to write a function that makes a list out of the first n elements of a given lst (assume lst is at least length n). If you want to try this out on your own first, click here.

To do this, we would start with an empty result list and keep a counter, adding elements to result from lst until our counter hits n. Here’s the iterative Python version for a linked list:

def keep_first_n(link, n):
    i, result = 0, Link.empty
    while i < n:
        result = Link(link.first, result)
        link = link.rest
        i += 1
    return result

Since there are no while loops in Scheme, we can imitate this using a helper function! A helper function will keep track of variables that change in its parameters! In this case, the counter i, our result list, and the link pointer change, so our helper function will take in three parameters i, result, and lst.

(define (keep-first-n lst n)
  (define (keep-helper i result lst)

    ))

To simulate the while condition, we use a base case to return our result when we’re done. We want to stop adding to result and return it when i is equal to n. Whatever happens in the while loop will go in the “else” case.

(define (keep-first-n lst n)
  (define (keep-helper i result)
      (if (= i n) result)
    ))

So far, so good. Now we need to take care of what goes on in the while loop, which is updating result, lst, and i. Using recursion, we simply update our “variables” by passing their new values as arguments to a recursive call.

(define (keep-first-n lst n)
  (define (keep-helper i result)
      (if (= i n) result
        (keep-helper (+ i 1) (append result (list (car lst))) (cdr lst)))
    ))

Almost done! All that’s left to do now is initialize our “variables”. To do this, call our helper function in the body of the original function with the initial values as arguments.

(define (keep-first-n lst n)
  (define (helper i result lst)
      (if (= i n) result
        (helper (+ i 1) (append result (list (car lst))) (cdr lst)))
    )
  (helper 0 '() lst))

This function is now a tail-recursive version of the iterative solution!