For fun, let's say you are programming in a language that doesn't allow variable assignments and you still want to make a recursive function. Although you can't assign variables, you can use functions (and enclosed function arguments). Can you make a function recursive without calling it by name?
Lets try implementing the factorial function. First with a function calling itself by name, then with a funtion that never calls itself by name
Here is the implementation of factorial that calls itself by name. It's a simple recursive function
factorial = (x) ->
if x is 1 then return 1
x * factorial(x - 1)
Simple enough. factorial(6) gives us 720.
But if I restricted myself to not calling factorial within factorial, I would have to make a function like this
factorialGenerator = (factorial) ->
(x) ->
if x is 1 then return 1
x * factorial(x - 1)
factorialGenerator returns the factorial function, whose implementation does not call itself, but instead the first argument to factorialGenerator which should be that same implementation of factorial.
Can this even be done?
Yes. With something called a Y Combinator.
The simplest implementation I found is
y = (fnGenerator) ->
fakeFn = (arg) -> realFn(arg)
realFn = fnGenerator(fakeFn)
realFn
To get the factorialGenerator to work, we have to call it with the first argument being the same thing that factorialGenerator returned!
So we create a fake function (fakeFn) that pretends it's like factorial, taking in an arg and calling realFn. And because realFn is what is returned from fnGenerator we are good!
we call y(factorialGenerator)(6) and we get 720
But we are still relying on variable assigmnents inside our Y combinator. Let's step-by-step get rid of those.
First step, inline fakeFn so it's not a variable
y = (fnGenerator) ->
realFn = fnGenerator (arg) -> realFn(arg)
realFn
Next step, (maybe the hardest), let's make realFn not call itself. Let's make a realFn generator that returns what realFn did. Let's make it take as an argument itself, so calling realFnGenerator(realFnGenerator) will return what realFn did in the last example.
y = (fnGenerator) ->
realFnGenerator = (realFnGenerator) ->
realFn = realFnGenerator realFnGenerator
fnGenerator (arg) -> realFn(arg)
realFnGenerator(realFnGenerator)
So you are doing what you did before, but instead of defining a realFn variable, you are defining a realFnGenerator that takes in itself realFnGenerator. whenever you call realFnGenerator(realFnGenerator) you get what realFn would be.
Next step, let's inline the remaining realFn
y = (fnGenerator) ->
realFnGenerator = (realFnGenerator) ->
fnGenerator (arg) -> realFnGenerator(realFnGenerator)(arg)
realFnGenerator(realFnGenerator)
Now let's copy paste realFnGenerator so we don't have to define it twice
y = (fnGenerator) ->
realFnGenerator = (realFnGenerator) ->
fnGenerator (arg) -> realFnGenerator(realFnGenerator)(arg)
realFnGenerator2 = (realFnGenerator) ->
fnGenerator (arg) -> realFnGenerator(realFnGenerator)(arg)
realFnGenerator(realFnGenerator2)
Now instead of returning realFnGenerator(realFnGenerator2) let's inline them.
y = (fnGenerator) ->
(
(realFnGenerator) ->
fnGenerator (arg) -> realFnGenerator(realFnGenerator)(arg)
)(
(realFnGenerator) ->
fnGenerator (arg) -> realFnGenerator(realFnGenerator)(arg)
)
And if we make the variable names smaller for fun
y = (f) -> ((g) -> f (x) -> g(g)(x))((g) -> f (x) -> g(g)(x))
now y(factorialGenerator)(6) will be 720
http://rosettacode.org/wiki/Y_combinator#JavaScript
What if we implemented factorialGenerator like this?
factorialGenerator = (factorialGenerator) ->
(x) ->
if x is 1 then return 1
x * factorialGenerator(factorialGenerator)(x - 1)
factorial = factorialGenerator(factorialGenerator)
factorial(6) # == 720
Instead of taking factorial as the first argument of factorialGenerator, what if the same factorialGenerator was the first argument of itself.
lets abstract a little
factorialGenerator = (fnGenerator) ->
(x) ->
factorial = fnGenerator(fnGenerator)
if x is 1 then return 1
x * factorial(x - 1)
factorial = factorialGenerator(factorialGenerator)
factorial(6) # == 720
and more
factorialGenerator = (fnGenerator) ->
(x) ->
factorial = fnGenerator(fnGenerator)
fac = (x) ->
if x is 1 then return 1
x * factorial(x - 1)
fac(x)
factorial = factorialGenerator(factorialGenerator)
factorial(6) # == 720
yet more
factorialGenerator = (fnGenerator) ->
(x) ->
factorial = fnGenerator(fnGenerator)
facGenerator = (fac1) ->
fac2 = (x) ->
if x is 1 then return 1
x * fac1(x - 1)
facGenerator(factorial)(x)
factorial = factorialGenerator(factorialGenerator)
factorial(6) # == 720
and even more
factorialGenerator = (fnGenerator, facGenerator) ->
(x) ->
factorial = fnGenerator(fnGenerator, facGenerator)
facGenerator(factorial)(x)
facGenerator = (fac1) ->
(x) ->
if x is 1 then return 1
x * fac1(x - 1)
factorial = factorialGenerator(factorialGenerator, facGenerator)
factorial(6) # == 720
and more
y = (facGenerator) ->
factorial = factorialGenerator(factorialGenerator, facGenerator)
factorialGenerator = (fnGenerator, facGenerator) ->
(x) ->
factorial = fnGenerator(fnGenerator, facGenerator)
facGenerator(factorial)(x)
facGenerator = (fac1) ->
(x) ->
if x is 1 then return 1
x * fac1(x - 1)
factorial = y(facGenerator)
factorial(6) # == 720
even more
y = (facGenerator) ->
factorialGenerator = (fnGenerator, facGenerator) ->
(x) ->
factorial = fnGenerator(fnGenerator, facGenerator)
facGenerator(factorial)(x)
factorial = factorialGenerator(factorialGenerator, facGenerator)
facGenerator = (fac1) ->
(x) ->
if x is 1 then return 1
x * fac1(x - 1)
factorial = y(facGenerator)
factorial(6) # == 720
get rid of second param, because its in scope now
y = (facGenerator) ->
factorialGenerator = (fnGenerator) ->
(x) ->
factorial = fnGenerator(fnGenerator)
facGenerator(factorial)(x)
factorial = factorialGenerator(factorialGenerator)
facGenerator = (fac1) ->
(x) ->
if x is 1 then return 1
x * fac1(x - 1)
factorial = y(facGenerator)
factorial(6) # == 720
and now
y = (facGenerator) ->
factorialGenerator = (fnGenerator) ->
(x) ->
factorial = fnGenerator(fnGenerator)
facGenerator(factorial)(x)
factorial = factorialGenerator(factorialGenerator)
facGenerator = (fac1) ->
(x) ->
if x is 1 then return 1
x * fac1(x - 1)
factorial = y(facGenerator)
factorial(6) # == 720
there's more
y = (facGenerator) ->
factorialGenerator = (fnGenerator) ->
(x) -> facGenerator(fnGenerator(fnGenerator))(x)
factorial = factorialGenerator(factorialGenerator)
facGenerator = (fac1) ->
(x) ->
if x is 1 then return 1
x * fac1(x - 1)
factorial = y(facGenerator)
factorial(6) # == 720
more
y = (facGenerator) ->
factorialGenerator = (fnGenerator) ->
(x) -> facGenerator(fnGenerator(fnGenerator))(x)
factorialGenerator(factorialGenerator)
facGenerator = (fac1) ->
(x) ->
if x is 1 then return 1
x * fac1(x - 1)
factorial = y(facGenerator)
factorial(6) # == 720
more again
y = (facGenerator) ->
(
(fnGenerator) ->
(x) -> facGenerator(fnGenerator(fnGenerator))(x)
)(
(fnGenerator) ->
(x) -> facGenerator(fnGenerator(fnGenerator))(x)
)
facGenerator = (fac1) ->
(x) ->
if x is 1 then return 1
x * fac1(x - 1)
factorial = y(facGenerator)
factorial(6) # == 720
and again. simplify var names.
y = (f) ->
(
(g) ->
(x) -> f(g(g))(x)
)(
(g) ->
(x) -> f(g(g))(x)
)
facGenerator = (fac1) ->
(x) ->
if x is 1 then return 1
x * fac1(x - 1)
factorial = y(facGenerator)
factorial(6) # == 720
one line it
y = (f) -> ((g) -> (x) -> f(g(g))(x))((g) -> (x) -> f(g(g))(x))
facGenerator = (fac1) ->
(x) ->
if x is 1 then return 1
x * fac1(x - 1)
factorial = y(facGenerator)
factorial(6) # == 720
The final formula is a bit different. Are they eqaul. They both work for factorial.
I also wrote some fixed-point combinators implementations a while ago (https://gist.github.com/shesek/3059994 ):