How to define recursive function calls in functional programming languages using Quine's trick (aka the ‘Y’ and ‘Z’ combinators): the same demo in OCaml (with recursive types), Python, and Scheme

y-combinator-1-ocaml.txt

$ ocaml -rectypes
        OCaml version 4.13.1

# (* Initial version, with language recursion *)
  let rec fib = fun n -> if n<=1 then n else fib(n-1)+fib(n-2) ;;
val fib : int -> int = <fun>
# (* Testing *)
  List.map fib [0;1;2;3;4;5;6] ;;
- : int list = [0; 1; 1; 2; 3; 5; 8]
# (* Quine's trick: call this with itself as argument *)
  let protofib = fun self -> fun n -> if n<=1 then n else (self self)(n-1)+(self self)(n-2) ;;
val protofib : ('a -> int -> int as 'a) -> int -> int = <fun>
# let fib = protofib protofib ;;
val fib : int -> int = <fun>
# (* Testing *)
  List.map fib [0;1;2;3;4;5;6] ;;
- : int list = [0; 1; 1; 2; 3; 5; 8]
# (* The function we want to make recursive *)
  let prefib = fun fib -> fun n -> if n<=1 then n else fib(n-1)+fib(n-2) ;;
val prefib : (int -> int) -> int -> int = <fun>
# (* Automate Quine's trick: naïve version *)
  let ycomb = fun f -> (fun self -> f (self self)) (fun self -> f (self self)) ;;
val ycomb : ('a -> 'a) -> 'a = <fun>
# let fib = ycomb prefib ;;
Stack overflow during evaluation (looping recursion?).
# (* Automate Quine's trick: delayed version *)
  let zcomb = fun f -> (fun self -> f (fun v -> self self v)) (fun self -> f (fun v -> self self v)) ;;
val zcomb : (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b = <fun>
# let fib = zcomb prefib ;;
val fib : int -> int = <fun>
# (* Testing *)
  List.map fib [0;1;2;3;4;5;6] ;;
- : int list = [0; 1; 1; 2; 3; 5; 8]
# 

y-combinator-2-python.txt

$ python3
Python 3.11.2 (main, Apr 28 2025, 14:11:48) [GCC 12.2.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> # Initial version, with language recursion
>>> def fib(n): return (n if n<=1 else fib(n-1)+fib(n-2))
... 
>>> # Testing
>>> [fib(n) for n in range(7)]
[0, 1, 1, 2, 3, 5, 8]
>>> del(fib)
>>> # Quine's trick: call this with itself as argument
>>> protofib = lambda self: lambda n: n if n<=1 else (self(self))(n-1)+(self(self))(n-2)
>>> fib = protofib(protofib)
>>> # Testing
>>> [fib(n) for n in range(7)]
[0, 1, 1, 2, 3, 5, 8]
>>> del(fib)
>>> # The function we want to make recursive
>>> prefib = lambda fib: lambda n: n if n<=1 else fib(n-1)+fib(n-2)
>>> # Automate Quine's trick: naïve version
>>> ycomb = lambda f: (lambda self: f(self(self)))(lambda self: f(self(self)))
>>> fib = ycomb(prefib)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 1, in <lambda>
  File "<stdin>", line 1, in <lambda>
  File "<stdin>", line 1, in <lambda>
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded
>>> # Automate Quine's trick: delayed version
>>> zcomb = lambda f: (lambda self: f(lambda v: (self(self))(v)))(lambda self: f(lambda v: (self(self))(v)))
>>> fib = zcomb(prefib)
>>> # Testing
>>> [fib(n) for n in range(7)]
[0, 1, 1, 2, 3, 5, 8]
>>> 

y-combinator-3-scheme.txt

$ chezscheme
Chez Scheme Version 9.5.8
Copyright 1984-2022 Cisco Systems, Inc.

> ; Initial version, with language recursion
  (define (fib n) (if (<= n 1) n (+ (fib (- n 1)) (fib (- n 2)))))
> ; Testing
  (map fib '(0 1 2 3 4 5 6))
(0 1 1 2 3 5 8)
> ; Quine's trick: call this with itself as argument
  (define protofib (lambda (self) (lambda (n) (if (<= n 1) n (+ ((self self) (- n 1)) ((self self) (- n 2)))))))
> (define fib (protofib protofib))
> ; Testing
  (map fib '(0 1 2 3 4 5 6))
(0 1 1 2 3 5 8)
> ; The function we want to make recursive
  (define prefib (lambda (fib) (lambda (n) (if (<= n 1) n (+ (fib (- n 1)) (fib (- n 2)))))))
> ; Automate Quine's trick: naïve version
  (define ycomb (lambda (f) ((lambda (self) (f (self self))) (lambda (self) (f (self self))))))
> (define fib (ycomb prefib))
^Cbreak> r

> ; Automate Quine's trick: delayed version
  (define zcomb (lambda (f) ((lambda (self) (f (lambda (v) ((self self) v))))
                             (lambda (self) (f (lambda (v) ((self self) v)))))))
> (define fib (zcomb prefib))
> ; Testing
  (map fib '(0 1 2 3 4 5 6))
(0 1 1 2 3 5 8)
>