I've heard often about "tail recursive" functions but never really tried to understand them. However, recently I've been bitten by not knowing what they are. I wrote the following OCaml code:

let rec apply_n_times n f x =
if n = 0 then
x
else
f (apply_n_times (n-1) f x);;

Now, that's not tail recursive, as bogklug at

TopCoder noted. With this version my program ended with a stack overflow error. The problem magicaly disappears in the tail recursive version:

let rec apply_n_times n f x =
if n = 0 then
x
else
apply_n_times (n-1) f (f x);;

It may seem like a trivial change but think about how would you transform these functions into loops. For the first one it is not obvious at all. You would probably need a stack if you don't do some VERY smart optimizations. But the second one is simple; in C++:

while (true)
{
if (n == 0) return x;
x = f(x);
n = n-1;
}

It is almost the same code. The structure is: stop condition followed by recursive function arguments (n, x) recomputation. This transformation into a simple loop with no stack is possible for every tail recursive function. A general form for a tail recursive function is:

rec_f(a1, ..., an) =
if stop(a1, ..., an) then
base_case(a1, ..., an)
else
rec_f(f1(a1, ..., an), ..., fn(a1, ..., an))

For some functions it is not obvious how you can express them as such. For example the simple implementation of factorial is NOT tail recursive:

let rec fact n =
if n = 0 then
1
else
n * fact (n-1);;

But it can be transformed by introducing an auxiliary function that looks like the recursive call: fact_aux(m, n) = m * n!, and expressing the factorial as n! = fact_aux(1, n). Here it is:

let rec fact_aux m n =
if n = 0 then
m
else
fact_aux (m*n) (n-1);;
let fact n = fact_aux 1 n;;

I'm guessing this technique can be applied to more general situations as well.

## No comments:

## Post a Comment

Note: (1) You need to have third-party cookies enabled in order to comment on Blogger. (2) Better to copy your comment before hitting publish/preview. Blogger sometimes eats comments on the first try, but the second works. Crazy Blogger.