php: doing recursion with recursive iterator(iterator)s
Tags: php, webdev
Published: 2024-06-05 15:49:32

recursion has a bad reputation amongst programmers; it's convoluted and complicated and difficult to debug, a real footgun. it's something you do at school (if you went to school for that sort of thing) and then never touch again if you can avoid it. which is a drag, because there's a lot of use cases for recursion. data structures of arbitrary depth are everywhere: file systems, dom trees, that 32kb json packet your integration partner just shovelled into your api.

in this post we're going to over two features of php that help make recursion easier: the [`RecursiveIterator`](https://gbh.fruitbat.io/2024/06/04/php-doing-recursion-with-recursive-iteratoriterators/) interface, which provides us with methods and features that make writing recursive functions easier, and the dreadfully-named [`RecursiveIteratorIterator`](https://gbh.fruitbat.io/2024/06/04/php-doing-recursion-with-recursive-iteratoriterators/) class which we can use to flatten down arbitrarily-deep data structures.

![iterate the iterator with an iterator iterator](https://gbh.fruitbat.io/wp-content/uploads/2024/05/meme_iterator.jpg "the despicable me meme that says 'iterate the iterator with an iterator iterator'")<figcaption>php to developers: “say ‘iterator’ five times fast”</figcaption>

we'll be building a recursive function using `RecursiveArrayIterator`, starting with a simple loop and working up to the full function. then we'll look at how leverage `RecursiveIteratorIterator` to smash that nested array into a single level so we can extract data, either with a simple loop or a more-complex-but-powerful call to `iterator_apply`.

## our sample array

all of the examples here are going to use the following sample array that represents an underwhelming collection of record albums:

```php
$albums = [ 
    'first_name' => 'grant',
    'last_name' => 'horwood',
    'albums' => [
        [
            'title' => 'pottymouth',
            'artist' => 'bratmobile',
            'year' => 1993,
        ],  
        [   
            'title' => 'monks music',
            'artist' => 'monk, thelonious',
            'year' => 1957,
        ],  
    ],  
];
```

this array contains three top-level elements, one of which (`albums`) is an array of arrays. this is good stuff for recursion.

## the `RecursiveIterator` interface

here are the two main things we need to know about the `RecursiveIterator` interface:


1. **it's an interface:** `RecursiveIterator` doesn't actually do anything itself, it's just an interface that defines behaviour. if we want something usable, we have to look at classes that implement `RecursiveIterator`; classes like [`RecursiveArrayIterator`](https://www.php.net/manual/en/class.recursivearrayiterator.php) (for handling arrays) and [`RecursiveDirectoryIterator`](https://www.php.net/manual/en/class.recursivedirectoryiterator.php) (for handling filesystems).
2. **it doesn't actually do any recursion:** classes that implement `RecursiveIterator` don't do recursion for us. what they do is provide tools to help us build our own recursive functions more easily.

that may seem disappointing, but it shouldn't be: those tools that `RecursiveIterator` provide are useful. let's look at the three of them.

* **`hasChildren()`:** a data structure of arbitrary depth, like an array, can have values that are, themselves, arrays. the `hasChildren` method tests if the value we're looking is an array itself. we use this to test when we need our recursive function to actually recurse. it returns a boolean.

* **`getChildren()`:** if `hasChildren` returns `true` then we're going to need to need to get an iterator of current value so we have something to recurse with. that's what `getChildren` does.

* **a cursor:** as we loop over our `RecursiveIterator`, there's an internal cursor that keeps track of where we are in the array. this allows us to call methods like `hasChildren` for the current element. this is very handy.

if that didn't make immediate sense, don't worry; we're going to go over building a recursive function with `RecursiveIterator` step by step, starting with a not-very-useful loop.

## a simple (and not-very-useful) loop with `RecursiveArrayIterator`

because `RecursiveArrayIterator` is an iterator, we can use it in a `foreach` loop. let's do that.

```php
$rai = new RecursiveArrayIterator($albums);

foreach($rai as $k => $v) {
    @print "$k => $v".PHP_EOL;
}
```

this is pretty straighforward: we create a new instance of `RecursiveArrayIterator` with our array and then do a `foreach`, printing out keys and values. the results are underwhelming.

```
first_name => grant
last_name => horwood
albums => Array
```

this is straight iterator behaviour; our loop went over the top level of the array and that's it. to start building a recursive function that does what we want, we're going to need to use `RecursiveIterator`'s `hasChildren` and `getChildren` methods.

## using `hasChildren`

as the name implies, the purpose of `hasChildren` is to determine if the current value is an array that can build an iterator from. let's add `hasChildren` to our disappointing loop.

```php
$rai = new RecursiveArrayIterator($albums);

foreach($rai as $k => $v) {
    print $k;
    if($rai->hasChildren()) {
        print " has children";
    }
    print PHP_EOL;
}
```

here, we test if the value of the current element is an array, ie. it has a number of 'child' elements, and print out 'has children' if it is. the output is:

```
first_name
last_name
albums has children
```

---

ℹ️ **important note about cursors:** we see here that we call the method `hasChildren` on `$rai`, the `RecursiveArrayIterator` object itself. we can do this because `RecursiveArrayIterator` has an internal cursor pointing to the current element we're looping over. as we loop, this cursor advances to the next element so that when we call methods on the iterator object it's always for the element we're working on.

---

## once we have children, we can `getChildren`

now that we know `albums` has children, we can get a new `RecursiveArrayIterator` object for that array with `getChildren` and iterate over that. for instance:

```php
$rai = new RecursiveArrayIterator($albums);

foreach($rai as $k => $v) {
    print $k." => ";
    if($rai->hasChildren()) {
        $rai2 = $rai->getChildren();
        foreach($rai2 as $k2 => $v2) {
            @print PHP_EOL."  $k2 => $v2";
        }
    }
    else {
        print $v;
    }
    print PHP_EOL;
}
```

the biggest change we have made here is that, when `hasChildren` returns `true`, we get a new `RecursiveArrayIterator` object for those children with `getChildren` and then loop over that. the output is:

```
first_name => grant
last_name => horwood
albums => 
  0 => Array
  1 => Array
```

now we have all the tools to build a recursive function that will handle our entire array.

## at last: building a recursive function that will handle our entire array

upgrading our loop to a recursive function now only requires us to do two things:

1. put our loop in a function
2. have our function call itself when `hasChildren` return `true`

that's literally it. let's look:

```php
$rai = new RecursiveArrayIterator($albums);

function recurse(RecursiveArrayIterator $rai) {
    foreach($rai as $k => $v) {
        if($rai->hasChildren()) {
            recurse($rai->getChildren());
        }
        else {
            print "$k => $v".PHP_EOL;
        }
    }
}

// call our recursive function
recurse($rai);
```

our function accepts one argument, a `RecursiveArrayIterator` object. when we call that function, it loops over the top level of that array, printing out key/value pairs. when it encounters a value that `hasChildren`, it creates a new iterator with `getChildren` and then calls itself with that new iterator as an argument, looping over the next level down of the array. this keeps going until the first loop runs out of elements.

the output looks like this

```
first_name => grant
last_name => horwood
title => pottymouth
artist => bratmobile
year => 1993
title => monks music
artist => monk, thelonious
year => 1957
```

this is great stuff. except that we've lost the structure of our array. it's been 'flattened' down to one level.

of course, this can still be useful. lots of languages have built-in 'flattening' commands to do precisely this (i write a lot of scala and use the [`flatten`](https://allaboutscala.com/tutorials/chapter-8-beginner-tutorial-using-scala-collection-functions/scala-flatten-function-example/) method all the time).

but maybe we want to keep that structure. for that we need to add an accumulator.

!["successful recursion"](https://gbh.fruitbat.io/wp-content/uploads/2024/05/meme_recursion.png, "the moe throwing barney out of the bar meme")<figcaption>a successful recursion</figcaption>


## adding an accumulator to our function

as the name implies, an accumulator is a variable where we accumulate the results of our recursive function while it executes. when our recursion is done, we return it. let's add one to our existing function:

```php
$rai = new RecursiveArrayIterator($albums);

function recurse(RecursiveArrayIterator $rai, Array $accumlator) {
    foreach($rai as $k => $v) {
        if($rai->hasChildren()) {
            // add the return of our next call to recurse to our accumulator
            $accumlator[$k] = recurse($rai->getChildren(), []);
        }
        else {
            // add the key/value pair to the accumulator
            $accumlator[$k] = $v;
        }
    }

    return $accumlator;
}

// call our recursive function with an empty accumulator
$accumlator = recurse($rai, []);

// see the results
print_r($accumlator);
```

here, our accumulator is an array. we pass in an empty one when we call `recurse`, and in our function body instead of printing out our key/value pairs, we add them to the accumulator. when our function terminates, the accumulator is returned.

looking at the return value, we notice that the structure has been maintained. in fact, it is the exact same array as the one we passed to our function. success! kind of.

building a function that returns the same array it was passed is not exactly groundbreaking functionality. what we probably want to do with our recursive function is either transform or filter out some of those values.

we can do that, of course, by adding some code to the line where we assign a value to the accumulator. for instance, if we want to uppercase all of our values, we could add `strtoupper` like so:

```php
$accumlator[$k] = strtoupper($v);
```

or, if we wanted remove the `year` element from every album, we could filter it.

```php
if($k != 'year') {
    $accumlator[$k] = $v;
}
```

now we're doing something useful!

## building a more generic solution

so, now we can traverse our entire array and apply the custom filters or transformations of our choosing. this is good, but it would be much better if we could write up a generic recursion function that took filters and transformations as arguments. let's do that.

```php
$rai = new RecursiveArrayIterator($albums);

/**
 * Traverse the array applying $filter to each key and $transformer to each value
 *
 * @param  RecursiveArrayIterator $rai
 * @param  Array $accumlator
 * @param  callable $filter
 * @param  callable $transformer
 * @return array
 */
function recurse(RecursiveArrayIterator $rai, Array $accumlator, callable $filter = null, callable $transformer = null): Array {

    // a default filter that removes nothing
    $filter = $filter ?? fn($n) => true;

    // a default transformer that changes nothing
    $transformer = $transformer ?? fn($n) => $n;

    foreach($rai as $k => $v) {
        if($rai->hasChildren()) {
            $accumlator[$k] = recurse($rai->getChildren(), [], $filter, $transformer);
        }
        else {
            // test the filter and apply the transformer
            if($filter($k)) {
                $accumlator[$k] = $transformer($v);
            }
        }
    }

    return $accumlator;
}

// filter to apply to each key. remove elements with key 'year'
$filter = fn($n) => $n != 'year';

// transformer to apply to each value. apply uppercase to all values
$transformer = fn($n) => strtoupper($n);

// call our recursive function with an empty accumulator
$accumlator = recurse($rai, [], $filter, $transformer);

// see the results
print_r($accumlator);
```

we've added two new arguments to our function here:

* **`$filter`:** this is a callable that accepts the key of our array element as an argument. it performs a test on the key and returns a boolean. in the above example, we test if the key is `year` and return `false` if it is. this callable is applied to each array element and only the elements that return `true` are added to our accumulator.
* **`$transformer`:** a callable that accepts the value of the element as an argument and applies some functionality to that value. in the example, we uppercase the value with `strtoupper`. the transformed value will be added to the accumulator when we run this example code, we get this:

```php
Array
(
    [first_name] => GRANT
    [last_name] => HORWOOD
    [albums] => Array
        (
            [0] => Array
                (
                    [title] => POTTYMOUTH
                    [artist] => BRATMOBILE
                )
            [1] => Array
                (
                    [title] => MONKS MUSIC
                    [artist] => MONK, THELONIOUS
                )
        )
)
```

all the elements keyed with `year` have been removed and `strtoupper` has been applied to all the values. exactly what we asked for.

if we pass `null`'s for either `$filter` or `$transformer`, the default callables are used: no filtering, no transformation.

this technique has real-world uses. for the [day job](https://fruitbat.studio) a long time ago, i wrote a package to [redact passwords and such from arbitrary json](https://github.com/gbhorwood/Redactem) so we wouldn't be storing those hacker goodies in our log files; recursion with filters and transformers was the solution.

## using `RecursiveIteratorIterator` to flatten arrays

remember back when we did the first recursion and our multi-dimensional array came back flattened to one level?

we can achieve that functionality in a far-less cumbersome way by using the `RecursiveIteratorIterator` class. for example:

```php
$rai = new RecursiveArrayIterator($albums);

// create a RecursiveIteratorIterator object
$rii = new RecursiveIteratorIterator($rai);

// loop over the RecursiveIteratorIterator
foreach($rii as $k => $v) {
    print "$k => $v".PHP_EOL;
}
```

this loop replaces our entire recursive function and spits out the same results, a flattened array:

```
first_name => grant
last_name => horwood
title => pottymouth
artist => bratmobile
year => 1993
title => monks music
artist => monk, thelonious
year => 1957
```

essentially, the `RecursiveIteratorIterator` is just an iterator that loops over our `RecursiveArrayIterator`and all the `RecursiveArrayIterator`s it contains. it's an iterator that iterates over an iterator and all the iterators that iterator contains, recursively. that sentence would have sounded ridiculous at the beginning of this post, but now it makes perfect sense.

## using `iterator_apply` on all this stuff

flattening an array can have a lot of benefits. for instance, if we wanted to just get all of the artists in our album collection, we could write a recursive function with `RecursiveArrayIterator` and extract that information, or we could just flatten the whole thing with `RecursiveIteratorIterator` and grab every value keyed `artist`. the flattening approach is way faster and easier.

there are a couple of ways to extract data from a flattened array, but the first one i'll mention is way that will not work: `array_filter`.

at first glance, `array_filter` seems perfect for the job. we want to filter our array to get only `artist`, after all. however, `array_filter` preserves keys. this is a problem since, if we look at our output above, we have two elements with the same key: `artist`. with `array_filter`, those keys would all get clobbered and we would wind up with only one value: the last one. not good.

the most direct approach is to simply filter in our `foreach` loop.

```php
$rai = new RecursiveArrayIterator($albums);

$rii = new RecursiveIteratorIterator($rai);

$artists = [];
foreach($rii as $k => $v) {
    if($k == "artist") {
        $artists[] = $v;
    }
}

print_r($artists);
```

here, we loop over our `RecursiveIteratorIterator` and if the key is `artist` we add it to our `$artists` array. the result is an array of artist names. perfect.

or we could use `iterator_apply`.

`iterator_apply` applies a function to each element in an iterator. in this sense is kind of like `array_map`. let's look at how we would get our artists using it:

```php
$rai = new RecursiveArrayIterator($albums);

$rii = new RecursiveIteratorIterator($rai);

// our filtering function to extract only 'artists'
$filter = fn($n) => $n == 'artist';

$artists = [];
iterator_apply($rii,
    function($n, $filter, &amp;$artists) {

        // test the key with the filter
        if($filter($n->key())) {
            $artists[] = $n->current();
        }

        return true;
    },
    [$rii, $filter, &amp;$artists]);

print_r($artists);
```

looking at `iterator_apply`, we see it takes three arguments. the first argument is our iterator; very straightforward.

the second a third arguments define the function we want to apply to each iterator element. argument two is the function itself, a callable. the third argument is an array representing all the arguments that we are passing to that function. if the function we defined in argument two takes five arguments, the array here needs to have five elements. the first argument of our function and, correspondingly, the first element of our array, should always be the iterator itself.

in the example above, the function we're passing to iterator_apply takes three arguments: the iterator, a callable we're using to filter the elements in the iterator, and an accumulator called `$artists`. we're passing `$artists` by reference so we can modify it in the function body and have the results available to us after execution is done.

in the body of the function, we get the key of the current element of the iterator by calling the `key()` method and pass it to our `$filter`, our callable that determines if that key is `artists`. if `$filter` returns true, we get the value of the current element of the iterator by calling the `current()` and add it to our accumulator `$artists`.

in all honesty, this approach is neither easy nor obvious and, as a result, most people just use `foreach` loops. but `iterator_apply` is quite powerful, especially if we have a complex or pre-existing function that we would like to apply. it's worthwhile knowing it exists, even if we have to re-read the manual every time we use it.

> 🔎  this post was originally written in the [grant horwood technical blog](https://gbh.fruitbat.io/2024/06/04/php-doing-recursion-with-recursive-iteratoriterators/)