Since PHP 5.3 now has closures, all things that other languages with closures do should also be possible. One of them is having recursive closures. I.e. something like this:

```
$factorial = function($n) {
if ($n <= 1)
return 1;
else
return $n * call_user_func(__FUNCTION__, $n - 1);
};
```

which does not work. One of the ways to do it is to use Y combinator function, which allows, by application of dark magic and friendly spirits from other dimensions, to convert non-recursive code to recursive code. In PHP, Y combinator function would look like this:

```
function Y($F) {
$func = function ($f) { return $f($f); };
return $func(function ($f) use($F) {
return $F(function ($x) use($f) {
$ff = $f($f);
return $ff($x);
});
});
}
```

And then the factorial function would be:

```
$factorial = Y(function($fact) {
return function($n) use($fact) {
return ($n <= 1)?1:$n*$fact($n-1);
};
});
```

Which does work:

```
var_dump($factorial(6)); ==> int(720)
```

Of course, we could also cheat and go this way:

```
$factorial = function($n) use (&$factorial) {
if ($n <= 1)
return 1;
else
return $n * $factorial($n - 1);
};
```

Doing Y-combinator in PHP was attempted before (and here), but now I think it works better. It could be even nicer if PHP syntax allowed chaining function invocations – ($foo($bar))($baz) – but for now it doesn’t.

If you wonder, using such techniques does have legitimate applications, though I’m not sure if doing it in PHP this way is worth the trouble.

Pingback: » Перетворення не рекурсивної функції в рекурсивну Замітки програмуючого програміста :)

Pingback: PHP 5.3 : Practical look into Lambda functions and closures | Test site

Pingback: Anonymous (lambda) functions in PHP | Living with PHP

Pingback: 5.3!!! | BrainPair - the Techno Blog

Pingback: 5.3!!! « PHP 10.0 Blog

Да, есть над чем задуматься. Спасибо!

Thank you very much :) I was wondering how PHP can handle recursive closures and you just gave me the answer.

Would scandir() (when used recursively) be a good candidate for a YCombinator?

Would scandir() (when used to walk a directory structure, not just a single directory) be a good candidate for a YCombinator?

Pingback: Y-Combinator in PHP " PHP 10.0 Blog « DevEzine

Pingback: PHP 10.1 Blog: Y-Combinator in PHP : Dragonfly Networks

Correct me if i’m wrong but the Y-combinator for Fibonacci is exponential. It becomes linear only when you add caching. Seems to me it is possible to add caching the recursive function either. So the performance boost comes not from using Y-combinator but caching.

My question then is if there’s any performance boost to Y-combinator at all?

Žilvinas, yes – see the “legitimate applications” like for an example of caching Y-combinator for Fibonacci numbers.

I’d doubt there’s much performance boost from using Y-combinator alone. But I won’t be surprised if some creative use of it allowed doing some stuff faster.

what is this “y” combinator in php……..

amazing stuff, thanks for posting this Stas, and especially the link to the legitimate application usage. This faster recursion may be very useful in an app like phpDocumentor, which does lots of recursive processing.