{{task|Classic CS problems and programs}} {{requires|First class functions}} [[Category:Recursion]]

In strict [[wp:Functional programming|functional programming]] and the [[wp:lambda calculus|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 [http://mvanier.livejournal.com/2897.html 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 [[wp:Fixed-point combinator|fixed-point combinators]].

;Task: Define the stateless Y combinator and use it to compute [[wp:Factorial|factorials]] and [[wp:Fibonacci number|Fibonacci numbers]] from other stateless functions or lambda expressions.

;Cf:

• [http://vimeo.com/45140590 Jim Weirich: Adventures in Functional Programming]

ALGOL 68

{{trans|Python}} Note: This specimen retains the original [[#Python|Python]] coding style. {{wont work with|ALGOL 68|Revision 1 - scoping extensions to language used.}} {{works with|ALGOL 68S|from Amsterdam Compiler Kit ( [[wp:Guido van Rossum|Guido van Rossum]]'s teething ring) with runtime scope checking turned off.}}

BEGIN
  MODE F = PROC(INT)INT;
  MODE Y = PROC(Y)F;

# compare python Y = lambda f: (lambda x: x(x)) (lambda y: f( lambda *args: y(y)(*args)))#
  PROC y =      (PROC(F)F f)F: (  (Y x)F: x(x)) (  (Y z)F: f((INT arg )INT: z(z)( arg )));

  PROC fib = (F f)F: (INT n)INT: CASE n IN n,n OUT f(n-1) + f(n-2) ESAC;

  FOR i TO 10 DO print(y(fib)(i)) OD
END

AppleScript

AppleScript is not particularly "functional" friendly. It can, however, support the Y combinator.

AppleScript does not have anonymous functions, but it does have anonymous objects. The code below implements the latter with the former (using a handler (i.e. function) named 'lambda' in each anonymous object).

Unfortunately, an anonymous object can only be created in its own statement ('script'...'end script' can not be in an expression). Thus, we have to apply Y to the automatic 'result' variable that holds the value of the previous statement.

The identifier used for Y uses "pipe quoting" to make it obviously distinct from the y used inside the definition.

-- Y COMBINATOR ---------------------------------------------------------------

on |Y|(f)
    script
        on |λ|(y)
            script
                on |λ|(x)
                    y's |λ|(y)'s |λ|(x)
                end |λ|
            end script

            f's |λ|(result)
        end |λ|
    end script

    result's |λ|(result)
end |Y|


-- TEST -----------------------------------------------------------------------
on run

    -- Factorial
    script fact
        on |λ|(f)
            script
                on |λ|(n)
                    if n = 0 then return 1
                    n * (f's |λ|(n - 1))
                end |λ|
            end script
        end |λ|
    end script


    -- Fibonacci
    script fib
        on |λ|(f)
            script
                on |λ|(n)
                    if n = 0 then return 0
                    if n = 1 then return 1
                    (f's |λ|(n - 2)) + (f's |λ|(n - 1))
                end |λ|
            end script
        end |λ|
    end script

    {facts:map(|Y|(fact), enumFromTo(0, 11)), fibs:map(|Y|(fib), enumFromTo(0, 20))}

    --> {facts:{1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800},

    --> fibs:{0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987,
    --           1597, 2584, 4181, 6765}}

end run


-- GENERIC FUNCTIONS FOR TEST -------------------------------------------------

-- map :: (a -> b) -> [a] -> [b]
on map(f, xs)
    tell mReturn(f)
        set lng to length of xs
        set lst to {}
        repeat with i from 1 to lng
            set end of lst to |λ|(item i of xs, i, xs)
        end repeat
        return lst
    end tell
end map

-- enumFromTo :: Int -> Int -> [Int]
on enumFromTo(m, n)
    if n < m then
        set d to -1
    else
        set d to 1
    end if
    set lst to {}
    repeat with i from m to n by d
        set end of lst to i
    end repeat
    return lst
end enumFromTo

-- Lift 2nd class handler function into 1st class script wrapper
-- mReturn :: Handler -> Script
on mReturn(f)
    if class of f is script then
        f
    else
        script
            property |λ| : f
        end script
    end if
end mReturn

{{Out}}

{facts:{1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800},
fibs:{0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765}}

ARM Assembly

{{works with|as|Raspberry Pi}}

/* ARM assembly Raspberry PI  */
/*  program Ycombi.s   */

/* REMARK 1 : this program use routines in a include file
   see task Include a file language arm assembly
   for the routine affichageMess conversion10
   see at end of this program the instruction include */

/* Constantes    */
.equ STDOUT, 1                           @ Linux output console
.equ EXIT,   1                           @ Linux syscall
.equ WRITE,  4                           @ Linux syscall


/*******************************************/
/* Structures                               */
/********************************************/
/* structure function*/
    .struct  0
func_fn:                    @ next element
    .struct  func_fn + 4
func_f_:                    @ next element
    .struct  func_f_ + 4
func_num:
    .struct  func_num + 4
func_fin:

/* Initialized data */
.data
szMessStartPgm:            .asciz "Program start \n"
szMessEndPgm:              .asciz "Program normal end.\n"
szMessError:               .asciz "\033[31mError Allocation !!!\n"

szFactorielle:             .asciz "Function factorielle : \n"
szFibonacci:               .asciz "Function Fibonacci : \n"
szCarriageReturn:          .asciz "\n"

/* datas message display */
szMessResult:            .ascii "Result value :"
sValue:                  .space 12,' '
                         .asciz "\n"

/* UnInitialized data */
.bss

/*  code section */
.text
.global main
main:                                           @ program start
    ldr r0,iAdrszMessStartPgm                   @ display start message
    bl affichageMess
    adr r0,facFunc                              @ function factorielle address
    bl YFunc                                    @ create Ycombinator
    mov r5,r0                                   @ save Ycombinator
    ldr r0,iAdrszFactorielle                    @ display message
    bl affichageMess
    mov r4,#1                                   @ loop counter
1:  @ start loop
    mov r0,r4
    bl numFunc                                  @ create number structure
    cmp r0,#-1                                  @ allocation error ?
    beq 99f
    mov r1,r0                                   @ structure number address
    mov r0,r5                                   @ Ycombinator address
    bl callFunc                                 @ call
    ldr r0,[r0,#func_num]                       @ load result
    ldr r1,iAdrsValue                           @ and convert ascii string
    bl conversion10
    ldr r0,iAdrszMessResult                     @ display result message
    bl affichageMess
    add r4,#1                                   @ increment loop counter
    cmp r4,#10                                  @ end ?
    ble 1b                                      @ no -> loop
/*********Fibonacci  *************/
    adr r0,fibFunc                              @ function factorielle address
    bl YFunc                                    @ create Ycombinator
    mov r5,r0                                   @ save Ycombinator
    ldr r0,iAdrszFibonacci                      @ display message
    bl affichageMess
    mov r4,#1                                   @ loop counter
2:  @ start loop
    mov r0,r4
    bl numFunc                                  @ create number structure
    cmp r0,#-1                                  @ allocation error ?
    beq 99f
    mov r1,r0                                   @ structure number address
    mov r0,r5                                   @ Ycombinator address
    bl callFunc                                 @ call
    ldr r0,[r0,#func_num]                       @ load result
    ldr r1,iAdrsValue                           @ and convert ascii string
    bl conversion10
    ldr r0,iAdrszMessResult                     @ display result message
    bl affichageMess
    add r4,#1                                   @ increment loop counter
    cmp r4,#10                                  @ end ?
    ble 2b                                      @ no -> loop
    ldr r0,iAdrszMessEndPgm                     @ display end message
    bl affichageMess
    b 100f
99:                                             @ display error message
    ldr r0,iAdrszMessError
    bl affichageMess
100:                                            @ standard end of the program
    mov r0, #0                                  @ return code
    mov r7, #EXIT                               @ request to exit program
    svc 0                                       @ perform system call
iAdrszMessStartPgm:        .int szMessStartPgm
iAdrszMessEndPgm:          .int szMessEndPgm
iAdrszFactorielle:         .int szFactorielle
iAdrszFibonacci:           .int szFibonacci
iAdrszMessError:           .int szMessError
iAdrszCarriageReturn:      .int szCarriageReturn
iAdrszMessResult:          .int szMessResult
iAdrsValue:                .int sValue
/******************************************************************/
/*     factorielle function                         */
/******************************************************************/
/* r0 contains the Y combinator address  */
/* r1 contains the number structure  */
facFunc:
    push {r1-r3,lr}             @ save  registers
    mov r2,r0                   @ save Y combinator address
    ldr r0,[r1,#func_num]       @ load number
    cmp r0,#1                   @ > 1 ?
    bgt 1f                      @ yes
    mov r0,#1                   @ create structure number value 1
    bl numFunc
    b 100f
1:
    mov r3,r0                   @ save number
    sub r0,#1                   @ decrement number
    bl numFunc                  @ and create new structure number
    cmp r0,#-1                  @ allocation error ?
    beq 100f
    mov r1,r0                   @ new structure number -> param 1
    ldr r0,[r2,#func_f_]        @ load function address to execute
    bl callFunc                 @ call
    ldr r1,[r0,#func_num]       @ load new result
    mul r0,r1,r3                @ and multiply by precedent
    bl numFunc                  @ and create new structure number
                                @ and return her address in r0
100:
    pop {r1-r3,lr}              @ restaur registers
    bx lr                       @ return
/******************************************************************/
/*     fibonacci function                         */
/******************************************************************/
/* r0 contains the Y combinator address  */
/* r1 contains the number structure  */
fibFunc:
    push {r1-r4,lr}             @ save  registers
    mov r2,r0                   @ save Y combinator address
    ldr r0,[r1,#func_num]       @ load number
    cmp r0,#1                   @ > 1 ?
    bgt 1f                      @ yes
    mov r0,#1                   @ create structure number value 1
    bl numFunc
    b 100f
1:
    mov r3,r0                   @ save number
    sub r0,#1                   @ decrement number
    bl numFunc                  @ and create new structure number
    cmp r0,#-1                  @ allocation error ?
    beq 100f
    mov r1,r0                   @ new structure number -> param 1
    ldr r0,[r2,#func_f_]        @ load function address to execute
    bl callFunc                 @ call
    ldr r4,[r0,#func_num]       @ load new result
    sub r0,r3,#2                @ new number - 2
    bl numFunc                  @ and create new structure number
    cmp r0,#-1                  @ allocation error ?
    beq 100f
    mov r1,r0                   @ new structure number -> param 1
    ldr r0,[r2,#func_f_]        @ load function address to execute
    bl callFunc                 @ call
    ldr r1,[r0,#func_num]       @ load new result
    add r0,r1,r4                @ add two results
    bl numFunc                  @ and create new structure number
                                @ and return her address in r0
100:
    pop {r1-r4,lr}              @ restaur registers
    bx lr                       @ return
/******************************************************************/
/*     call function                         */
/******************************************************************/
/* r0 contains the address of the function  */
/* r1 contains the address of the function 1 */
callFunc:
    push {r2,lr}                                @ save  registers
    ldr r2,[r0,#func_fn]                        @ load function address to execute
    blx r2                                      @ and call it
    pop {r2,lr}                                 @ restaur registers
    bx lr                                       @ return
/******************************************************************/
/*     create Y combinator function                         */
/******************************************************************/
/* r0 contains the address of the function  */
YFunc:
    push {r1,lr}                                @ save  registers
    mov r1,#0
    bl newFunc
    cmp r0,#-1                                  @ allocation error ?
    strne r0,[r0,#func_f_]                      @ store function and return in r0
    pop {r1,lr}                                 @ restaur registers
    bx lr                                       @ return
/******************************************************************/
/*     create structure number function                         */
/******************************************************************/
/* r0 contains the number  */
numFunc:
    push {r1,r2,lr}                             @ save  registers
    mov r2,r0                                   @ save number
    mov r0,#0                                   @ function null
    mov r1,#0                                   @ function null
    bl newFunc
    cmp r0,#-1                                  @ allocation error ?
    strne r2,[r0,#func_num]                     @ store number in new structure
    pop {r1,r2,lr}                              @ restaur registers
    bx lr                                       @ return
/******************************************************************/
/*     new function                                               */
/******************************************************************/
/* r0 contains the function address   */
/* r1 contains the function address 1   */
newFunc:
    push {r2-r7,lr}                             @ save  registers
    mov r4,r0                                   @ save address
    mov r5,r1                                   @ save adresse 1
    @ allocation place on the heap
    mov r0,#0                                   @ allocation place heap
    mov r7,#0x2D                                @ call system 'brk'
    svc #0
    mov r3,r0                                   @ save address heap for output string
    add r0,#func_fin                            @ reservation place one element
    mov r7,#0x2D                                @ call system 'brk'
    svc #0
    cmp r0,#-1                                  @ allocation error
    beq 100f
    mov r0,r3
    str r4,[r0,#func_fn]                        @ store address
    str r5,[r0,#func_f_]
    mov r2,#0
    str r2,[r0,#func_num]                       @ store zero to number
100:
    pop {r2-r7,lr}                              @ restaur registers
    bx lr                                       @ return
/***************************************************/
/*      ROUTINES INCLUDE                 */
/***************************************************/
.include "../affichage.inc"

{{output}}

Program start
Function factorielle :
Result value :1
Result value :2
Result value :6
Result value :24
Result value :120
Result value :720
Result value :5040
Result value :40320
Result value :362880
Result value :3628800
Function Fibonacci :
Result value :1
Result value :2
Result value :3
Result value :5
Result value :8
Result value :13
Result value :21
Result value :34
Result value :55
Result value :89
Program normal end.

ATS

(* ****** ****** *)
//
#include "share/atspre_staload.hats"
//
(* ****** ****** *)
//
fun
myfix
{a:type}
(
 f: lazy(a) -<cloref1> a
) : lazy(a) = $delay(f(myfix(f)))
//
val
fact =
myfix{int-<cloref1>int}
(
lam(ff) => lam(x) => if x > 0 then x * !ff(x-1) else 1
)
(* ****** ****** *)
//
implement main0 () = println! ("fact(10) = ", !fact(10))
//
(* ****** ****** *)

BlitzMax

BlitzMax doesn't support anonymous functions or classes, so everything needs to be explicitly named.

SuperStrict

'Boxed type so we can just use object arrays for argument lists
Type Integer
	Field val:Int
	Function Make:Integer(_val:Int)
		Local i:Integer = New Integer
		i.val = _val
		Return i
	End Function
End Type


'Higher-order function type - just a procedure attached to a scope
Type Func Abstract
	Method apply:Object(args:Object[]) Abstract
End Type

'Function definitions - extend with fields as locals and implement apply as body
Type Scope Extends Func Abstract
	Field env:Scope

	'Constructor - bind an environment to a procedure
	Function lambda:Scope(env:Scope) Abstract

	Method _init:Scope(_env:Scope)	'Helper to keep constructors small
		env = _env ; Return Self
	End Method
End Type


'Based on the following definition:
'(define (Y f)
'    (let ((_r (lambda (r) (f (lambda a (apply (r r) a))))))
'      (_r _r)))

'Y (outer)
Type Y Extends Scope
	Field f:Func	'Parameter - gets closed over

	Function lambda:Scope(env:Scope)	'Necessary due to highly limited constructor syntax
		Return (New Y)._init(env)
	End Function

	Method apply:Func(args:Object[])
		f = Func(args[0])
		Local _r:Func = YInner1.lambda(Self)
		Return Func(_r.apply([_r]))
	End Method
End Type

'First lambda within Y
Type YInner1 Extends Scope
	Field r:Func	'Parameter - gets closed over

	Function lambda:Scope(env:Scope)
		Return (New YInner1)._init(env)
	End Function

	Method apply:Func(args:Object[])
		r = Func(args[0])
		Return Func(Y(env).f.apply([YInner2.lambda(Self)]))
	End Method
End Type

'Second lambda within Y
Type YInner2 Extends Scope
	Field a:Object[]	'Parameter - not really needed, but good for clarity

	Function lambda:Scope(env:Scope)
		Return (New YInner2)._init(env)
	End Function

	Method apply:Object(args:Object[])
		a = args
		Local r:Func = YInner1(env).r
		Return Func(r.apply([r])).apply(a)
	End Method
End Type


'Based on the following definition:
'(define fac (Y (lambda (f)
'                 (lambda (x)
'                   (if (<= x 0) 1 (* x (f (- x 1)))))))

Type FacL1 Extends Scope
	Field f:Func	'Parameter - gets closed over

	Function lambda:Scope(env:Scope)
		Return (New FacL1)._init(env)
	End Function

	Method apply:Object(args:Object[])
		f = Func(args[0])
		Return FacL2.lambda(Self)
	End Method
End Type

Type FacL2 Extends Scope
	Function lambda:Scope(env:Scope)
		Return (New FacL2)._init(env)
	End Function

	Method apply:Object(args:Object[])
		Local x:Int = Integer(args[0]).val
		If x <= 0 Then Return Integer.Make(1) ; Else Return Integer.Make(x * Integer(FacL1(env).f.apply([Integer.Make(x - 1)])).val)
	End Method
End Type


'Based on the following definition:
'(define fib (Y (lambda (f)
'                 (lambda (x)
'                   (if (< x 2) x (+ (f (- x 1)) (f (- x 2)))))))

Type FibL1 Extends Scope
	Field f:Func	'Parameter - gets closed over

	Function lambda:Scope(env:Scope)
		Return (New FibL1)._init(env)
	End Function

	Method apply:Object(args:Object[])
		f = Func(args[0])
		Return FibL2.lambda(Self)
	End Method
End Type

Type FibL2 Extends Scope
	Function lambda:Scope(env:Scope)
		Return (New FibL2)._init(env)
	End Function

	Method apply:Object(args:Object[])
		Local x:Int = Integer(args[0]).val
		If x < 2
			Return Integer.Make(x)
		Else
			Local f:Func = FibL1(env).f
			Local x1:Int = Integer(f.apply([Integer.Make(x - 1)])).val
			Local x2:Int = Integer(f.apply([Integer.Make(x - 2)])).val
			Return Integer.Make(x1 + x2)
		EndIf
	End Method
End Type


'Now test
Local _Y:Func = Y.lambda(Null)

Local fac:Func = Func(_Y.apply([FacL1.lambda(Null)]))
Print Integer(fac.apply([Integer.Make(10)])).val

Local fib:Func = Func(_Y.apply([FibL1.lambda(Null)]))
Print Integer(fib.apply([Integer.Make(10)])).val

Bracmat

The lambda abstraction

 (λx.x)y

translates to

 /('(x.$x))$y

in Bracmat code. Likewise, the fixed point combinator

Y := λg.(λx.g (x x)) (λx.g (x x))

the factorial

G := λr. λn.(1, if n = 0; else n × (r (n−1)))

the Fibonacci function

H := λr. λn.(1, if n = 1 or n = 2; else (r (n−1)) + (r (n−2)))

and the calls

(Y G) i

and

(Y H) i

where i varies between 1 and 10, are translated into Bracmat as shown below

(   ( Y
    = /(
       ' ( g
         .   /('(x.$g'($x'$x)))
           $ /('(x.$g'($x'$x)))
         )
       )
    )
  & ( G
    = /(
       ' ( r
         . /(
            ' ( n
              .   $n:~>0&1
                | $n*($r)$($n+-1)
              )
            )
         )
       )
    )
  & ( H
    = /(
       ' ( r
         . /(
            ' ( n
              .   $n:(1|2)&1
                | ($r)$($n+-1)+($r)$($n+-2)
              )
            )
         )
       )
    )
  & 0:?i
  &   whl
    ' ( 1+!i:~>10:?i
      & out$(str$(!i "!=" (!Y$!G)$!i))
      )
  & 0:?i
  &   whl
    ' ( 1+!i:~>10:?i
      & out$(str$("fib(" !i ")=" (!Y$!H)$!i))
      )
  &
)

{{out}}

1!=1
2!=2
3!=6
4!=24
5!=120
6!=720
7!=5040
8!=40320
9!=362880
10!=3628800
fib(1)=1
fib(2)=1
fib(3)=2
fib(4)=3
fib(5)=5
fib(6)=8
fib(7)=13
fib(8)=21
fib(9)=34
fib(10)=55

C

C doesn't have first class functions, so we demote everything to second class to match.

#include <stdio.h>
#include <stdlib.h>

/* func: our one and only data type; it holds either a pointer to
   a function call, or an integer.  Also carry a func pointer to
   a potential parameter, to simulate closure                   */
typedef struct func_t *func;
typedef struct func_t {
        func (*fn) (func, func);
        func _;
        int num;
} func_t;

func new(func(*f)(func, func), func _) {
        func x = malloc(sizeof(func_t));
        x->fn = f;
        x->_ = _;       /* closure, sort of */
        x->num = 0;
        return x;
}

func call(func f, func n) {
        return f->fn(f, n);
}

func Y(func(*f)(func, func)) {
        func g = new(f, 0);
        g->_ = g;
        return g;
}

func num(int n) {
        func x = new(0, 0);
        x->num = n;
        return x;
}


func fac(func self, func n) {
        int nn = n->num;
        return nn > 1   ? num(nn * call(self->_, num(nn - 1))->num)
                        : num(1);
}

func fib(func self, func n) {
        int nn = n->num;
        return nn > 1
                ? num(  call(self->_, num(nn - 1))->num +
                        call(self->_, num(nn - 2))->num )
                : num(1);
}

void show(func n) { printf(" %d", n->num); }

int main() {
        int i;
        func f = Y(fac);
        printf("fac: ");
        for (i = 1; i < 10; i++)
                show( call(f, num(i)) );
        printf("\n");

        f = Y(fib);
        printf("fib: ");
        for (i = 1; i < 10; i++)
                show( call(f, num(i)) );
        printf("\n");

        return 0;
}

{{out}}

fac:  1 2 6 24 120 720 5040 40320 362880
fib:  1 2 3 5 8 13 21 34 55

C#

Like many other statically typed languages, this involves a recursive type, and like other strict languages, it is the Z-combinator instead.

The combinator here is expressed entirely as a lambda expression and is a static property of the generic YCombinator class. Both it and the RecursiveFunc type thus "inherit" the type parameters of the containing class—there effectively exists a separate specialized copy of both for each generic instantiation of YCombinator.

''Note: in the code, Func<T, TResult> is a delegate type (the CLR equivalent of a function pointer) that has a parameter of type T and return type of TResult. See [[Higher-order functions#C#]] or [https://docs.microsoft.com/en-us/dotnet/standard/delegates-lambdas the documentation] for more information.''

using System;

static class YCombinator<T, TResult>
{
    // RecursiveFunc is not needed to call Fix() and so can be private.
    private delegate Func<T, TResult> RecursiveFunc(RecursiveFunc r);

    public static Func<Func<Func<T, TResult>, Func<T, TResult>>, Func<T, TResult>> Fix { get; } =
        f => ((RecursiveFunc)(g => f(x => g(g)(x))))(g => f(x => g(g)(x)));
}

static class Program
{
    static void Main()
    {
        var fac = YCombinator<int, int>.Fix(f => x => x < 2 ? 1 : x * f(x - 1));
        var fib = YCombinator<int, int>.Fix(f => x => x < 2 ? x : f(x - 1) + f(x - 2));

        Console.WriteLine(fac(10));
        Console.WriteLine(fib(10));
    }
}

{{out}}

3628800
55

Alternatively, with a non-generic holder class (note that Fix is now a method, as properties cannot be generic):

static class YCombinator
{
    private delegate Func<T, TResult> RecursiveFunc<T, TResult>(RecursiveFunc<T, TResult> r);

    public static Func<T, TResult> Fix<T, TResult>(Func<Func<T, TResult>, Func<T, TResult>> f)
        => ((RecursiveFunc<T, TResult>)(g => f(x => g(g)(x))))(g => f(x => g(g)(x)));
}

Using the late-binding offered by dynamic to eliminate the recursive type:

static class YCombinator<T, TResult>
{
    public static Func<Func<Func<T, TResult>, Func<T, TResult>>, Func<T, TResult>> Fix { get; } =
        f => ((Func<dynamic, Func<T, TResult>>)(g => f(x => g(g)(x))))((Func<dynamic, Func<T, TResult>>)(g => f(x => g(g)(x))));
}

The usual version using recursion, disallowed by the task (implemented as a generic method):

static class YCombinator
{
    static Func<T, TResult> Fix<T, TResult>(Func<Func<T, TResult>, Func<T, TResult>> f) => x => f(Fix(f))(x);
}

Translations

To compare differences in language and runtime instead of in approaches to the task, the following are translations of solutions from other languages. Two versions of each translation are provided, one seeking to resemble the original as closely as possible, and another that is identical in program control flow but syntactically closer to idiomatic C#.

====[http://rosettacode.org/mw/index.php?oldid=287744#C++ C++]==== std::function<TResult(T)> in C++ corresponds to Func<T, TResult> in C#.

'''Verbatim'''

using Func = System.Func<int, int>;
using FuncFunc = System.Func<System.Func<int, int>, System.Func<int, int>>;

static class Program {
    struct RecursiveFunc<F> {
        public System.Func<RecursiveFunc<F>, F> o;
    }

    static System.Func<A, B> Y<A, B>(System.Func<System.Func<A, B>, System.Func<A, B>> f) {
        var r = new RecursiveFunc<System.Func<A, B>>() {
            o = new System.Func<RecursiveFunc<System.Func<A, B>>, System.Func<A, B>>((RecursiveFunc<System.Func<A, B>> w) => {
                return f(new System.Func<A, B>((A x) => {
                    return w.o(w)(x);
                }));
            })
        };
        return r.o(r);
    }

    static FuncFunc almost_fac = (Func f) => {
        return new Func((int n) => {
            if (n <= 1) return 1;
            return n * f(n - 1);
        });
    };

    static FuncFunc almost_fib = (Func f) => {
        return new Func((int n) => {
            if (n <= 2) return 1;
            return f(n - 1) + f(n - 2);
        });
    };

    static int Main() {
        var fib = Y(almost_fib);
        var fac = Y(almost_fac);
        System.Console.WriteLine("fib(10) = " + fib(10));
        System.Console.WriteLine("fac(10) = " + fac(10));
        return 0;
    }
}

'''Semi-idiomatic'''

using System;

using FuncFunc = System.Func<System.Func<int, int>, System.Func<int, int>>;

static class Program {
    struct RecursiveFunc<F> {
        public Func<RecursiveFunc<F>, F> o;
    }

    static Func<A, B> Y<A, B>(Func<Func<A, B>, Func<A, B>> f) {
        var r = new RecursiveFunc<Func<A, B>> {
            o = w => f(x => w.o(w)(x))
        };
        return r.o(r);
    }

    static FuncFunc almost_fac = f => n => n <= 1 ? 1 : n * f(n - 1);

    static FuncFunc almost_fib = f => n => n <= 2 ? 1 : f(n - 1) + f(n - 2);

    static void Main() {
        var fib = Y(almost_fib);
        var fac = Y(almost_fac);
        Console.WriteLine("fib(10) = " + fib(10));
        Console.WriteLine("fac(10) = " + fac(10));
    }
}

====[http://rosettacode.org/mw/index.php?oldid=287744#Ceylon Ceylon]==== TResult(T) in Ceylon corresponds to Func<T, TResult> in C#.

Since C# does not have local classes, RecursiveFunc and y1 are declared in a class of their own. Moving the type parameters to the class also prevents type parameter inference.

'''Verbatim'''

using System;
using System.Diagnostics;

class Program {
    public delegate TResult ParamsFunc<T, TResult>(params T[] args);

    static class Y<Result, Args> {
        class RecursiveFunction {
            public Func<RecursiveFunction, ParamsFunc<Args, Result>> o;
            public RecursiveFunction(Func<RecursiveFunction, ParamsFunc<Args, Result>> o) => this.o = o;
        }

        public static ParamsFunc<Args, Result> y1(
                Func<ParamsFunc<Args, Result>, ParamsFunc<Args, Result>> f) {

            var r = new RecursiveFunction((RecursiveFunction w)
                => f((Args[] args) => w.o(w)(args)));

            return r.o(r);
        }
    }

    static ParamsFunc<Args, Result> y2<Args, Result>(
            Func<ParamsFunc<Args, Result>, ParamsFunc<Args, Result>> f) {

        Func<dynamic, ParamsFunc<Args, Result>> r = w => {
            Debug.Assert(w is Func<dynamic, ParamsFunc<Args, Result>>);
            return f((Args[] args) => w(w)(args));
        };

        return r(r);
    }

    static ParamsFunc<Args, Result> y3<Args, Result>(
            Func<ParamsFunc<Args, Result>, ParamsFunc<Args, Result>> f)
        => (Args[] args) => f(y3(f))(args);

    static void Main() {
        var factorialY1 = Y<int, int>.y1((ParamsFunc<int, int> fact) => (int[] x)
            => (x[0] > 1) ? x[0] * fact(x[0] - 1) : 1);

        var fibY1 = Y<int, int>.y1((ParamsFunc<int, int> fib) => (int[] x)
            => (x[0] > 2) ? fib(x[0] - 1) + fib(x[0] - 2) : 2);

        Console.WriteLine(factorialY1(10)); // 362880
        Console.WriteLine(fibY1(10));       // 110
    }
}

'''Semi-idiomatic'''

using System;
using System.Diagnostics;

static class Program {
    delegate TResult ParamsFunc<T, TResult>(params T[] args);

    static class Y<Result, Args> {
        class RecursiveFunction {
            public Func<RecursiveFunction, ParamsFunc<Args, Result>> o;
            public RecursiveFunction(Func<RecursiveFunction, ParamsFunc<Args, Result>> o) => this.o = o;
        }

        public static ParamsFunc<Args, Result> y1(
                Func<ParamsFunc<Args, Result>, ParamsFunc<Args, Result>> f) {

            var r = new RecursiveFunction(w => f(args => w.o(w)(args)));

            return r.o(r);
        }
    }

    static ParamsFunc<Args, Result> y2<Args, Result>(
            Func<ParamsFunc<Args, Result>, ParamsFunc<Args, Result>> f) {

        Func<dynamic, ParamsFunc<Args, Result>> r = w => {
            Debug.Assert(w is Func<dynamic, ParamsFunc<Args, Result>>);
            return f(args => w(w)(args));
        };

        return r(r);
    }

    static ParamsFunc<Args, Result> y3<Args, Result>(
            Func<ParamsFunc<Args, Result>, ParamsFunc<Args, Result>> f)
        => args => f(y3(f))(args);

    static void Main() {
        var factorialY1 = Y<int, int>.y1(fact => x => (x[0] > 1) ? x[0] * fact(x[0] - 1) : 1);
        var fibY1 = Y<int, int>.y1(fib => x => (x[0] > 2) ? fib(x[0] - 1) + fib(x[0] - 2) : 2);

        Console.WriteLine(factorialY1(10));
        Console.WriteLine(fibY1(10));
    }
}

====[http://rosettacode.org/mw/index.php?oldid=287744#Go Go]==== func(T) TResult in Go corresponds to Func<T, TResult> in C#.

'''Verbatim'''

using System;

// Func and FuncFunc can be defined using using aliases and the System.Func<T, TReult> type, but RecursiveFunc must be a delegate type of its own.
using Func = System.Func<int, int>;
using FuncFunc = System.Func<System.Func<int, int>, System.Func<int, int>>;

delegate Func RecursiveFunc(RecursiveFunc f);

static class Program {
    static void Main() {
        var fac = Y(almost_fac);
        var fib = Y(almost_fib);
        Console.WriteLine("fac(10) = " + fac(10));
        Console.WriteLine("fib(10) = " + fib(10));
    }

    static Func Y(FuncFunc f) {
        RecursiveFunc g = delegate (RecursiveFunc r) {
            return f(delegate (int x) {
                return r(r)(x);
            });
        };
        return g(g);
    }

    static Func almost_fac(Func f) {
        return delegate (int x) {
            if (x <= 1) {
                return 1;
            }
            return x * f(x-1);
        };
    }

    static Func almost_fib(Func f) {
        return delegate (int x) {
            if (x <= 2) {
                return 1;
            }
            return f(x-1)+f(x-2);
        };
    }
}

Recursive:

    static Func Y(FuncFunc f) {
        return delegate (int x) {
            return f(Y(f))(x);
        };
    }

'''Semi-idiomatic'''

using System;

delegate int Func(int i);
delegate Func FuncFunc(Func f);
delegate Func RecursiveFunc(RecursiveFunc f);

static class Program {
    static void Main() {
        var fac = Y(almost_fac);
        var fib = Y(almost_fib);
        Console.WriteLine("fac(10) = " + fac(10));
        Console.WriteLine("fib(10) = " + fib(10));
    }

    static Func Y(FuncFunc f) {
        RecursiveFunc g = r => f(x => r(r)(x));
        return g(g);
    }

    static Func almost_fac(Func f) => x => x <= 1 ? 1 : x * f(x - 1);

    static Func almost_fib(Func f) => x => x <= 2 ? 1 : f(x - 1) + f(x - 2);
}

Recursive:

    static Func Y(FuncFunc f) => x => f(Y(f))(x);

====[http://rosettacode.org/mw/index.php?oldid=287744#Java Java]====

'''Verbatim'''

Since Java uses interfaces and C# uses delegates, which are the only type that the C# compiler will coerce lambda expressions to, this code declares a Functions class for providing a means of converting CLR delegates to objects that implement the Function and RecursiveFunction interfaces.

using System;

static class Program {
    interface Function<T, R> {
        R apply(T t);
    }

    interface RecursiveFunction<F> : Function<RecursiveFunction<F>, F> {
    }

    static class Functions {
        class Function<T, R> : Program.Function<T, R> {
            readonly Func<T, R> _inner;

            public Function(Func<T, R> inner) => this._inner = inner;

            public R apply(T t) => this._inner(t);
        }

        class RecursiveFunction<F> : Function<Program.RecursiveFunction<F>, F>, Program.RecursiveFunction<F> {
            public RecursiveFunction(Func<Program.RecursiveFunction<F>, F> inner) : base(inner) {
            }
        }

        public static Program.Function<T, R> Create<T, R>(Func<T, R> inner) => new Function<T, R>(inner);
        public static Program.RecursiveFunction<F> Create<F>(Func<Program.RecursiveFunction<F>, F> inner) => new RecursiveFunction<F>(inner);
    }

    static Function<A, B> Y<A, B>(Function<Function<A, B>, Function<A, B>> f) {
        var r = Functions.Create<Function<A, B>>(w => f.apply(Functions.Create<A, B>(x => w.apply(w).apply(x))));
        return r.apply(r);
    }

    static void Main(params String[] arguments) {
        Function<int, int> fib = Y(Functions.Create<Function<int, int>, Function<int, int>>(f => Functions.Create<int, int>(n =>
            (n <= 2)
              ? 1
              : (f.apply(n - 1) + f.apply(n - 2))))
        );
        Function<int, int> fac = Y(Functions.Create<Function<int, int>, Function<int, int>>(f => Functions.Create<int, int>(n =>
            (n <= 1)
              ? 1
              : (n * f.apply(n - 1))))
        );

        Console.WriteLine("fib(10) = " + fib.apply(10));
        Console.WriteLine("fac(10) = " + fac.apply(10));
    }
}

'''"Idiomatic"'''

For demonstrative purposes, to completely avoid using CLR delegates, lambda expressions can be replaced with explicit types that implement the functional interfaces. Closures are thus implemented by replacing all usages of the original local variable with a field of the type that represents the lambda expression; this process, called "hoisting" is actually how variable capturing is implemented by the C# compiler (for more information, see [https://blogs.msdn.microsoft.com/abhinaba/2005/10/18/c-anonymous-methods-are-not-closures/ this Microsoft blog post].

using System;

static class YCombinator {
    interface Function<T, R> {
        R apply(T t);
    }

    interface RecursiveFunction<F> : Function<RecursiveFunction<F>, F> {
    }

    static class Y<A, B> {
        class __1 : RecursiveFunction<Function<A, B>> {
            class __2 : Function<A, B> {
                readonly RecursiveFunction<Function<A, B>> w;

                public __2(RecursiveFunction<Function<A, B>> w) {
                    this.w = w;
                }

                public B apply(A x) {
                    return w.apply(w).apply(x);
                }
            }

            Function<Function<A, B>, Function<A, B>> f;

            public __1(Function<Function<A, B>, Function<A, B>> f) {
                this.f = f;
            }

            public Function<A, B> apply(RecursiveFunction<Function<A, B>> w) {
                return f.apply(new __2(w));
            }
        }

        public static Function<A, B> _(Function<Function<A, B>, Function<A, B>> f) {
            var r = new __1(f);
            return r.apply(r);
        }
    }

    class __1 : Function<Function<int, int>, Function<int, int>> {
        class __2 : Function<int, int> {
            readonly Function<int, int> f;

            public __2(Function<int, int> f) {
                this.f = f;
            }

            public int apply(int n) {
                return
                    (n <= 2)
                  ? 1
                  : (f.apply(n - 1) + f.apply(n - 2));
            }
        }

        public Function<int, int> apply(Function<int, int> f) {
            return new __2(f);
        }
    }

    class __2 : Function<Function<int, int>, Function<int, int>> {
        class __3 : Function<int, int> {
            readonly Function<int, int> f;

            public __3(Function<int, int> f) {
                this.f = f;
            }

            public int apply(int n) {
                return
                    (n <= 1)
                  ? 1
                  : (n * f.apply(n - 1));
            }
        }

        public Function<int, int> apply(Function<int, int> f) {
            return new __3(f);
        }
    }

    static void Main(params String[] arguments) {
        Function<int, int> fib = Y<int, int>._(new __1());
        Function<int, int> fac = Y<int, int>._(new __2());

        Console.WriteLine("fib(10) = " + fib.apply(10));
        Console.WriteLine("fac(10) = " + fac.apply(10));
    }
}

'''C# 1.0'''

To conclude this chain of decreasing reliance on language features, here is above code translated to C# 1.0. The largest change is the replacement of the generic interfaces with the results of manually substituting their type parameters.

using System;

class Program {
    interface Func {
        int apply(int i);
    }

    interface FuncFunc {
        Func apply(Func f);
    }

    interface RecursiveFunc {
        Func apply(RecursiveFunc f);
    }

    class Y {
        class __1 : RecursiveFunc {
            class __2 : Func {
                readonly RecursiveFunc w;

                public __2(RecursiveFunc w) {
                    this.w = w;
                }

                public int apply(int x) {
                    return w.apply(w).apply(x);
                }
            }

            readonly FuncFunc f;

            public __1(FuncFunc f) {
                this.f = f;
            }

            public Func apply(RecursiveFunc w) {
                return f.apply(new __2(w));
            }
        }

        public static Func _(FuncFunc f) {
            __1 r = new __1(f);
            return r.apply(r);
        }
    }

    class __fib : FuncFunc {
        class __1 : Func {
            readonly Func f;

            public __1(Func f) {
                this.f = f;
            }

            public int apply(int n) {
                return
                    (n <= 2)
                  ? 1
                  : (f.apply(n - 1) + f.apply(n - 2));
            }

        }

        public Func apply(Func f) {
            return new __1(f);
        }
    }

    class __fac : FuncFunc {
        class __1 : Func {
            readonly Func f;

            public __1(Func f) {
                this.f = f;
            }

            public int apply(int n) {
                return
                    (n <= 1)
                  ? 1
                  : (n * f.apply(n - 1));
            }
        }

        public Func apply(Func f) {
            return new __1(f);
        }
    }

    static void Main(params String[] arguments) {
        Func fib = Y._(new __fib());
        Func fac = Y._(new __fac());

        Console.WriteLine("fib(10) = " + fib.apply(10));
        Console.WriteLine("fac(10) = " + fac.apply(10));
    }
}

'''Modified/varargs (the last implementation in the Java section)'''

Since C# delegates cannot declare members, extension methods are used to simulate doing so.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;

static class Func {
    public static Func<T, TResult2> andThen<T, TResult, TResult2>(
            this Func<T, TResult> @this,
            Func<TResult, TResult2> after)
        => _ => after(@this(_));
}

delegate OUTPUT SelfApplicable<OUTPUT>(SelfApplicable<OUTPUT> s);
static class SelfApplicable {
    public static OUTPUT selfApply<OUTPUT>(this SelfApplicable<OUTPUT> @this) => @this(@this);
}

delegate FUNCTION FixedPoint<FUNCTION>(Func<FUNCTION, FUNCTION> f);

delegate OUTPUT VarargsFunction<INPUTS, OUTPUT>(params INPUTS[] inputs);
static class VarargsFunction {
    public static VarargsFunction<INPUTS, OUTPUT> from<INPUTS, OUTPUT>(
            Func<INPUTS[], OUTPUT> function)
        => function.Invoke;

    public static VarargsFunction<INPUTS, OUTPUT> upgrade<INPUTS, OUTPUT>(
            Func<INPUTS, OUTPUT> function) {
        return inputs => function(inputs[0]);
    }

    public static VarargsFunction<INPUTS, OUTPUT> upgrade<INPUTS, OUTPUT>(
            Func<INPUTS, INPUTS, OUTPUT> function) {
        return inputs => function(inputs[0], inputs[1]);
    }

    public static VarargsFunction<INPUTS, POST_OUTPUT> andThen<INPUTS, OUTPUT, POST_OUTPUT>(
            this VarargsFunction<INPUTS, OUTPUT> @this,
            VarargsFunction<OUTPUT, POST_OUTPUT> after) {
        return inputs => after(@this(inputs));
    }

    public static Func<INPUTS, OUTPUT> toFunction<INPUTS, OUTPUT>(
            this VarargsFunction<INPUTS, OUTPUT> @this) {
        return input => @this(input);
    }

    public static Func<INPUTS, INPUTS, OUTPUT> toBiFunction<INPUTS, OUTPUT>(
            this VarargsFunction<INPUTS, OUTPUT> @this) {
        return (input, input2) => @this(input, input2);
    }

    public static VarargsFunction<PRE_INPUTS, OUTPUT> transformArguments<PRE_INPUTS, INPUTS, OUTPUT>(
            this VarargsFunction<INPUTS, OUTPUT> @this,
            Func<PRE_INPUTS, INPUTS> transformer) {
        return inputs => @this(inputs.AsParallel().AsOrdered().Select(transformer).ToArray());
    }
}

delegate FixedPoint<FUNCTION> Y<FUNCTION>(SelfApplicable<FixedPoint<FUNCTION>> y);

static class Program {
    static TResult Cast<TResult>(this Delegate @this) where TResult : Delegate {
        return (TResult)Delegate.CreateDelegate(typeof(TResult), @this.Target, @this.Method);
    }

    static void Main(params String[] arguments) {
        BigInteger TWO = BigInteger.One + BigInteger.One;

        Func<IFormattable, long> toLong = x => long.Parse(x.ToString());
        Func<IFormattable, BigInteger> toBigInteger = x => new BigInteger(toLong(x));

        /* Based on https://gist.github.com/aruld/3965968/#comment-604392 */
        Y<VarargsFunction<IFormattable, IFormattable>> combinator = y => f => x => f(y.selfApply()(f))(x);
        FixedPoint<VarargsFunction<IFormattable, IFormattable>> fixedPoint =
            combinator.Cast<SelfApplicable<FixedPoint<VarargsFunction<IFormattable, IFormattable>>>>().selfApply();

        VarargsFunction<IFormattable, IFormattable> fibonacci = fixedPoint(
            f => VarargsFunction.upgrade(
                toBigInteger.andThen(
                    n => (IFormattable)(
                        (n.CompareTo(TWO) <= 0)
                        ? 1
                        : BigInteger.Parse(f(n - BigInteger.One).ToString())
                            + BigInteger.Parse(f(n - TWO).ToString()))
                )
            )
        );

        VarargsFunction<IFormattable, IFormattable> factorial = fixedPoint(
            f => VarargsFunction.upgrade(
                toBigInteger.andThen(
                    n => (IFormattable)((n.CompareTo(BigInteger.One) <= 0)
                        ? 1
                        : n * BigInteger.Parse(f(n - BigInteger.One).ToString()))
                )
            )
        );

        VarargsFunction<IFormattable, IFormattable> ackermann = fixedPoint(
            f => VarargsFunction.upgrade(
                (BigInteger m, BigInteger n) => m.Equals(BigInteger.Zero)
                    ? n + BigInteger.One
                    : f(
                        m - BigInteger.One,
                        n.Equals(BigInteger.Zero)
                            ? BigInteger.One
                            : f(m, n - BigInteger.One)
                    )
            ).transformArguments(toBigInteger)
        );

        var functions = new Dictionary<String, VarargsFunction<IFormattable, IFormattable>>();
        functions.Add("fibonacci", fibonacci);
        functions.Add("factorial", factorial);
        functions.Add("ackermann", ackermann);

        var parameters = new Dictionary<VarargsFunction<IFormattable, IFormattable>, IFormattable[]>();
        parameters.Add(functions["fibonacci"], new IFormattable[] { 20 });
        parameters.Add(functions["factorial"], new IFormattable[] { 10 });
        parameters.Add(functions["ackermann"], new IFormattable[] { 3, 2 });

        functions.AsParallel().Select(
            entry => entry.Key
                + "[" + String.Join(", ", parameters[entry.Value].Select(x => x.ToString())) + "]"
                + " = "
                + entry.Value(parameters[entry.Value])
        ).ForAll(Console.WriteLine);
    }
}

====[http://rosettacode.org/mw/index.php?oldid=287744#Swift Swift]==== T -> TResult in Swift corresponds to Func<T, TResult> in C#.

'''Verbatim'''

The more idiomatic version doesn't look much different.

using System;

static class Program {
    struct RecursiveFunc<F> {
        public Func<RecursiveFunc<F>, F> o;
    }

    static Func<A, B> Y<A, B>(Func<Func<A, B>, Func<A, B>> f) {
        var r = new RecursiveFunc<Func<A, B>> { o = w => f(_0 => w.o(w)(_0)) };
        return r.o(r);
    }

    static void Main() {
        // C# can't infer the type arguments to Y either; either it or f must be explicitly typed.
        var fac = Y((Func<int, int> f) => _0 => _0 <= 1 ? 1 : _0 * f(_0 - 1));
        var fib = Y((Func<int, int> f) => _0 => _0 <= 2 ? 1 : f(_0 - 1) + f(_0 - 2));

        Console.WriteLine($"fac(5) = {fac(5)}");
        Console.WriteLine($"fib(9) = {fib(9)}");
    }
}

Without recursive type:

    public static Func<A, B> Y<A, B>(Func<Func<A, B>, Func<A, B>> f) {
        Func<dynamic, Func<A, B>> r = z => { var w = (Func<dynamic, Func<A, B>>)z; return f(_0 => w(w)(_0)); };
        return r(r);
    }

Recursive:

    public static Func<In, Out> Y<In, Out>(Func<Func<In, Out>, Func<In, Out>> f) {
        return x => f(Y(f))(x);
    }

C++

{{works with|C++11}} Known to work with GCC 4.7.2. Compile with g++ --std=c++11 ycomb.cc

#include <iostream>
#include <functional>

template <typename F>
struct RecursiveFunc {
	std::function<F(RecursiveFunc)> o;
};

template <typename A, typename B>
std::function<B(A)> Y (std::function<std::function<B(A)>(std::function<B(A)>)> f) {
	RecursiveFunc<std::function<B(A)>> r = {
		std::function<std::function<B(A)>(RecursiveFunc<std::function<B(A)>>)>([f](RecursiveFunc<std::function<B(A)>> w) {
			return f(std::function<B(A)>([w](A x) {
				return w.o(w)(x);
			}));
		})
	};
	return r.o(r);
}

typedef std::function<int(int)> Func;
typedef std::function<Func(Func)> FuncFunc;
FuncFunc almost_fac = [](Func f) {
	return Func([f](int n) {
		if (n <= 1) return 1;
		return n * f(n - 1);
	});
};

FuncFunc almost_fib = [](Func f) {
	return Func([f](int n) {
	 	if (n <= 2) return 1;
		return  f(n - 1) + f(n - 2);
	});
};

int main() {
	auto fib = Y(almost_fib);
	auto fac = Y(almost_fac);
	std::cout << "fib(10) = " << fib(10) << std::endl;
	std::cout << "fac(10) = " << fac(10) << std::endl;
	return 0;
}

{{out}}

fib(10) = 55
fac(10) = 3628800

{{works with|C++14}} A shorter version, taking advantage of generic lambdas. Known to work with GCC 5.2.0, but likely some earlier versions as well. Compile with g++ --std=c++14 ycomb.cc

#include <iostream>
#include <functional>
int main () {
  auto y = ([] (auto f) { return
              ([] (auto x) { return x (x); }
                 ([=] (auto y) -> std:: function <int (int)> { return
                    f ([=] (auto a) { return
                          (y (y)) (a) ;});}));});

  auto almost_fib = [] (auto f) { return
                       [=] (auto n) { return
                         n < 2? n: f (n - 1) + f (n - 2) ;};};
  auto almost_fac = [] (auto f) { return
                       [=] (auto n) { return
                         n <= 1? n: n * f (n - 1); };};

  auto fib = y (almost_fib);
  auto fac = y (almost_fac);
  std:: cout << fib (10) << '\n'
             << fac (10) << '\n';
}

{{out}}

fib(10) = 55
fac(10) = 3628800

The usual version using recursion, disallowed by the task:

template <typename A, typename B>
std::function<B(A)> Y (std::function<std::function<B(A)>(std::function<B(A)>)> f) {
	return [f](A x) {
		return f(Y(f))(x);
	};
}

Another version which is disallowed because a function passes itself, which is also a kind of recursion:

template <typename A, typename B>
struct YFunctor {
  const std::function<std::function<B(A)>(std::function<B(A)>)> f;
  YFunctor(std::function<std::function<B(A)>(std::function<B(A)>)> _f) : f(_f) {}
  B operator()(A x) const {
    return f(*this)(x);
  }
};

template <typename A, typename B>
std::function<B(A)> Y (std::function<std::function<B(A)>(std::function<B(A)>)> f) {
  return YFunctor<A,B>(f);
}

Ceylon

Using a class for the recursive type:

Result(*Args) y1<Result,Args>(
        Result(*Args)(Result(*Args)) f)
        given Args satisfies Anything[] {

    class RecursiveFunction(o) {
        shared Result(*Args)(RecursiveFunction) o;
    }

    value r = RecursiveFunction((RecursiveFunction w)
        =>  f(flatten((Args args) => w.o(w)(*args))));

    return r.o(r);
}

value factorialY1 = y1((Integer(Integer) fact)(Integer x)
    =>  if (x > 1) then x * fact(x - 1) else 1);

value fibY1 = y1((Integer(Integer) fib)(Integer x)
    =>  if (x > 2) then fib(x - 1) + fib(x - 2) else 2);

print(factorialY1(10)); // 3628800
print(fibY1(10));       // 110

Using Anything to erase the function type:

Result(*Args) y2<Result,Args>(
        Result(*Args)(Result(*Args)) f)
        given Args satisfies Anything[] {

    function r(Anything w) {
        assert (is Result(*Args)(Anything) w);
        return f(flatten((Args args) => w(w)(*args)));
    }

    return r(r);
}

Using recursion, this does not satisfy the task requirements, but is included here for illustrative purposes:

Result(*Args) y3<Result, Args>(
        Result(*Args)(Result(*Args)) f)
        given Args satisfies Anything[]
    =>  flatten((Args args) => f(y3(f))(*args));

Clojure

(defn Y [f]
  ((fn [x] (x x))
   (fn [x]
     (f (fn [& args]
          (apply (x x) args))))))

(def fac
     (fn [f]
       (fn [n]
         (if (zero? n) 1 (* n (f (dec n)))))))

(def fib
     (fn [f]
       (fn [n]
         (condp = n
           0 0
           1 1
           (+ (f (dec n))
              (f (dec (dec n))))))))

{{out}}

user> ((Y fac) 10)
3628800
user> ((Y fib) 10)
55

Y can be written slightly more concisely via syntax sugar:

(defn Y [f]
  (#(% %) #(f (fn [& args] (apply (% %) args)))))

Common Lisp

(defun Y (f)
  ((lambda (g) (funcall g g))
   (lambda (g)
     (funcall f (lambda (&rest a)
		  (apply (funcall g g) a))))))

(defun fac (n)
  (funcall
   (Y (lambda (f)
       (lambda (n)
         (if (zerop n)
	   1
	   (* n (funcall f (1- n)))))))
   n))

(defun fib (n)
  (funcall
   (Y (lambda (f)
       (lambda (n a b)
         (if (< n 1)
           a
           (funcall f (1- n) b (+ a b))))))
   n 0 1))

? (mapcar #'fac '(1 2 3 4 5 6 7 8 9 10))
(1 2 6 24 120 720 5040 40320 362880 3628800))

? (mapcar #'fib '(1 2 3 4 5 6 7 8 9 10))
(1 1 2 3 5 8 13 21 34 55)

CoffeeScript

Y = (f) -> g = f( (t...) -> g(t...) )

or

Y = (f) -> ((h)->h(h))((h)->f((t...)->h(h)(t...)))

fac = Y( (f) -> (n) -> if n > 1 then n * f(n-1) else 1 )
fib = Y( (f) -> (n) -> if n > 1 then f(n-1) + f(n-2) else n )

D

A stateless generic Y combinator:

import std.stdio, std.traits, std.algorithm, std.range;

auto Y(S, T...)(S delegate(T) delegate(S delegate(T)) f) {
    static struct F {
        S delegate(T) delegate(F) f;
        alias f this;
    }
    return (x => x(x))(F(x => f((T v) => x(x)(v))));
}

void main() { // Demo code:
    auto factorial = Y((int delegate(int) self) =>
        (int n) => 0 == n ? 1 : n * self(n - 1)
    );

    auto ackermann = Y((ulong delegate(ulong, ulong) self) =>
        (ulong m, ulong n) {
            if (m == 0) return n + 1;
            if (n == 0) return self(m - 1, 1);
            return self(m - 1, self(m, n - 1));
    });

    writeln("factorial: ", 10.iota.map!factorial);
    writeln("ackermann(3, 5): ", ackermann(3, 5));
}

{{out}}

factorial: [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880]
ackermann(3, 5): 253

=={{header|Déjà Vu}}== {{trans|Python}}

Y f:
	labda y:
		labda:
			call y @y
		f
	labda x:
		x @x
	call

labda f:
	labda n:
		if < 1 n:
			* n f -- n
		else:
			1
set :fac Y

labda f:
	labda n:
		if < 1 n:
			+ f - n 2 f -- n
		else:
			1
set :fib Y

!. fac 6
!. fib 6

{{out}}

720
13

Delphi

{{works with|Delphi XE and higher}} May work with Delphi 2009 and 2010 too. {{trans|C++}} (The translation is not literal; e.g. the function argument type is left unspecified to increase generality.)

program Y;

{$APPTYPE CONSOLE}

uses
  SysUtils;

type
  YCombinator = class sealed
    class function Fix<T> (F: TFunc<TFunc<T, T>, TFunc<T, T>>): TFunc<T, T>; static;
  end;

  TRecursiveFuncWrapper<T> = record // workaround required because of QC #101272 (http://qc.embarcadero.com/wc/qcmain.aspx?d=101272)
    type
      TRecursiveFunc = reference to function (R: TRecursiveFuncWrapper<T>): TFunc<T, T>;
    var
      O: TRecursiveFunc;
  end;

class function YCombinator.Fix<T> (F: TFunc<TFunc<T, T>, TFunc<T, T>>): TFunc<T, T>;
var
  R: TRecursiveFuncWrapper<T>;
begin
  R.O := function (W: TRecursiveFuncWrapper<T>): TFunc<T, T>
    begin
      Result := F (function (I: T): T
        begin
          Result := W.O (W) (I);
        end);
    end;
  Result := R.O (R);
end;


type
  IntFunc = TFunc<Integer, Integer>;

function AlmostFac (F: IntFunc): IntFunc;
begin
  Result := function (N: Integer): Integer
    begin
      if N <= 1 then
        Result := 1
      else
        Result := N * F (N - 1);
    end;
end;

function AlmostFib (F: TFunc<Integer, Integer>): TFunc<Integer, Integer>;
begin
  Result := function (N: Integer): Integer
    begin
      if N <= 2 then
        Result := 1
      else
        Result := F (N - 1) + F (N - 2);
    end;
end;

var
  Fib, Fac: IntFunc;
begin
  Fib := YCombinator.Fix<Integer> (AlmostFib);
  Fac := YCombinator.Fix<Integer> (AlmostFac);
  Writeln ('Fib(10) = ', Fib (10));
  Writeln ('Fac(10) = ', Fac (10));
end.

E

{{trans|Python}}

def y := fn f { fn x { x(x) }(fn y { f(fn a { y(y)(a) }) }) }
def fac := fn f { fn n { if (n<2) {1} else { n*f(n-1) } }}
def fib := fn f { fn n { if (n == 0) {0} else if (n == 1) {1} else { f(n-1) + f(n-2) } }}

? pragma.enable("accumulator")
? accum [] for i in 0..!10 { _.with(y(fac)(i)) }
[1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880]

? accum [] for i in 0..!10 { _.with(y(fib)(i)) }
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

EchoLisp

;; Ref : http://www.ece.uc.edu/~franco/C511/html/Scheme/ycomb.html

 (define Y
    (lambda (X)
      ((lambda (procedure)
         (X (lambda (arg) ((procedure procedure) arg))))
       (lambda (procedure)
         (X (lambda (arg) ((procedure procedure) arg)))))))

; Fib
(define Fib* (lambda (func-arg)
    (lambda (n) (if (< n 2) n (+ (func-arg (- n 1)) (func-arg (- n 2)))))))
(define fib (Y Fib*))
(fib 6)
    → 8

; Fact
(define F*
   (lambda (func-arg) (lambda (n) (if (zero? n) 1 (* n (func-arg (- n 1)))))))
(define fact (Y F*))

(fact 10)
    → 3628800

Eero

Translated from Objective-C example on this page.

typedef int (^Func)(int)
typedef Func (^FuncFunc)(Func)
typedef Func (^RecursiveFunc)(id) // hide recursive typing behind dynamic typing

Func fix(FuncFunc f)
  Func r(RecursiveFunc g)
    int s(int x)
      return g(g)(x)
    return f(s)
  return r(r)

int main(int argc, const char *argv[])
  autoreleasepool

    Func almost_fac(Func f)
      return (int n | return n <= 1 ? 1 : n * f(n - 1))

    Func almost_fib(Func f)
      return (int n | return n <= 2 ? 1 : f(n - 1) + f(n - 2))

    fib := fix(almost_fib)
    fac := fix(almost_fac)

    Log('fib(10) = %d', fib(10))
    Log('fac(10) = %d', fac(10))

  return 0

Ela

fix = \f -> (\x -> & f (x x)) (\x -> & f (x x))

fac _ 0 = 1
fac f n = n * f (n - 1)

fib _ 0 = 0
fib _ 1 = 1
fib f n = f (n - 1) + f (n - 2)

(fix fac 12, fix fib 12)

{{out}}

(479001600,144)

Elena

{{trans|Smalltalk}} ELENA 4.x :

import extensions;

singleton YCombinator
{
    fix(func)
        = (f){(x){ x(x) }((g){ f((x){ (g(g))(x) })})}(func);
}

public program()
{
    var fib := YCombinator.fix:(f => (i => (i <= 1) ? i : (f(i-1) + f(i-2)) ));
    var fact := YCombinator.fix:(f => (i => (i == 0) ? 1 : (f(i-1) * i) ));

    console.printLine("fib(10)=",fib(10));
    console.printLine("fact(10)=",fact(10));
}

{{out}}

fib(10)=55
fact(10)=3628800

Elixir

{{trans|Python}}

iex(1)> yc = fn f -> (fn x -> x.(x) end).(fn y -> f.(fn arg -> y.(y).(arg) end) end) end
#Function<6.90072148/1 in :erl_eval.expr/5>
iex(2)> fac = fn f -> fn n -> if n < 2 do 1 else n * f.(n-1) end end end
#Function<6.90072148/1 in :erl_eval.expr/5>
iex(3)> for i <- 0..9, do: yc.(fac).(i)
[1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880]
iex(4)> fib = fn f -> fn n -> if n == 0 do 0 else (if n == 1 do 1 else f.(n-1) + f.(n-2) end) end end end
#Function<6.90072148/1 in :erl_eval.expr/5>
iex(5)> for i <- 0..9, do: yc.(fib).(i)
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

Elm

This is similar to the Haskell solution below, but uses a strict fixed-point combinator since Elm lacks lazy evaluation.

import Html exposing (text)

type Mu a b = Roll (Mu a b -> a -> b)

unroll : Mu a b -> (Mu a b -> a -> b)
unroll (Roll x) = x

fix : ((a -> b) -> (a -> b)) -> (a -> b)
fix f = let g r = f (\v -> unroll r r v)
        in g (Roll g)

fac : Int -> Int
fac = fix <|
    \f n -> if n <= 0
            then 1
            else n * f (n - 1)

main = text <| toString <| fac 5

Erlang

Y = fun(M) -> (fun(X) -> X(X) end)(fun (F) -> M(fun(A) -> (F(F))(A) end) end) end.

Fac = fun (F) ->
          fun (0) -> 1;
              (N) -> N * F(N-1)
          end
      end.
Fib = fun(F) ->
          fun(0) -> 0;
             (1) -> 1;
             (N) -> F(N-1) + F(N-2)
          end
      end.
(Y(Fac))(5). %% 120
(Y(Fib))(8). %% 21

=={{header|F Sharp|F#}}==

type 'a mu = Roll of ('a mu -> 'a)  // ' fixes ease syntax colouring confusion with

let unroll (Roll x) = x
// val unroll : 'a mu -> ('a mu -> 'a)

// As with most of the strict (non-deferred or non-lazy) languages,
// this is the Z-combinator with the additional 'a' parameter...
let fix f = let g = fun x a -> f (unroll x x) a in g (Roll g)
// val fix : (('a -> 'b) -> 'a -> 'b) -> 'a -> 'b = <fun>

// Although true to the factorial definition, the
// recursive call is not in tail call position, so can't be optimized
// and will overflow the call stack for the recursive calls for large ranges...
//let fac = fix (fun f n -> if n < 2 then 1I else bigint n * f (n - 1))
// val fac : (int -> BigInteger) = <fun>

// much better progressive calculation in tail call position...
let fac = fix (fun f n i -> if i < 2 then n else f () (bigint i * n) (i - 1)) <| 1I
// val fac : (int -> BigInteger) = <fun>

// Although true to the definition of Fibonacci numbers,
// this can't be tail call optimized and recursively repeats calculations
// for a horrendously inefficient exponential performance fib function...
// let fib = fix (fun fnc n -> if n < 2 then n else fnc (n - 1) + fnc (n - 2))
// val fib : (int -> BigInteger) = <fun>

// much better progressive calculation in tail call position...
let fib = fix (fun fnc f s i -> if i < 2 then f else fnc s (f + s) (i - 1)) 1I 1I
// val fib : (int -> BigInteger) = <fun>

[<EntryPoint>]
let main argv =
  fac 10 |> printfn "%A" // prints 3628800
  fib 10 |> printfn "%A" // prints 55
  0 // return an integer exit code

{{output}}

3628800
55

Note that the first fac definition isn't really very good as the recursion is not in tail call position and thus will build stack, although for these functions one will likely never use it to stack overflow as the result would be exceedingly large; it is better defined as per the second definition as a steadily increasing function controlled by an int indexing argument and thus be in tail call position as is done for the fib function.

Also note that the above isn't the true fix point Y-combinator which would race without the beta conversion to the Z-combinator with the included a argument; the Z-combinator can't be used in all cases that require a true Y-combinator such as in the formation of deferred execution sequences in the last example, as follows:

// same as previous...
type 'a mu = Roll of ('a mu -> 'a)  // ' fixes ease syntax colouring confusion with

// same as previous...
let unroll (Roll x) = x
// val unroll : 'a mu -> ('a mu -> 'a)

// break race condition with some deferred execution - laziness...
let fix f = let g = fun x -> f <| fun() -> (unroll x x) in g (Roll g)
// val fix : ((unit -> 'a) -> 'a -> 'a) = <fun>

// same efficient version of factorial with added deferred execution...
let fac = fix (fun f n i -> if i < 2 then n else f () (bigint i * n) (i - 1)) <| 1I
// val fac : (int -> BigInteger) = <fun>

// same efficient version of factorial with added deferred execution...
let fib = fix (fun fnc f s i -> if i < 2 then f else fnc () s (f + s) (i - 1)) 1I 1I
// val fib : (int -> BigInteger) = <fun>

// given the following definition for an infinite Co-Inductive Stream (CIS)...
type CIS<'a> = CIS of 'a * (unit -> CIS<'a>) // ' fix formatting

// define a continuous stream of Fibonacci numbers; there are other simpler ways,
// this way does not use recursion at all by using the Y-combinator, although it is
// much slower than other ways due to the many additional function calls and memory allocations,
// it demonstrates something that can't be done with the Z-combinator...
let fibs() =
  let fbsgen : (CIS<bigint> -> CIS<bigint>) =
    fix (fun fnc f (CIS(s, rest)) ->
      CIS(f + s, fun() -> fnc () s <| rest())) 1I
  Seq.unfold
    (fun (CIS(hd, rest)) -> Some(hd, rest()))
    <| fix (fun cis -> fbsgen (CIS(0I, cis)))

[<EntryPoint>]
let main argv =
  fac 10 |> printfn "%A" // prints 3628800
  fib 10 |> printfn "%A" // prints 55
  fibs() |> Seq.take 20 |> Seq.iter (printf "%A ") // prints 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765
  printfn ""
  0 // return an integer exit code

{{output}}

3628800
55
1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765

The above would be useful if F# did not have recursive functions (functions that can call themselves in their own definition), but as for most modern languages, F# does have function recursion by the use of the rec keyword before the function name, thus the above fac and fib functions can be written much more simply (and to run faster using tail recursion) with a recursion definition for the fix Y-combinator as follows, with a simple injected deferred execution to prevent race:

let rec fix f = f <| fun() -> fix f
// val fix : f:((unit -> 'a) -> 'a) -> 'a

// the application of this true Y-combinator is the same as for the above non function recursive version.

Using the Y-combinator (or Z-combinator) as expressed here is pointless as in unnecessary and makes the code slower due to the extra function calls through the call stack, with the first non-function recursive implementation even slower than the second function recursion one; a non Y-combinator version can use function recursion with tail call optimization to simplify looping for about 100 times the speed in the actual loop overhead; thus, this is primarily an intellectual exercise.

Also note that these Y-combinators/Z-combinator are the non sharing kind; for certain types of algorithms that require that the input and output recursive values be the same (such as the same sequence or lazy list but made reference at difference stages), these will work but may be many times slower as in over 10 times slower than using binding recursion if the language allows it; F# allows binding recursion with a warning.

Factor

In rosettacode/Y.factor

USING: fry kernel math ;
IN: rosettacode.Y
: Y ( quot -- quot )
    '[ [ dup call call ] curry @ ] dup call ; inline

: almost-fac ( quot -- quot )
    '[ dup zero? [ drop 1 ] [ dup 1 - @ * ] if ] ;

: almost-fib ( quot -- quot )
    '[ dup 2 >= [ 1 2 [ - @ ] bi-curry@ bi + ] when ] ;

In rosettacode/Y-tests.factor

USING: kernel tools.test rosettacode.Y ;
IN: rosettacode.Y.tests

[ 120 ] [ 5 [ almost-fac ] Y call ] unit-test
[ 8 ]   [ 6 [ almost-fib ] Y call ] unit-test

running the tests :

 ( scratchpad - auto ) "rosettacode.Y" test
Loading resource:work/rosettacode/Y/Y-tests.factor
Unit Test: { [ 120 ] [ 5 [ almost-fac ] Y call ] }
Unit Test: { [ 8 ]   [ 6 [ almost-fib ] Y call ] }

Forth

\ Address of an xt.
variable 'xt
\ Make room for an xt.
: xt, ( -- ) here 'xt !  1 cells allot ;
\ Store xt.
: !xt ( xt -- ) 'xt @ ! ;
\ Compile fetching the xt.
: @xt, ( -- ) 'xt @ postpone literal postpone @ ;
\ Compile the Y combinator.
: y, ( xt1 -- xt2 ) >r :noname @xt, r> compile, postpone ; ;
\ Make a new instance of the Y combinator.
: y ( xt1 -- xt2 ) xt, y, dup !xt ;

Samples:

\ Factorial
10 :noname ( u1 xt -- u2 ) over ?dup if 1- swap execute * else 2drop 1 then ;
y execute . 3628800 ok

\ Fibonacci
10 :noname ( u1 xt -- u2 ) over 2 < if drop else >r 1- dup r@ execute swap 1- r> execute + then ;
y execute . 55 ok

Falcon

Y = { f => {x=> {n => f(x(x))(n)}} ({x=> {n => f(x(x))(n)}}) }
facStep = { f => {x => x < 1 ? 1 : x*f(x-1) }}
fibStep = { f => {x => x == 0 ? 0 : (x == 1 ? 1 : f(x-1) + f(x-2))}}

YFac = Y(facStep)
YFib = Y(fibStep)

> "Factorial 10: ", YFac(10)
> "Fibonacci 10: ", YFib(10)

GAP

Y := function(f)
    local u;
    u := x -> x(x);
    return u(y -> f(a -> y(y)(a)));
end;

fib := function(f)
    local u;
    u := function(n)
        if n < 2 then
            return n;
        else
            return f(n-1) + f(n-2);
        fi;
    end;
    return u;
end;

Y(fib)(10);
# 55

fac := function(f)
    local u;
    u := function(n)
        if n < 2 then
            return 1;
        else
            return n*f(n-1);
        fi;
    end;
    return u;
end;

Y(fac)(8);
# 40320

Genyris

{{trans|Scheme}}

def fac (f)
    function (n)
      if (equal? n 0) 1
        * n (f (- n 1))
def fib (f)
  function (n)
    cond
      (equal? n 0) 0
      (equal? n 1) 1
      else (+ (f (- n 1)) (f (- n 2)))

def Y (f)
  (function (x) (x x))
      function (y)
          f
             function (&rest args) (apply (y y) args)

assertEqual ((Y fac) 5) 120
assertEqual ((Y fib) 8) 21

Go

package main

import "fmt"

type Func func(int) int
type FuncFunc func(Func) Func
type RecursiveFunc func (RecursiveFunc) Func

func main() {
	fac := Y(almost_fac)
	fib := Y(almost_fib)
	fmt.Println("fac(10) = ", fac(10))
	fmt.Println("fib(10) = ", fib(10))
}

func Y(f FuncFunc) Func {
	g := func(r RecursiveFunc) Func {
		return f(func(x int) int {
			return r(r)(x)
		})
	}
	return g(g)
}

func almost_fac(f Func) Func {
	return func(x int) int {
		if x <= 1 {
			return 1
		}
		return x * f(x-1)
	}
}

func almost_fib(f Func) Func {
	return func(x int) int {
		if x <= 2 {
			return 1
		}
		return f(x-1)+f(x-2)
	}
}

{{out}}

fac(10) =  3628800
fib(10) =  55

The usual version using recursion, disallowed by the task:

func Y(f FuncFunc) Func {
	return func(x int) int {
		return f(Y(f))(x)
	}
}

Groovy

Here is the simplest (unary) form of applicative order Y:

def Y = { le -> ({ f -> f(f) })({ f -> le { x -> f(f)(x) } }) }

def factorial = Y { fac ->
    { n -> n <= 2 ? n : n * fac(n - 1) }
}

assert 2432902008176640000 == factorial(20G)

def fib = Y { fibStar ->
    { n -> n <= 1 ? n : fibStar(n - 1) + fibStar(n - 2) }
}

assert fib(10) == 55

This version was translated from the one in ''The Little Schemer'' by Friedman and Felleisen. The use of the variable name ''le'' is due to the fact that the authors derive Y from an ordinary recursive '''''le'''ngth'' function.

A variadic version of Y in Groovy looks like this:

def Y = { le -> ({ f -> f(f) })({ f -> le { Object[] args -> f(f)(*args) } }) }

def mul = Y { mulStar -> { a, b -> a ? b + mulStar(a - 1, b) : 0 } }

1.upto(10) {
    assert mul(it, 10) == it * 10
}

Haskell

The obvious definition of the Y combinator (\f-> (\x -> f (x x)) (\x-> f (x x))) cannot be used in Haskell because it contains an infinite recursive type (a = a -> b). Defining a data type (Mu) allows this recursion to be broken.

newtype Mu a = Roll
  { unroll :: Mu a -> a }

fix :: (a -> a) -> a
fix = g <*> (Roll . g)
  where
    g = (. (>>= id) unroll)

- this version is not in tail call position...
-- fac :: Integer -> Integer
-- fac =
--   fix $ \f n -> if n <= 0 then 1 else n * f (n - 1)

-- this version builds a progression from tail call position and is more efficient...
fac :: Integer -> Integer
fac =
  (fix $ \f n i -> if i <= 0 then n else f (i * n) (i - 1)) 1

-- make fibs a function, else memory leak as
-- head of the list can never be released as per:
--   https://wiki.haskell.org/Memory_leak, type 1.1
-- overly complex version...
{--
fibs :: () -> [Integer]
fibs() =
  fix $
    (0 :) . (1 :) .
      (fix
        (\f (x:xs) (y:ys) ->
          case x + y of n -> n `seq` n : f xs ys) <*> tail)
--}

-- easier to read, simpler (faster) version...
fibs :: () -> [Integer]
fibs() = 0 : 1 : fix fibs_ 0 1
  where
    fibs_ fnc f s =
      case f + s of n -> n `seq` n : fnc s n

main :: IO ()
main =
  mapM_
    print
    [ map fac [1 .. 20]
    , take 20 $ fibs()
    ]

The usual version uses recursion on a binding, disallowed by the task, to define the fix itself; but the definitions produced by this fix does ''not'' use recursion on value bindings although it does use recursion when defining a function (not possible in all languages), so it can be viewed as a true Y-combinator too:

-- note that this version of fix uses function recursion in its own definition;
-- thus its use just means that the recursion has been "pulled" into the "fix" function,
-- instead of the function that uses it...
fix :: (a -> a) -> a
fix f = f (fix f) -- _not_ the {fix f = x where x = f x}

fac :: Integer -> Integer
fac =
  (fix $
    \f n i ->
      if i <= 0 then n
      else f (i * n) (i - 1)) 1

fib :: Integer -> Integer
fib =
  (fix $
    \fnc f s i ->
      if i <= 1 then f
      else case f + s of n -> n `seq` fnc s n (i - 1)) 0 1

{--
-- compute a lazy infinite list. This is
-- a Y-combinator version of: fibs() = 0:1:zipWith (+) fibs (tail fibs)
-- which is the same as the above version but easier to read...
fibs :: () -> [Integer]
fibs() = fix fibs_
  where
    zipP f (x:xs) (y:ys) =
      case x + y of n -> n `seq` n : f xs ys
    fibs_ a = 0 : 1 : fix zipP a (tail a)
--}

-- easier to read, simpler (faster) version...
fibs :: () -> [Integer]
fibs() = 0 : 1 : fix fibs_ 0 1
  where
    fibs_ fnc f s =
      case f + s of n -> n `seq` n : fnc s n

-- This code shows how the functions can be used:
main :: IO ()
main =
  mapM_
    print
    [ map fac [1 .. 20]
    , map fib [1 .. 20]
    , take 20 fibs()
    ]

Now just because something is possible using the Y-combinator doesn't mean that it is practical: the above implementations can't compute much past the 1000th number in the Fibonacci list sequence and is quite slow at doing so; using direct function recursive routines compute about 100 times faster and don't hang for large ranges, nor give problems compiling as the first version does (GHC version 8.4.3 at -O1 optimization level).

If one has recursive functions as Haskell does and as used by the second fix, there is no need to use fix/the Y-combinator at all since one may as well just write the recursion directly. The Y-combinator may be interesting mathematically, but it isn't very practical when one has any other choice.

J

===Non-tacit version=== Unfortunately, in principle, J functions cannot take functions of the same type as arguments. In other words, verbs (functions) cannot take verbs, and adverbs or conjunctions (higher-order functions) cannot take adverbs or conjunctions. This implementation uses the body, a literal (string), of an explicit adverb (a higher-order function with a left argument) as the argument for Y, to represent the adverb for which the product of Y is a fixed-point verb; Y itself is also an adverb.

Y=. '('':''<@;(1;~":0)<@;<@((":0)&;))'(2 : 0 '')
  (1 : (m,'u'))(1 : (m,'''u u`:6('',(5!:5<''u''),'')`:6 y'''))(1 :'u u`:6')
)

This Y combinator follows the standard method: it produces a fixed-point which reproduces and transforms itself anonymously according to the adverb represented by Y's argument. All names (variables) refer to arguments of the enclosing adverbs and there are no assignments.

The factorial and Fibonacci examples follow:

   'if. * y do. y * u <: y else. 1 end.' Y 10 NB. Factorial
3628800
          '(u@:<:@:<: + u@:<:)^:(1 < ])' Y 10 NB. Fibonacci
55

The names u, x, and y are J's standard names for arguments; the name y represents the argument of u and the name u represents the verb argument of the adverb for which Y produces a fixed-point. Any verb can also be expressed tacitly, without any reference to its argument(s), as in the Fibonacci example.

A structured derivation of a Y with states follows (the stateless version can be produced by replacing all the names by its referents):

   arb=. ':'<@;(1;~":0)<@;<@((":0)&;)                     NB. AR of an explicit adverb from its body

   ara=. 1 :'arb u'                                       NB. The verb arb as an adverb
   srt=. 1 :'arb ''u u`:6('' , (5!:5<''u'') , '')`:6 y''' NB. AR of the self-replication and transformation adverb
   gab=. 1 :'u u`:6'                                      NB. The AR of the adverb and the adverb itself as a train

   Y=. ara srt gab                                        NB. Train of adverbs

The adverb Y, apart from using a representation as Y's argument, satisfies the task's requirements. However, it only works for monadic verbs (functions with a right argument). J's verbs can also be dyadic (functions with a left and right arguments) and ambivalent (almost all J's primitive verbs are ambivalent; for example - can be used as in - 1 and 2 - 1). The following adverb (XY) implements anonymous recursion of monadic, dyadic, and ambivalent verbs (the name x represents the left argument of u),

XY=. (1 :'('':''<@;(1;~":0)<@;<@((":0)&;))u')(1 :'('':''<@;(1;~":0)<@;<@((":0)&;))((''u u`:6('',(5!:5<''u''),'')`:6 y''),(10{a.),'':'',(10{a.),''x(u u`:6('',(5!:5<''u''),'')`:6)y'')')(1 :'u u`:6')

The following are examples of anonymous dyadic and ambivalent recursions,

   1 2 3 '([:`(>:@:])`(<:@:[ u 1:)`(<:@[ u [ u <:@:])@.(#.@,&*))'XY"0/  1 2 3 4 5 NB. Ackermann function...
 3  4  5   6   7
 5  7  9  11  13
13 29 61 125 253
                               '1:`(<: u <:)@.* : (+ + 2 * u@:])'XY"0/~ i.7       NB. Ambivalent recursion...
2  5 14 35 80 173 362
3  6 15 36 81 174 363
4  7 16 37 82 175 364
5  8 17 38 83 176 365
6  9 18 39 84 177 366
7 10 19 40 85 178 367
8 11 20 41 86 179 368
   NB. OEIS A097813 - main diagonal
   NB. OEIS A050488 = A097813 - 1 - adyacent upper off-diagonal

J supports directly anonymous tacit recursion via the verb $: and for tacit recursions, XY is equivalent to the adverb,

YX=. (1 :'('':''<@;(1;~":0)<@;<@((":0)&;))u')($:`)(`:6)

Tacit version

The Y combinator can be implemented indirectly using, for example, the linear representations of verbs (Y becomes a wrapper which takes an ad hoc verb as an argument and serializes it; the underlying self-referring system interprets the serialized representation of a verb as the corresponding verb):

Y=. ((((&>)/)((((^:_1)b.)(`(<'0';_1)))(`:6)))(&([ 128!:2 ,&<)))

The factorial and Fibonacci examples:

   u=. [ NB. Function (left)
   n=. ] NB. Argument (right)
   sr=. [ apply f. ,&< NB. Self referring

   fac=. (1:`(n * u sr n - 1:)) @. (0 < n)
   fac f. Y 10
3628800

   Fib=. ((u sr n - 2:) + u sr n - 1:) ^: (1 < n)
   Fib f. Y 10
55

The stateless functions are shown next (the f. adverb replaces all embedded names by its referents):

   fac f. Y NB. Factorial...
'1:`(] * [ ([ 128!:2 ,&<) ] - 1:)@.(0 < ])&>/'&([ 128!:2 ,&<)

   fac f.   NB. Factorial step...
1:`(] * [ ([ 128!:2 ,&<) ] - 1:)@.(0 < ])


   Fib f. Y NB. Fibonacci...
'(([ ([ 128!:2 ,&<) ] - 2:) + [ ([ 128!:2 ,&<) ] - 1:)^:(1 < ])&>/'&([ 128!:2 ,&<)

   Fib f.   NB. Fibonacci step...
(([ ([ 128!:2 ,&<) ] - 2:) + [ ([ 128!:2 ,&<) ] - 1:)^:(1 < ])

A structured derivation of Y follows:

   sr=. [ apply f.,&<                 NB. Self referring
   lv=. (((^:_1)b.)(`(<'0';_1)))(`:6) NB. Linear representation of a verb argument
   Y=. (&>)/lv(&sr)                   NB. Y with embedded states
   Y=. 'Y'f.                          NB. Fixing it...
   Y                                  NB. ... To make it stateless (i.e., a combinator)
((((&>)/)((((^:_1)b.)(`_1))(`:6)))(&([ 128!:2 ,&<)))

Explicit alternate implementation

Another approach:

Y=:1 :0
  f=. u Defer
  (5!:1<'f') f y
)

Defer=: 1 :0
:
  g=. x&(x`:6)
  (5!:1<'g') u y
)

almost_factorial=: 4 :0
  if. 0 >: y do. 1
  else. y * x`:6 y-1 end.
)

almost_fibonacci=: 4 :0
  if. 2 > y do. y
  else. (x`:6 y-1) + x`:6 y-2 end.
)

Example use:

   almost_factorial Y 9
362880
   almost_fibonacci Y 9
34
   almost_fibonacci Y"0 i. 10
0 1 1 2 3 5 8 13 21 34

Or, if you would prefer to not have a dependency on the definition of Defer, an equivalent expression would be:

Y=:2 :0(0 :0)
NB. this block will be n in the second part
:
  g=. x&(x`:6)
  (5!:1<'g') u y
)
  f=. u (1 :n)
  (5!:1<'f') f y
)

That said, if you think of association with a name as state (because in different contexts the association may not exist, or may be different) you might also want to remove that association in the context of the Y combinator.

For example:

   almost_factorial f. Y 10
3628800

Java

{{works with|Java|8+}}

import java.util.function.Function;

public interface YCombinator {
  interface RecursiveFunction<F> extends Function<RecursiveFunction<F>, F> { }
  public static <A,B> Function<A,B> Y(Function<Function<A,B>, Function<A,B>> f) {
    RecursiveFunction<Function<A,B>> r = w -> f.apply(x -> w.apply(w).apply(x));
    return r.apply(r);
  }

  public static void main(String... arguments) {
    Function<Integer,Integer> fib = Y(f -> n ->
      (n <= 2)
        ? 1
        : (f.apply(n - 1) + f.apply(n - 2))
    );
    Function<Integer,Integer> fac = Y(f -> n ->
      (n <= 1)
        ? 1
        : (n * f.apply(n - 1))
    );

    System.out.println("fib(10) = " + fib.apply(10));
    System.out.println("fac(10) = " + fac.apply(10));
  }
}

{{out}}

fib(10) = 55
fac(10) = 3628800

The usual version using recursion, disallowed by the task:

    public static <A,B> Function<A,B> Y(Function<Function<A,B>, Function<A,B>> f) {
        return x -> f.apply(Y(f)).apply(x);
    }

Another version which is disallowed because a function passes itself, which is also a kind of recursion:

    public static <A,B> Function<A,B> Y(Function<Function<A,B>, Function<A,B>> f) {
        return new Function<A,B>() {
	    public B apply(A x) {
		return f.apply(this).apply(x);
	    }
	};
    }

{{works with|Java|pre-8}} We define a generic function interface like Java 8's Function.

interface Function<A, B> {
    public B call(A x);
}

public class YCombinator {
    interface RecursiveFunc<F> extends Function<RecursiveFunc<F>, F> { }

    public static <A,B> Function<A,B> fix(final Function<Function<A,B>, Function<A,B>> f) {
        RecursiveFunc<Function<A,B>> r =
            new RecursiveFunc<Function<A,B>>() {
            public Function<A,B> call(final RecursiveFunc<Function<A,B>> w) {
                return f.call(new Function<A,B>() {
                        public B call(A x) {
                            return w.call(w).call(x);
                        }
                    });
            }
        };
        return r.call(r);
    }

    public static void main(String[] args) {
        Function<Function<Integer,Integer>, Function<Integer,Integer>> almost_fib =
            new Function<Function<Integer,Integer>, Function<Integer,Integer>>() {
            public Function<Integer,Integer> call(final Function<Integer,Integer> f) {
                return new Function<Integer,Integer>() {
                    public Integer call(Integer n) {
                        if (n <= 2) return 1;
                        return f.call(n - 1) + f.call(n - 2);
                    }
                };
            }
        };

        Function<Function<Integer,Integer>, Function<Integer,Integer>> almost_fac =
            new Function<Function<Integer,Integer>, Function<Integer,Integer>>() {
            public Function<Integer,Integer> call(final Function<Integer,Integer> f) {
                return new Function<Integer,Integer>() {
                    public Integer call(Integer n) {
                        if (n <= 1) return 1;
                        return n * f.call(n - 1);
                    }
                };
            }
        };

        Function<Integer,Integer> fib = fix(almost_fib);
        Function<Integer,Integer> fac = fix(almost_fac);

        System.out.println("fib(10) = " + fib.call(10));
        System.out.println("fac(10) = " + fac.call(10));
    }
}

The following code modifies the Function interface such that multiple parameters (via varargs) are supported, simplifies the y function considerably, and the [[Ackermann function#Java|Ackermann function]] has been included in this implementation (mostly because both [[Y combinator#D|D]] and [[Y combinator#PicoLisp|PicoLisp]] include it in their own implementations).

import java.util.function.Function;

@FunctionalInterface
public interface SelfApplicable<OUTPUT> extends Function<SelfApplicable<OUTPUT>, OUTPUT> {
  public default OUTPUT selfApply() {
    return apply(this);
  }
}

import java.util.function.Function;
import java.util.function.UnaryOperator;

@FunctionalInterface
public interface FixedPoint<FUNCTION> extends Function<UnaryOperator<FUNCTION>, FUNCTION> {}

import java.util.Arrays;
import java.util.Optional;
import java.util.function.Function;
import java.util.function.BiFunction;

@FunctionalInterface
public interface VarargsFunction<INPUTS, OUTPUT> extends Function<INPUTS[], OUTPUT> {
  @SuppressWarnings("unchecked")
  public OUTPUT apply(INPUTS... inputs);

  public static <INPUTS, OUTPUT> VarargsFunction<INPUTS, OUTPUT> from(Function<INPUTS[], OUTPUT> function) {
    return function::apply;
  }

  public static <INPUTS, OUTPUT> VarargsFunction<INPUTS, OUTPUT> upgrade(Function<INPUTS, OUTPUT> function) {
    return inputs -> function.apply(inputs[0]);
  }

  public static <INPUTS, OUTPUT> VarargsFunction<INPUTS, OUTPUT> upgrade(BiFunction<INPUTS, INPUTS, OUTPUT> function) {
    return inputs -> function.apply(inputs[0], inputs[1]);
  }

  @SuppressWarnings("unchecked")
  public default <POST_OUTPUT> VarargsFunction<INPUTS, POST_OUTPUT> andThen(
      VarargsFunction<OUTPUT, POST_OUTPUT> after) {
    return inputs -> after.apply(apply(inputs));
  }

  @SuppressWarnings("unchecked")
  public default Function<INPUTS, OUTPUT> toFunction() {
    return input -> apply(input);
  }

  @SuppressWarnings("unchecked")
  public default BiFunction<INPUTS, INPUTS, OUTPUT> toBiFunction() {
    return (input, input2) -> apply(input, input2);
  }

  @SuppressWarnings("unchecked")
  public default <PRE_INPUTS> VarargsFunction<PRE_INPUTS, OUTPUT> transformArguments(Function<PRE_INPUTS, INPUTS> transformer) {
    return inputs -> apply((INPUTS[]) Arrays.stream(inputs).parallel().map(transformer).toArray());
  }
}

import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.function.Function;
import java.util.function.UnaryOperator;
import java.util.stream.Collectors;
import java.util.stream.LongStream;

@FunctionalInterface
public interface Y<FUNCTION> extends SelfApplicable<FixedPoint<FUNCTION>> {
  public static void main(String... arguments) {
    BigInteger TWO = BigInteger.ONE.add(BigInteger.ONE);

    Function<Number, Long> toLong = Number::longValue;
    Function<Number, BigInteger> toBigInteger = toLong.andThen(BigInteger::valueOf);

    /* Based on https://gist.github.com/aruld/3965968/#comment-604392 */
    Y<VarargsFunction<Number, Number>> combinator = y -> f -> x -> f.apply(y.selfApply().apply(f)).apply(x);
    FixedPoint<VarargsFunction<Number, Number>> fixedPoint = combinator.selfApply();

    VarargsFunction<Number, Number> fibonacci = fixedPoint.apply(
      f -> VarargsFunction.upgrade(
        toBigInteger.andThen(
          n -> (n.compareTo(TWO) <= 0)
            ? 1
            : new BigInteger(f.apply(n.subtract(BigInteger.ONE)).toString())
              .add(new BigInteger(f.apply(n.subtract(TWO)).toString()))
        )
      )
    );

    VarargsFunction<Number, Number> factorial = fixedPoint.apply(
      f -> VarargsFunction.upgrade(
        toBigInteger.andThen(
          n -> (n.compareTo(BigInteger.ONE) <= 0)
            ? 1
            : n.multiply(new BigInteger(f.apply(n.subtract(BigInteger.ONE)).toString()))
        )
      )
    );

    VarargsFunction<Number, Number> ackermann = fixedPoint.apply(
      f -> VarargsFunction.upgrade(
        (BigInteger m, BigInteger n) -> m.equals(BigInteger.ZERO)
          ? n.add(BigInteger.ONE)
          : f.apply(
              m.subtract(BigInteger.ONE),
              n.equals(BigInteger.ZERO)
                ? BigInteger.ONE
                  : f.apply(m, n.subtract(BigInteger.ONE))
            )
      ).transformArguments(toBigInteger)
    );

    Map<String, VarargsFunction<Number, Number>> functions = new HashMap<>();
    functions.put("fibonacci", fibonacci);
    functions.put("factorial", factorial);
    functions.put("ackermann", ackermann);

    Map<VarargsFunction<Number, Number>, Number[]> parameters = new HashMap<>();
    parameters.put(functions.get("fibonacci"), new Number[]{20});
    parameters.put(functions.get("factorial"), new Number[]{10});
    parameters.put(functions.get("ackermann"), new Number[]{3, 2});

    functions.entrySet().stream().parallel().map(
      entry -> entry.getKey()
        + Arrays.toString(parameters.get(entry.getValue()))
        + " = "
        + entry.getValue().apply(parameters.get(entry.getValue()))
    ).forEach(System.out::println);
  }
}

{{out}} (may depend on which function gets processed first): factorial[10] = 3628800 ackermann[3, 2] = 29 fibonacci[20] = 6765

## JavaScript

The standard version of the Y combinator does not use lexically bound local variables (or any local variables at all), which necessitates adding a wrapper function and some code duplication - the remaining locale variables are only there to make the relationship to the previous implementation more explicit:

```javascript
function Y(f) {
    var g = f((function(h) {
        return function() {
            var g = f(h(h));
            return g.apply(this, arguments);
        }
    })(function(h) {
        return function() {
            var g = f(h(h));
            return g.apply(this, arguments);
        }
    }));
    return g;
}

var fac = Y(function(f) {
    return function (n) {
        return n > 1 ? n * f(n - 1) : 1;
    };
});

var fib = Y(function(f) {
    return function(n) {
        return n > 1 ? f(n - 1) + f(n - 2) : n;
    };
});