PHP can’t jump? Thing about recursion.


Let’s get straight into the problem – assume we want to calculate nth  Fibonacci number. Definition : F(n) = F(n-1) + F(n-2) with seed values F(1) = F(2) = 1  so the most intuitive way to do this is just from the definition (recursive)

Yay, everything works, so let’s play with bigger numbers. I would like to know the 35th Fibonacci number. On my machine it takes about 8 seconds. That sucks and takes definitely too long. Let’s have a look on our algorithm:
Line return fibonacci($n - 1) + fibonacci($n - 2) for every function call creates another 2, so for 35th Fibonacci number it means our function is called 18454929 times (29860703 calls for 36th number). Something went really wrong here. Let’s try implementing it in a way, where there will be only one another call. So at the first call calculate first number, at second call second, and so on.

It works fast (0.2s for 36th number). Now we can calculate bigger numbers. For fibonacci(250) we’ll get 1.2776523572925E+52. We can live with that or get the full number representation, but for that we will need to use a library, and pass numbers as strings. I’m using the BC Math and its bcadd function.

And now we’ve got the full 250th Fibonacci number: 12776523572924732586037033894655031898659556447352249!
But what if we call fibonacci(255)? With standard php ini configuration an error occurred: Fatal error: Maximum function nesting level of '256' reached, aborting! We can change ini file in order to have more nesting levels or we can do something to optimize our calls. And here comes the trampoline. Instead of going deeper from one function call into another one we can call them in the iterative way – one after the other and “jump” from the first call to the second and so on until we have the result. To do it – instead of returning the result of called function we have to return our function wrapped into anonymous functions, which our trampoline will call until one of them return something not callable and have some kind of initiator function which will create our trampoline.

It’s fast, and works well but it’s ugly because we have everything in simple functions. I wrapped it into objects:

In my opinion now it now looks great! It’s testable and mockable.

It was a pure academic example. Now we can solve a real life issue. Let’s implement array_walk_recursive function (to simplify I’ll pass only the node value without a key to callback).

And now a simple benchmark:

On my machine, array_walk_recursive is few to dozen times faster than my implementation, depending on the array size and nesting level, but with enough nested levels (for me it was about 28000) array_walk_recursive causes segfault while my implementation still works. It looks like I won this time.

I found out about trampolines from the lecture presented during PHPconPL 2016 and it inspired me to do some research on this topic. There is a lot of examples in JS but unfortunately justa a few in PHP. You can find more about an advanced trampoline implementation in this library:

Leave a Reply

Your email address will not be published. Required fields are marked *