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