[Lisp, ML, Haskell] Tail call/recursion/optimization

Many noob Lispers, including myself, have a hard time understanding, what is proper tail call/recursion/optimization, and what is not. Here is some code I've stole from Wikipedia. (Rewritten to pure C.)

#include <stdio.h>

int fact_iter(int n, int a)
{
        if (n==0)
                return a;
        return fact_iter(n-1, n*a);
};

int fact(int n)
{
        return fact_iter(n, 1);
};

void main()
{
        printf ("%d\n", fact(11));
};

So far, this is a recursive version of factorial. How can we optimize it? Remove recursion? Here is how (pure C again):

...
int fact_iter(int n, int a)
{
begin:
        if (n==0)
                return a;

        // modify arguments.
        // as if this function called again with new arguments:
        a=n*a;
        n=n-1;
        goto begin;
};
...

Ugly? "Go To Statement Considered Harmful"? Yes. A rare case, when function argument's modification is justified. But if the end of your function can be rewritten so manually, a Lisp compiler would be able to do this as well. This is what happens in low-level.

To write a tail-recursive function, think, if you can rewrite it in such a way.

On contrary, this function can't be rewritten (again, copy-pasted from Wikipedia), so a Lisp compiler couldn't optimize it (Python code):

def fact(n):
    if n == 0:
        return 1
    else:
        return n * fact(n - 1)

Aside from Lisp, ML dialects (OCaml, etc), Haskell also supports tail calls. But Python is not.

(the post first published at 20220506.)

List of my other blog posts.

Subscribe to my news feed

Yes, I know about these lousy Disqus ads. Please use adblocker. I would consider to subscribe to 'pro' version of Disqus if the signal/noise ratio in comments would be good enough.