Recursion without Referencing and Assignment

You can use something like lambda calculus to avoid assignment and self reference, replacing both with access to an argument of an anonymous function. For example:

fact = (lambda f: f(f))(lambda f: (lambda n: n*f(f)(n-1) if n else 1))

Tested in Ideone.

---

Some details below for further background.

I know lambda calculus is famous for being a powerful (Turing complete) yet minimalistic “programming language”. It only uses identifiers for variables, which can be either bound (pretty much function arguments) or unbound (mostly relevant when talking about parts of an expression). So it felt like a good starting point.

The canonical way to express recursion in lambda calculus is using a fixed point combinator. While that combinator can be expressed naively in Python syntax, eager evaluation leads to infinte recursion.

The code at https://rosettacode.org/wiki/Y_combinator#Python mentioned in comments avoids this infinite recursion by delaying one of the recursive calls till the function actually gets called. But I would prefer leaving detailed explanation of that approach to a separate answer.

What is the core idea of expressing recursion in lambda calculus? Passing a function as an argument to itself. So I started with this:

lambda f: f(f)  # λ f.f f

I need to pass that function another function that takes a function as a value. Like lambda f: …. And the result of that call should be a function that should take an n as an argument to compute the factorial. My first approximation was thinking of f itself as an expression for the recursive call, so I had this first:

(lambda f: f(f))(lambda f: (lambda n: n*f(n-1) if n else 1))

But then I realized this was wrong: f itself is not the recursive call, since f is the function that takes an argument f. So f(f) is the recursive call, leading to the solution I printed in the beginning.