Recursion and Generators
A dumb experiment
Generators are awesome. If they’re new to you then take some time to read where they come from and what they do. If you’ve come from a particular programming language background, they may be difficult for you to understand.
They were, and continue to be, tricky for me to grasp. So I’ve spent loads of time trying to understand them, and what they can do for my code.
This morning Lee Davis asked about maintaining state in recursive functions, and I jokingly replied “sounds like a job for generators and array_reduce”. I didn’t really think recursive functions should be replaced with generators and array functions, but it got me thinking…
How good would generators be for implementing recursive functionality?
Sorting
Fibonacci is boring! Let’s instead look at an implementation of Bubble Sort. As sorting algorithms go, Bubble Sort is horrible. As an illustration of something which could be implemented recursively, it’s great!
function bubble_iterative(array $items) {
$times = count($items);
while($times) {
for ($i = 1; $i < $times; $i++) {
$prev = $items[$i - 1];
$next = $items[$i];
if ($prev > $next) {
$items[$i] = $prev;
$items[$i - 1] = $next;
}
}
$times--;
}
return $items;
}
$items = [1, 6, 2, 5, 3, 4];
bubble_iterative($items); // [1, 2, 3, 4, 5, 6]Bubble Sort works by comparing each item with the next and swapping them so that the list becomes ordered by smallest to greatest. It’s a simple algorithm, and while this may not be the best implementation example, it should be easy to see what’s going on with it.
Ok, so how would we implement this kind of thing recursively?
function bubble_recursive(array $items, $times = null) {
if ($times === null) {
$times = count($items);
}
$items = bubble_recursive_inner($items, $times);
if ($times > 1) {
return bubble_recursive($items, $times - 1);
}
return $items;
}
function bubble_recursive_inner(array $items, $times, $i = 1) {
if ($i < $times) {
$prev = $items[$i - 1];
$next = $items[$i];
if ($prev > $next) {
$items[$i] = $prev;
$items[$i - 1] = $next;
}
return bubble_recursive_inner($items, $times, $i + 1);
}
return $items;
}
$items = [1, 6, 2, 5, 3, 4];
bubble_recursive($items); // [1, 2, 3, 4, 5, 6]Seems we need a recursive function for every loop we’re replacing. Again, probably not the best implementation, but it sure is recursive.
Generators
Let’s go back to the iterative example and think of how we can start replacing loops and/or recursion with generators…
function bubble_generative(array $items) {
$times = count($items);
while($times) {
for ($i = 1; $i < $times; $i++) {
$prev = $items[$i - 1];
$next = $items[$i];
if ($prev > $next) {
$items[$i] = $prev;
$items[$i - 1] = $next;
}
yield $items;
}
yield $items;
$times--;
}
yield $items;
}
$items = [1, 6, 2, 5, 3, 4];
$generator = bubble_generative($items);
foreach ($generator as $iteration) {
$last = $iteration;
}
$last; // [1, 2, 3, 4, 5, 6]Generators suspend execution at each yield keyword. We’re still doing the same iteration we were doing before, but now we get to peek inside the function to see what the items are at each step.
We could begin to split this up, again…
function bubble_generative_inner($items, $times) {
for ($i = 1; $i < $times; $i++) {
$prev = $items[$i - 1];
$next = $items[$i];
if ($prev > $next) {
$items[$i] = $prev;
$items[$i - 1] = $next;
}
yield $items;
}
}
function bubble_generative($items) {
$times = count($items);
while($times) {
$inner = bubble_generative_inner($items, $times);
foreach ($inner as $items) {
yield $items;
}
$times--;
}
}So what have we really gained? Well, aside from being able to see their state; not much really. We could put state into them…
function bubble_generative_inner($items, $times) {
$last = $items;
for ($i = 1; $i < $times; $i++) {
$prev = $items[$i - 1];
$next = $items[$i];
if ($prev > $next) {
$items[$i] = $prev;
$items[$i - 1] = $next;
}
yield [$items, $times, $items == $last];
}
}
function bubble_generative($items) {
$times = count($items);
while($times) {
$inner = bubble_generative_inner($items, $times);
foreach ($inner as $result) {
$operation = (yield $result);
}
if ($operation === "break") {
break;
}
$times--;
}
}
$items = [1, 6, 2, 5, 3, 4];
$generator = bubble_generative($items);
$repeats = 0;
foreach ($generator as $i => list($items, $times, $repeated)) {
if ($repeated) {
$repeats++;
}
if ($repeats >= $times) {
$generator->send("break");
}
$last = $items;
}We can modify the generators to return arrays of data, so we can tell more about each iteration. For instance, we can tell whether inner iterations yield the same sort order, and when we’ve seen enough repeats, terminate the sort.
On the same array of items, this reduces the number of iterations from 15 to 13. If we apply the sort to the already sorted 6 integers, the number of iterations drops to 9.
Now, this isn’t a lesson on optimising Bubble Sort. It’s just an interesting use of generators. Is it genuinely useful? Not really. Should you use generators instead of recursion or simple iteration? Perhaps…
The question is, why do we use recursion? It’s not obviously faster than simple iteration. Not in every case. So why do we use recursion?
I think we sometimes use recursion because it allows the transfer of state, from one iteration to the next. We could use variables to do this, but there’s something elegant in how the state moves from nested function call to nested function call.
It’s not that generators give us additional computational abilities over recursion, or recursion over iteration. It’s just that recursion sometimes looks more elegant, or more expressive.
Iterators are just shorthand for loops/recursion and generators are just shorthand for iterators. It’s all the same stuff. The trick is finding the times when generators are the more elegant approach.
I’ll let you decide if it was more elegant, in this case:
array_reduce(
iterator_to_array(
bubble_generative($items)
),
function($carry, $item) {
return $item[0];
}
);