Ответ 1

Наконец-то я определил реальное использование рекурсивных генераторов.

Недавно я изучал QuadTree datastructures. Для тех, кто не знаком с QuadTrees, они используют древовидную структуру дерева для геопространственной индексации и позволяют быстро искать поиск всех точек/местоположений в пределах определенной ограничивающей рамки. Каждый node в QuadTree представляет сегмент отображаемой области и действует как ведро, в котором хранятся местоположения... но ведро с ограниченным размером. Когда ведро переполняется, QuadTree node разделяет 4 дочерних узла, представляющих северо-западную, северо-восточную, юго-западную и юго-восточную области родительского node, и начинает заполнять их.

При поиске местоположений, попадающих в указанный ограничивающий прямоугольник, процедура поиска начинается с верхнего уровня node, проверяя все местоположения в этом ковше; затем рекурсирует в дочерние узлы, проверяя, пересекаются ли они с ограничивающей рамкой или охвачены ограничивающей рамкой, проверяя каждый QuadTree node внутри этого набора, а затем снова рекурсивный вниз через дерево. Каждый node может возвращать ни одного, ни одного или нескольких местоположений.

Я реализовал базовый QuadTree в PHP, предназначенный для возврата массива результатов; затем понял, что это может быть допустимый прецедент для рекурсивного генератора, поэтому я реализовал GeneratorQuadTree, к которому можно получить доступ в цикле foreach(), дающем единственный результат каждая итерация.

Кажется, это более эффективный вариант использования для рекурсивных генераторов, потому что он является действительно рекурсивной функцией поиска и потому, что каждый генератор может возвращать ни один, ни один или несколько результатов, а не один результат. Эффективно каждый вложенный генератор обрабатывает часть поиска, подавая свои результаты обратно через дерево через своего родителя.

Этот код слишком много для публикации здесь; но вы можете взглянуть на реализацию на github.

Он меньше медленнее, чем версия, отличная от генератора (но не значительно): основным преимуществом является сокращение памяти, поскольку оно не просто возвращает массив переменной величины (что может быть значительным преимуществом в зависимости от количества результатов возвращается). Самым большим недостатком является то, что результаты не могут быть легко отсортированы (моя версия, отличная от генератора, выполняет функцию usort() в массиве результатов после ее возврата).

Ответ 2

Итак, проблема, с которой я столкнулась при попытке создания рекурсивной функции генератора, заключается в том, что, пройдя свой первый уровень глубины, каждый последующий выход уступает его родительскому вызову, а не реализации итерации (цикл).

Как и в php 7, добавлена ​​новая функция, которая позволяет выводить из следующую функцию генератора. Это новая функция Делегация генераторов: https://wiki.php.net/rfc/generator-delegation

Это позволяет нам выходить из последующих рекурсивных вызовов, что означает, что теперь мы можем эффективно записывать рекурсивные функции с использованием генераторов.

$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";
}

Это дает следующий результат.

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

Ответ 3

function fibonacci($n)
{
    if($n < 2) {
        yield $n;
    }

    $x = fibonacci($n-1);
    $y = fibonacci($n-2);
    yield $x->current() + $y->current();
}


for($i = 0; $i <= 10; $i++) {
    $x = fibonacci($i);
    $value = $x->current();
    echo $i , ' -> ' , $value, PHP_EOL;
}

Ответ 4

Благодаря Mark Baker Я понял, что реальный прецедент для этого трудно найти (если не невозможно).

Генератор не является функцией, да (может быть, это меня смутило) - поэтому "вызов" внутри внутри с "рекурсивным" параметром почти бесполезен. Мы можем действовать, как предположил Марк, но, немного подумав, я закончил этот код для моей последовательности Фибоначчи:

function xfibonacci($n)
{
   $recursion = function($n) use (&$recursion)
   {
      return $n<2?$n:$recursion($n-1)+$recursion($n-2);
   };
   for($i=0; $i<$n; $i++)
   {
      yield $recursion($i);
   }  
}
//...
foreach(xfibonacci(6) as $i)
{
   echo('num is: '.$i.PHP_EOL);//0,1,1,2,3,5
}

- и, что более важно, его можно легко преобразовать в обычный случай, когда мы хотим иметь генератор, который опирается на некоторую рекурсивную функцию генерации последовательности. Итак, это будет:

function xrecursive($n, callable $callback, $args=null)
{
   for($i=0; $i<$n; $i++)
   {
      yield is_array($args)?
         call_user_func_array($callback, array_merge([$i], $args)):
         call_user_func_array($callback, [$i]);
   }  
}

- с образцом использования:

//factorial:
foreach(xrecursive(6, $f=function($n) use (&$f){return $n?$n*$f($n-1):1;}) as $i)
{
   echo('num is: '.$i.PHP_EOL);//1,1,2,6,24,120
}

-so, генератор, который полагается на функцию рекурсивной генерации последовательности, может быть разделен на реализацию. Это не полный ответ для оригинального вопроса (так как могут быть способы реализации желаемого поведения) - но в то же время я думаю, что это более правильный способ использования генератора в контексте генерации рекурсивных последовательностей.

Ответ 5

Если вы сначала хотите создать генератор, вы можете использовать итеративную версию фибоначчи:

function fibonacci ($from, $to)
{
  $a = 0;
  $b = 1;
  $tmp;
  while( $to > 0 ) {
    if( $from > 0 )
      $from--;
    else
      yield $a;

    $tmp = $a + $b;
    $a=$b;
    $b=$tmp;
    $to--;
  }
}

foreach( fibonacci(10,20) as $fib ) {  
    print "$fib "; // prints "55 89 144 233 377 610 987 1597 2584 4181 " 
}

Ответ 6

Здесь рекурсивный генератор для комбинаций (порядок несущественный, без замены):

<?php

function comb($set = [], $size = 0) {
    if ($size == 0) {
        // end of recursion
        yield [];
    }
    // since nothing to yield for an empty set...
    elseif ($set) {
        $prefix = [array_shift($set)];

        foreach (comb($set, $size-1) as $suffix) {
            yield array_merge($prefix, $suffix);
        }

        // same as `yield from comb($set, $size);`
        foreach (comb($set, $size) as $next) {
            yield $next;
        }
    }
}

// let verify correctness
assert(iterator_to_array(comb([0, 1, 2, 3, 4], 3)) == [
    [0, 1, 2], [0, 1, 3], [0, 1, 4], [0, 2, 3], [0, 2, 4],
    [0, 3, 4], [1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]
]);

foreach (comb([0, 1, 2, 3], 3) as $combination) {
    echo implode(", ", $combination), "\n";
}

Выходы:

0, 1, 2
0, 1, 3
0, 2, 3
1, 2, 3

То же самое, что и без урона.

Ответ 7

Недавно возникла проблема, которая требовала "рекурсивных" генераторов или генератора. В итоге я написал небольшую функцию, которая преобразует делегированные вызовы генераторов в один генератор.

Я превратил его в пакет, чтобы вы могли просто потребовать его с композитором или проверить источник здесь: hedronium/generator-nest.

код:

function nested(Iterator $generator)
{
    $cur = 0;
    $gens = [$generator];

    while ($cur > -1) {
        if ($gens[$cur]->valid()) {
            $key = $gens[$cur]->key();
            $val = $gens[$cur]->current();
            $gens[$cur]->next();
            if ($val instanceof Generator) {
                $gens[] = $val;
                $cur++;
            } else {
                yield $key => $val;
            }
        } else {
            array_pop($gens);
            $cur--;
        }
    }
}

Вы используете его как:

foreach (nested(recursive_generator()) as $combination) {
    // your code
}

Ознакомьтесь с этой ссылкой выше. В нем есть примеры.

Ответ 8

Короткий ответ: рекурсивные генераторы просты. Пример прохода по дереву:

class Node {

    public function getChildren() {
        return [ /* array of children */ ];
    }

    public function walk() {
        yield $this;

        foreach ($this->getChildren() as $child) {
            foreach ($child->walk() as $return) {
                yield $return;
            };
        }
    }
}

Все.

Длинный ответ о фибоначчи:

Генератор - это то, что используется с foreach (generator() as $item) { ... }. Но OP хочет, чтобы функция fib() возвращала int, но в то же время он хочет вернуть generator для использования в foreach. Это очень запутанно.

Можно реализовать рекурсивное генераторное решение для фибоначчи. Нам просто нужно включить внутри fib() функцию цикла, которая действительно будет yield каждого члена последовательности. Поскольку генератор предполагается использовать с foreach, он выглядит действительно странным, и я не думаю, что он эффективен, но вот он:

function fibGenerator($n) {
    if ($n < 2) {
        yield $n;
        return;
    }

    // calculating current number
    $x1 = fibGenerator($n - 1);
    $x2 = fibGenerator($n - 2);
    $result = $x1->current() + $x2->current();

    // yielding the sequence
    yield $result;
    yield $x1->current();
    yield $x2->current();

    for ($n = $n - 3; $n >= 0; $n--) {
        $res = fibGenerator($n);
        yield $res->current();
    }
}

foreach (fibGenerator(15) as $x) {
    echo $x . " ";
}

Ответ 9

Я предлагаю два решения для числа Фибоначчи с рекурсией и без нее:

function fib($n)
{
    return ($n < 3) ? ($n == 0) ? 0 : 1 : fib($n - 1) + fib($n - 2);
}
function fib2()
{
    $a = 0;
    $b = 1;
    for ($i = 1; $i <= 10; $i++)
    {
        echo $a  . "\n";
        $a = $a + $b;
        $b = $a - $b;
    }
}

for ($i = 0; $i <= 10; $i++)
{
    echo fib($i) . "\n";
}

echo fib2();