Recursive generators in PHP

Question

Introduction

Since version 5.5 in PHP there's such great thing as generators. I will not repeat official manual page, but they are great thing for short definition of iterators. The most-known sample is:

function xrange($from, $till, $step) {    if ($from>$till || $step<=0)    {       throw new InvalidArgumentException('Invalid range initializers');    }     for ($i = $from; $i < $till; $i += $step)    {       yield $i;    } }  //...  foreach (xrange(2, 13, 3) as $i) {    echo($i.PHP_EOL); // 2,5,8,11 } 

and generator is actually not a function, but an instance of a concrete class:

get_class(xrange(1, 10, 1)); // Generator 

The problem

Done with RTM stuff, now moving on to my question. Imagine that we want to create generator of Fibonacci numbers. Normally, to get those, we can use simple function:

function fibonacci($n) {    if(!is_int($n) || $n<0)    {       throw new InvalidArgumentException('Invalid sequence limit');    }    return $n < 2 ? $n : fibonacci($n-1) + fibonacci($n-2); }  var_dump(fibonacci(6)); // 8 

Let's transform this into something, that holds sequence and not only it's last member:

function fibonacci($n) {    if (!is_int($n) || $n<0)    {       throw new InvalidArgumentException('Invalid sequence limit');    }    if ($n<2)    {       return range(0, $n);    }    $n1 = fibonacci($n-1);    $n2 = fibonacci($n-2);    return array_merge($n1, [array_pop($n1)+array_pop($n2)]); }  //...  foreach (fibonacci(6) as $i) {    echo($i.PHP_EOL); // 0,1,1,2,3,5,8 } 

We have now a function that returns array with full sequence

The question

Finally, the question part: how can I transform my latest fibonacci function so it will yield my values, not holding them in an array? My $n can be big, so I want to use benefits of generators, like in xrange sample. Pseudo-code will be:

function fibonacci($n) {    if (!is_int($n) || $n<0)    {       throw new InvalidArgumentException('Invalid sequence limit');    }     if ($n<2)    {       yield $n;    }     yield fibonacci($n-2) + fibonacci($n-1); } 

But this, obviously, is crap since we can't handle with it like this way because recursion will cause object of class Generator and not int value.

Bonus: getting fibonacci sequence is just a sample for more general question: how to use generators with recursion in common case? Of course, I can use standard Iterator for that or re-write my function to avoid recursion. But I want to achieve that with generators. Is this possible? Does this worth efforts to use this such way?

Answer 1

So the issue I ran into when attempting to create a recursive generator function, is that once you go past your first depth level each subsequent yield is yielding to its parent call rather than the iteration implementation (the loop).

As of php 7 a new feature has been added that allows you to yield from a subsequent generator function. This is the new Generator Delegation feature: https://wiki.php.net/rfc/generator-delegation

This allows us to yield from subsequent recursive calls, which means we can now efficiently write recursive functions with the use of generators.

$items = ['what', 'this', 'is', ['is', 'a', ['nested', 'array', ['with', 'a', 'bunch',  ['of', ['values']]]]]];  function processItems($items) {     foreach ($items as $value)     {         if (is_array($value))         {             yield from processItems($value);             continue;         }         yield $value;     } }  foreach (processItems($items) as $item) {     echo $item . "\n"; } 

This gives the following output..

what this is is a nested array with a bunch of values