[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.

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.