In strict functional programming and the lambda calculus, functions (lambda expressions) don't have state and are only allowed to refer to arguments of enclosing functions.

This rules out the usual definition of a recursive function wherein a function is associated with the state of a variable and this variable's state is used in the body of the function.

The   Y combinator   is itself a stateless function that, when applied to another stateless function, returns a recursive version of the function.

The Y combinator is the simplest of the class of such functions, called fixed-point combinators.



Task

Define the stateless   Y combinator   and use it to compute factorials and Fibonacci numbers from other stateless functions or lambda expressions.



Cf

 Jim Weirich: Adventures in Functional Programming


Private Function call_fn(f As String, n As Long) As Long
    call_fn = Application.Run(f, f, n)
End Function
 
Private Function Y(f As String) As String
    Y = f
End Function
 
Private Function fac(self As String, n As Long) As Long
    If n > 1 Then
        fac = n * call_fn(self, n - 1)
    Else
        fac = 1
    End If
End Function
 
Private Function fib(self As String, n As Long) As Long
    If n > 1 Then
        fib = call_fn(self, n - 1) + call_fn(self, n - 2)
    Else
        fib = n
    End If
End Function
 
Private Sub test(name As String)
    Dim f As String: f = Y(name)
    Dim i As Long
    Debug.Print name
    For i = 1 To 10
        Debug.Print call_fn(f, i);
    Next i
    Debug.Print
End Sub
 
Public Sub main()
    test "fac"
    test "fib"
End Sub