Tail Recursion Easy Solutions

Tail Recursion: Conceptual Solutions

Identifying Tail recursion

For each of the following functions, identify whether or not it is tail recursive and explain why.

(define (f1 x)
    (if (= x 0)
        1
        (if (= (remainder x 2) 0)
            (+ 1 (f1 (- x 1)))
            (+ x (f1 (- x 1))))))
Not tail recursive because in both of the recursive cases, there is a calculation that must be done after the recursive call.

(define (f2 x)
    (define (helper y z)
        (if (= y 0)
            z
            (helper (- y 1) (+ z y))))
    (helper x 0))
Yes, this function is tail recursive because there are no calculations after the recursive calls, so python only needs to keep one frame open.

(define (f3 x):
    (if (= x 0)
        0
        (f1 x)))
This function isn't actually recursive, so it can't be tail recursive.

Creating a tail recursive function

Turn the summer function into a tail recursive function. Hint: Use a helper function.

(define (summer num)
    (if (= x 0)
        0
        (+ num (summer (- num 1)))))
(define (summer num)
    (define (helper n total)
        (if (= x 0)
            total
            (helper (- n 1) (+ total n))))
    (helper num 0))

Code writing

Write a tail recursive function that takes in a list and reverses it.
> (define lst '(1 2 3 4 5))
> (reverse lst)
(5 4 3 2 1)
(define (reverse lst)
    (define (helper lst rev)
        (if (null? lst)
            rev
            (helper (cdr lst) (cons (car lst) rev))))
    (helper lst nil))