Can a computer program call itself to solve problems?
Image: Photograph by Andrew Steele (https://andrewsteele.co.uk), jointly released into the public domain by the person in the p, CC0, via Wikimedia Commons
the Y combinator does: enables recursion in languages without named functions
Can a computer program call itself to solve problems?
Imagine you're giving a friend a recipe to bake cookies, but you forgot to include the recipe itself. You'd be stuck with no instructions on how to make the recipe!
The Y combinator is like a secret recipe that lets a computer program bake its own recipe by calling itself, even though it can't have its own name in the recipe.
Example
A computer program uses the Y combinator to calculate its own factorial, like 5! = 5 × 4 × 3 × 2 × 1, without needing its own name.
Remember this
The Y combinator enables recursion in programming languages that don't support named functions.
Text adapted from Wikipedia, licensed under CC BY-SA 4.0.
Related concepts
Overlapping subproblems
Ever calculated a huge Fibonacci sequence by hand?
Halting problem
Alan Turing proved the halting problem is undecidable
Monad (functional programming)
Monads are a type constructor with two operations: return and bind
Kolmogorov complexity
Kolmogorov complexity is uncomputable
subword tokenization solves: handles rare words by breaking into known pieces
Subword tokenization solves rare word handling by breaking into known pieces
Shor's algorithm
Shor's algorithm factors integers in polynomial time on a quantum computer
Swipe through 100 ML concepts daily
Open Pocket Polymath