How to simulate array_reverse() using a recursive user-defined function?

Question

I want to reverse the values in an indexed array using recursion. The output should be the same as array_reverse().

My code:

$array = [1,2,3,4,5,6,7];

function reverseString(&$s) {
    if(count($s) < 2){
        return;
    }
    $len = count($s);
    $temp = $s[0];
    $s[0] = $s[$len - 1];
    $s[$len - 1] = $temp;
    reverseString(array_slice($s, 1, $len - 2));
}

reverseString($array);
print_r($array);

returns:

Array (
    [0] => 7
    [1] => 2
    [2] => 3
    [3] => 4
    [4] => 5
    [5] => 6
    [6] => 1 )

array_slice() is a link of an array part, am I right?

Why aren't the inner elements being affected by my recursive swapping technique?

It should be `array_slice(...)`, not `$array_slice(...)`. It is a function, not a variable. — arkascha, Feb 07 '20 at 12:02
Not really clear what you are trying to ask here. But `$array_slice` should probably be `array_slice` to begin with, you do not want to use “variable functions” here. — 04FS, Feb 07 '20 at 12:02
PHP is really not optimised for this. Might be fun to consider how to code in a more functional programming style in PHP but please do not write this code in anything that people will use. — apokryfos, Feb 07 '20 at 12:49

score 5 · Accepted Answer · answered Feb 07 '20 at 12:16

A string and an array are two separate things. I cleared up your algorithm a bit:

<?php
$array = [1,2,3,4,5,6,7];

function reverseSequence(&$s) {
    $len = count($s);
    if($len < 2){
        return;
    }

    $rest = array_slice($s, 1, $len - 2);
    reverseSequence($rest);
    $s = array_merge([$s[$len - 1]], $rest, [$s[0]]);
}

reverseSequence($array);
print_r($array);

The output obviously is:

Array
(
    [0] => 7
    [1] => 6
    [2] => 5
    [3] => 4
    [4] => 3
    [5] => 2
    [6] => 1
)

mickmackusa · Answer 2 · 2020-02-08T10:07:12.277

If you have your error reporting switched on, you will see three of these Notices:

Notice: Only variables should be passed by reference...

This is because you are passing the output of array_slice() as the referenced parameter; to fix this you must declare `array_slice()'s output as a variable before passing it in.

The fact that you are seeing three Notices actually indicates that your recursive technique IS traverse as far as intended and doing the work, but the resultant element swapping is not being applied to the previous calls on $s -- IOW all of the subsequent recursive modifications are lost. (Demo)

@arkascha supplied the necessary fixes to your script about an hour before me, but I might write it slightly differently.

Code: (Demo)

function swapOutermost(&$a) {
    $size = count($a);
    if ($size > 1) {
        $innerElements = array_slice($a, 1, -1);
        swapOutermost($innerElements);
        $a = array_merge(
            [$a[$size - 1]],  // last is put first
            $innerElements,   // recursed reference in the middle
            [$a[0]]           // first is put last
        );
    }
}

count() only once per recursive call -- arkascha fixed this
no return is written
-1 as the 3rd parameter of array_slice() has the same effect as your $len - 2.

Here is a recursive technique that only uses iterated count() calls -- no slicing or merging because it is passing the entire original input array each time. Only the targeted indexes change during recursion. I am swapping based on index incrementation using Symmetric Array Destructuring (a tool available from PHP7.1 and up).

Code: (Demo)

function swapOutermost(&$a, $i = 0) {
    $last = count($a) - 1 - $i;
    if ($i < $last) {
        [$a[$i], $a[$last]] = [$a[$last], $a[$i]];
        swapOutermost($a, ++$i);
    }
}

swapOutermost($array);

...of course, since the count never changes, it would be more efficient to just pass it in once and reuse it.

function swapOutermost(&$a, $count, $i = 0) {
    $last = $count - 1 - $i;
    if ($i < $last) {
        [$a[$i], $a[$last]] = [$a[$last], $a[$i]];
        swapOutermost($a, $count, ++$i);
    }
}

swapOutermost($array, count($array));

Now, your original snippet uses modification by reference, but you don't explicitly demand this in your question requirements -- only that recursion must be used. If you might entertain a recursive function that returns the variable instead (because, say, you want to be able to nest this call inside of another function), then here is one way that passes an ever shorter array with each level of recursion (as your original did):

Code: (Demo)

function recursiveArrayReverse($a) {
    $size = count($a);
    if ($size < 2) {
        return $a;
    }
    return array_merge(
        [$a[$size - 1]],
        recursiveArrayReverse(
            array_slice($a, 1, -1)
        ),
        [$a[0]]
    );
}

$array = [1, 2, 3, 4, 5, 6, 7];
$array = recursiveArrayReverse($array);

How to simulate array_reverse() using a recursive user-defined function?

2 Answers2

Linked