Counting to 1000 in PHP without loops or conditionals

14 Mar 2011

Update: added a benchmark for performance comparison and updated the code to no longer rely on a fatal error to exit.

It started with one question:

Print numbers from 1 to 1000 without using any loop or conditional statements. Don’t just write the printf() or cout statement 1000 times.

How would you do that using C or C++?

Source: Stack Overflow

My favorite answer was an amazing example of obscure C. Using math to iterate between two function pointers (printf and exit). And while it brought back memories of my C days, I kind of left it at that.

Later in the day, one of my co-workers messaged me with his version of a 1-1000 iterator in PHP. So naturally, I had to write my own version.

Remember the rules: no control loops and no conditionals.

I hammered out a quick example using an array to simulate the pointer technique used in my favorite C-language solution. It was 10 lines of code. I managed to break it down to one function call:


call_user_func( $x = function( $f, $i=1 ) {
  echo "$i\n", $f[floor($i/1000)]($f, ++$i);
}, array( $x, function(){} ));


Try it. Assuming that you have PHP 5.3 for the lambda functions, it will work. Now to break down why it works:

The call_user_function call takes a callback as the first parameter and passes all subsequent parameters directly to the callback. A callback in PHP can be a string, array, or lambda function. I’m using the later here.

My lambda function takes two parameters. An array and a counter. If the counter is not specified it will default to one. The trickier part is the array. In this case it is an array of functions. My function is recursive so the array needs to reference it. By taking advantage of the left-to-right nature of PHP, I am assigning the function to the variable $x prior to the array being constructed.

Now, inside my function I am echoing the value of $i and the return value of the recursive function (which is undefined... it’s just a little cheat to keep it on one line).

Now to break down the second parameter to the echo.

It looks up a function in the array that is passed in. Remember, the array contains only one value (the function itself) two values (the function itself and an empty exit function). It uses the floor of $i/1000 as the array index. Which means that the value will be 0 until $i is equal to 1000. Then it passes in the array and the counter. Remember that if the ++ is before the variable then the increment will happen prior to the enclosing function being called.

When the index does hit 1, there will be an error. I suppressed that using the @ operator it will call the empty function. At this point the recursion ends.

And we’re done.

Benchmarks (added March 15th)

This is obviously meant to be a thought exercise and not a practical thing to do in a real-world application but I thought it might be fun to run some tests against a normal loop. I upped the loop to 1,000,000 to make things more interesting. Here is my test code:

ini_set('memory_limit', '1000M');
const COUNT = 1000000;
$t1 = 0;
$t2 = 0;
$s = microtime(true);
  echo "$i\n",  $f[floor($i/COUNT)]($f, ++$i);
$t1 = microtime(true)-$s;
$s = microtime(true);
for ( $i=0; $i<COUNT; $i++ ) {
  echo "$i\n";
$t2 = microtime(true)-$s;
echo 'Recursive: '.number_format($t1,2)."s\n";
echo 'Loop: '.number_format($t2,2)."s\n";
Recursive: 6.38s
Loop: 5.28s

Not to mention that every recursive call needs to add the current state to the stack. Which is why the memory limit is increased the the beginning of the script. So clearly it is impractical. However, I’m actually a little surprised that the results are as close at they are.