Joran Honig

Decoding the Y Combinator: A Deep Dive into Recursion

3 min read

The Y Combinator, an intriguing concept in functional programming, is a powerful tool that facilitates recursion even in programming languages that don’t natively support it.

What is a Y Combinator?

The Y Combinator can be represented as follows:

Y = λf.(λx.f (x x)) (λx.f (x x))

In this expression, (x x) means that we apply x to itself.

Sounds a bit abstract? Let’s break it down!

Inside the Lambda Function

The lambda function consists of three main components:

  1. f(r') -> r: This is a recursive function generator, where f is a function that builds a recursive function by taking a reference to a semantically equivalent recursive function, and r is the recursive function that’s returned.
  2. λx.f (x x): This is a function which uses a recursive function generator f, and itself x!
  3. (x x) applies x to itself, creating a new recursive function generator that will receive a clone of x.

Essentially, we’re creating new copies of our recursive function as we go further into the recursion.

The Y Combinator in Action: A Python Example

To better illustrate how this works, let’s explore a simple Python version:

# Example with function names
 
def y_combinator(f):
    # the y combinator is a generator of new f references
 
    def apply_x(x):
        # x is the self duplicating function
        # y is the argument we wanna pass to the recursive function
        # f is the recursive function generator
        return f(lambda y: x(x)(y))
 
    def another_apply_x(x):
    # same 
        return f(lambda y: x(x)(y))
 
    # the trick can be found here! 
    # We get to avoid using a recursive reference through simply duplicating code.
    return apply_x(another_apply_x)
 
# What does this look like? 
# y=y_combinator and x = apply_x and x' is apply_other_x
# y(f)(n) = x(x')(n) = f(x(x'))(n)
# notice how evaluating x(x'), produces f(x(x')), a copy for the next iteration

Let’s imagine Python doesn’t natively support recursion. We could still implement a recursive factorial function using our Y Combinator:

# Example usage assuming python doesn't have recursion yet
def factorial_func(f):
    # even though we don't have recursion let's act like f is a recursive factorial function.
    # even though the implementation below isn't recursive, it'd still work.
    def factorial(n):
        return 1 if n == 0 else n * f(n - 1)
    return factorial
 
# factoral func is really just a factorial function builder.
# calling the function will look like this: factoral_func(*factorial)(number)
factorial = y_combinator(factorial_func)
 
print(factorial(5))  # Output: 120
 
# What does this look like?
# factorial = y(fac_gen) = factorial_func(x(x'))
# factorial(5) = 5 * f(n-1)
# remeber: f=x(x') = factorial_func(x(x'))
# factorial(5) = 5 * factorial_func(x(x'))(4) = 5 * y(fac_gen)(4)
# recursion!

This example shows how the Y Combinator creates new instances of the factorial function as required, facilitating recursion even when the language doesn’t inherently support it.

Wrapping Up

The Y Combinator is an cool solution to a complex problem, and it demonstrates the power of functional programming as a paradigm.

Graph View