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

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

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

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

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

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

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

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

Начиная с 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 

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

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

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

 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 } 

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

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

 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 " } , 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 " } которых 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 " } 

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

 <?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's 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 

То же самое, что не уступает.

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

Я превратил его в пакет, чтобы вы могли просто потребовать его с композитором или проверить источник здесь: 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 } 

Проверьте, что ссылка выше. У него есть примеры.

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

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

Это все.

Длинные ответы о fibonacci:

Генератор – это то, что используется с 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 . " "; } 

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

 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();