Hi se7en,
It's quite difficult for me to explain this in English but I *do* think the functions I posted are tail recursive.
A way to see if a LISP recursive function is tail recursive is to trace the function. If the last call on the stack returns the final result, then the function is tail recursive.
Example with the famous factorial function:
fact1 is not tail recursive:
(defun fact1 (n)
(if (<= n 1)
1
(* n (fact1 (1- n)))
)
)
fact2 calls
f which is tail recursive (with an accumulator):
(defun fact2 (n / f)
(defun f (n a)
(if (<= n 1)
a
(f (1- n) (* n a))
)
)
(f n 1)
)
Tracing both: (trace fact1 f) and running: (fact1 5) (fact2 5), the vlide trace window displays:
Saisie (FACT1 5)
Saisie (FACT1 4)
Saisie (FACT1 3)
Saisie (FACT1 2)
Saisie (FACT1 1)
Résultat: 1
Résultat: 2
Résultat: 6
Résultat: 24
Résultat: 120
Saisie (F 5 1)
Saisie (F 4 5)
Saisie (F 3 20)
Saisie (F 2 60)
Saisie (F 1 120)
Résultat: 120
Résultat: 120
Résultat: 120
Résultat: 120
Résultat: 120
Doing the same thing with the
memb function (wich is tail recursive without accumulator) and the
trunc function (the complementary function which is not tail recursive:
(defun memb (ele lst)
(if lst
(if (equal (car lst) ele)
lst
(memb ele (cdr lst))
)
)
)
(defun trunc (ele lst)
(if lst
(if (equal (car lst) ele)
nil
(cons (car lst) (trunc ele (cdr lst)))
)
)
)
Tracing both (trace memb trunc) and runing (memb 2 '(0 1 2 3)) (trunc 2 '(0 1 2 3)):
Saisie (MEMB 2 (0 1 2 3))
Saisie (MEMB 2 (1 2 3))
Saisie (MEMB 2 (2 3))
Résultat: (2 3)
Résultat: (2 3)
Résultat: (2 3)
Saisie (TRUNC 2 (0 1 2 3))
Saisie (TRUNC 2 (1 2 3))
Saisie (TRUNC 2 (2 3))
Résultat: nil
Résultat: (1)
Résultat: (0 1)
In both examples, with non tail recursive functions (
fact1 and
trunc) the last call calls the recursive function within another statement: (* n (fact1 (1- n))) and (cons (car lst) (trunc ele (cdr lst))) so that the final result can't be solved until unstacking.
With the tail recusive functions (
f and
memb) the last call directly calls the function: (f (1- n) (* n a)) and (memb ele (cdr lst)) and the final result is returned soon the head of the stack.
If you're no more comfortable with LISP, you can try with F# (which optimises the tail recursion).
Here're F# traductions of the
memb and
trunc functions, you can try
here if you do not have F# (VS 2010) installed.
let rec memb ele lst =
match lst with
| [] -> []
| h::t when h = ele -> lst
| _ -> memb ele lst.Tail
let rec trunc ele lst =
match lst with
| [] -> []
| h::t when h = ele -> []
| _ -> lst.Head :: trunc ele lst.Tail
Then, try:
memb 199999 [0 .. 200000]
and
trunc 199999 [0 .. 200000]
The return in F# interactive should be:
> memb 199999 [0 .. 200000];;
val it : int list = [199999; 200000]
> trunc 199999 [0 .. 200000];;
Session termination detected. Press Enter to restart.
Process is terminated due to StackOverflowException.