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