Looking for more information on how to do PHP the right way? Check out PHP: The Right Way

Hubert Brylkowski:
PHP can’t jump? Thing about recursion.
Dec 26, 2016 @ 21:14:37

Hubert Brylkowski has written up a post to his site looking at recursion in PHP and some of the limitations that can some with traditional methods.

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.

He talks about what some of the issues with this normal recursive method is (including how many times the function is called) and a possible way to resolve it. He updates this to use the BCMath handling as the numbers are starting to get larger but soon hits the max nesting level for PHP itself. Instead of traditional recursion, he suggests using a few functions/methods to to "jump" from one call to the next without one having to call the other. He includes some refactoring of this solution and a bit of benchmarking to show the performance gain over traditional methods.

tagged: recursion jump alternative benchmark tutorial fibonacci number

Link: http://brylkowski.com/php-cant-jump-thing-about-recursion/


Trending Topics: