Skip to content
scrambled
Programming Language Theory Flashcard

How to use fix to define recursive functions?

Question

How to use fix to define recursive functions?

Answer

Sketch a normal recursive function as you will in regular programming languages:

tsx
function fact(n: number): number {
	if (n == 0) return 1;
	return n * fact(n - 1);
}

Rewrite it to a recursive variable definition:

tsx
const fact = function (n: number): number {
	if (n == 0) return 1;
	return n * fact(n - 1);
}

In Pure/Untyped lambda calculus, recursive definition like this is not possible as we don't really have an "assignment" operator, make the recursive function a parameter (a Self-replicator):

tsx
(fct) => (n) => {
	if (n == 0) return 1;
	return n * fct(n - 1);
}

Then, we can write it in Pure/Untyped lambda calculus as follows:

λfact. λn. if n=0 then 1 else n∗fact(n−1)

We can finally define the recursive function as:

fix λfact. λn. if n=0 then 1 else n∗fact(n−1)