How to increment depth variable in recursion? It keeps resetting

Question

I have a question like this:

Create a function that takes in a nested array and an element and returns the frequency of that element by nested level.

Example:

freqCount([1, 4, 4, [1, 1, [1, 2, 1, 1]]], 1) ➞ [[0, 1], [1, 2], [2,3]] // The array has one 1 at level 0, 2 1's at level 1, and 3 1's at level 2.

So I have to use recursion since we don't know how many levels there are. I am getting the right number of occurrences of the $el passed but not the right level of depth because $depth keeps getting reset on every new call of recurse();

Here is the basic code:

<?php

function freqCount($arr, $el) {

recurse($arr, $el);

}

function recurse($a, $e) {

   $counter = 0;
     $depth = 0;
    $result = [];

    foreach($a as $k => $v) {
        if(!is_array($v) && $v === $e) {
            $counter++;
            $result[$depth] = $counter;
        } elseif(is_array($v)) {
            $depth++;
            recurse($v, $e);
        } else {
            continue;
        }
    }

    echo "<pre>";
    print_r($result);

}

Outputs:

Array
(
    [0] => 3 // Should be [2] => 3
)

Array
(
    [0] => 2 // Should be [1] => 2
)

Array
(
    [0] => 1
)

Probably want static $depth = 0; also I think you'll need to decrement it somewhere also. — AbraCadaver
– AbraCadaver, Commented Nov 2, 2020 at 21:30
@AbraCadaver: Nice static does keep track of the depth, thanks! Why would I need to decrement it? Here's the question: edabit.com/challenge/F96gXX2c8BvKnYiZ8 — rec0nstr
– rec0nstr, Commented Nov 2, 2020 at 21:31

Patrick Kelly · Accepted Answer · 2020-11-02 21:35:07Z

2

Your depth variable is locally scoped to the function and gets set to 0 each time the function is called. You need to pass the depth variable down the recursion so that it increments properly. Something like:

<?php

function freqCount($arr, $el) {
$depth = 0;
recurse($arr, $el, $depth);

}

function recurse($a, $e, $depth) {

    $counter = 0;
    $result = [];
    
    foreach($a as $k => $v) {
        if(!is_array($v) && $v === $e) {
            $counter++;
            $result[$depth] = $counter;
        } elseif(is_array($v)) {
            $depth++;
            recurse($v, $e, $depth);
        } else {
            continue;
        }
    }

    echo "<pre>";
    print_r($result);

}

answered Nov 2, 2020 at 21:35

Patrick Kelly

3202 silver badges9 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Jeto · Accepted Answer · 2020-11-02 22:49:55Z

1

Here's a possible simplified, PHP 7.4 version of what you're looking for:

function freqCount(array $values, $searchValue): array
{
    $frequencies = computeFrequencies($values, $searchValue, 0);

    return array_map(
        static fn (int $depth) => [$depth, $frequencies[$depth]],
        array_keys($frequencies)
    );
}

function computeFrequencies(array $values, $searchValue, int $depth): array
{
    $frequencies = [$depth => 0];

    foreach ($values as $value) {
        if ($value === $searchValue) {
            $frequencies[$depth]++;
        } elseif (is_array($value)) {
            foreach (computeFrequencies($value, $searchValue, $depth + 1) as $deeperDepth => $frequency) {
                $frequencies[$deeperDepth] = ($frequencies[$deeperDepth] ?? 0) + $frequency;
            }
        }
    }

    return $frequencies;
}

Usage:

print_r(freqCount([1, 4, 4, [1, 1, [1, 2, 1, 1]]], 1));  // [[0, 1], [1, 2], [2, 3]]
print_r(freqCount([1, [2], 1, [[2]], 1, [[[2]]], 1, [[[[2]]]]], 2));  // [[0, 0], [1, 1], [2, 1], [3, 1], [4, 1]]

It basically splits the task into two functions:

computeFrequencies is the "private" recursive one, it takes a $depth parameter and returns a level => occurrences associative array,
freqCount simply calls it once with $depth = 0, lets it do its thing then transforms the result into the desired output.

Demo (PHP 7.4)

Demo (PHP 7.2+)

edited Nov 2, 2020 at 22:49

answered Nov 2, 2020 at 22:14

Jeto

15k2 gold badges39 silver badges50 bronze badges

10 Comments

rec0nstr Over a year ago

Excellent, thank you my friend. This was considered an "expert" question (highest difficulty) and I felt confused. Would you say this is difficult based on (I assume) coding for a living? I'm trying to improve and was hoping I could've figured it out :(

Jeto Over a year ago

@rec0nstr I didn't dig too deep into your code but it seems like you weren't that far off. Recursive functions are quite counter-intuitive when you're not used to them, so I wouldn't worry too much about it. It comes with habit.

rec0nstr Over a year ago

Thank you! Very clean, modern solution :)

rec0nstr Over a year ago

FYI: I receive error about :: when testing on the question site: "PHP Parse error: syntax error, unexpected 'fn' (T_STRING), expecting :: (T_PAAMAYIM_NEKUDOTAYIM)" -- I assume it's an earlier version of PHP?

rec0nstr Over a year ago

Thanks, I believe it's 7.3 -- So I think the arrow function is problematic.

|

Collectives™ on Stack Overflow

How to increment depth variable in recursion? It keeps resetting

2 Answers 2

Comments

10 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

10 Comments

Your Answer

Sign up or log in

Post as a guest

Related