Anonymous Recursion Examples

2025-02-27, Thu

Anynomous recursion1 is always interesting, if only for the sake of playing with formula and code. However, I tend to forget all the concepts and approaches to address them after a while. So better write down some examples based on Wikipedia entry2.

1. Lisp

Lisp code is a straightforward translation of the original lambda calculus: 

((lambda (f)
   ((lambda (x) (funcall f (funcall x x)))
    (lambda (x) (funcall f (funcall x x)))))
 (lambda (unused-param)
   (format t "func called")))

Try to evalute this snippet in SLIME, and the following error shows up:

Control stack exhausted (no more space for function call frames). This is probably due to heavily nested or infinitely recursive function calls, or a tail call that SBCL cannot or has not optimized away.

Try again as Emacs Lisp, got the following error in the *Messages* buffer.

cl-prin1: (excessive-lisp-nesting 1622) cl-prin1: (error "Lisp nesting exceeds ‘max-lisp-eval-depth’")

2. JavaScript

This is when the Scheme heritage of JavaScript shines. 

((f) =>
    ((x) => f(x(x)))
    ((x) => f(x(x)))
)
(
    () => "func called"
)

Try to evalute this snippet in browser and error "RangeError: Maximum call stack size exceeded." shows up.

More examples could be found on RosettaCode.org3.

Footnotes:

1

Anonymous Recursion: https://en.wikipedia.org/wiki/Anonymous_recursion

2

Fixed-Point Combinator: https://en.wikipedia.org/wiki/Fixed-point_combinator

3

RosettaCode examples on Y combinator: https://rosettacode.org/wiki/Y_combinator