Simplifying recursive function

Question

While wrapping my brains around recursion, I hope to with the below simple problem to better understand recursion itself, but also in the spirit of TIMTOWTDI to other or better ways to achieve my goal.

Problem is pretty simple, given an complex Perl data structure, $cds (that guarantees to start with HASH, hmm, does it make a diff ?), I wish to traverse $cds and remove single-level-arrays.

I started with the below, which worked fine...

sub reduce_1level
{
    my $cds = shift;

    if (ref $cds eq 'HASH')
    {
        foreach my $key (keys %$cds)
        {
            if (ref $cds->{$key} eq 'ARRAY')
            {
                if (@{$cds->{$key}} == 1)
                {
                    $cds->{$key} = $cds->{$key}[0];
                }
                else
                {
                    reduce_1level ($cds->{$key});
                }
            }
            elsif (ref $cds->{$key} eq 'HASH')
            {
                reduce_1level ($cds->{$key});
            }
        }
    }
    elsif (ref $cds eq 'ARRAY')
    {
        foreach (@$cds)
        {
            reduce_1level ($_) if ref;
        }
    }
}

... but I somehow felt the code could be simpler and shorter. After needling the stack on similar problems, I revised to:

sub reduce_1level
{
    my $cds = shift;

    if (ref $cds eq 'ARRAY')
    {
        foreach (@$cds)
        {
            reduce_1level ($_) if ref;
        }
    }
    elsif (ref $cds eq 'HASH')
    {
        foreach my $key (keys %$cds)
        {
            if (ref $cds->{$key} eq 'ARRAY' and @{$cds->{$key}} == 1)
            {
                $cds->{$key} = $cds->{$key}[0];
            }
            next unless ref $cds->{$key};
            reduce_1level ($cds->{$key});
        }
    }
}

I'm wondering what else or better way can be done to achieve indented goal?

"I'm wondering what else or better way can be done to achieve indented goal?" This seems a bit broad...what do you mean by "better"? Fewer lines of code? More readable? Better performance? Since it looks like you have working code that you want critiqued, this might be a better fit for http://codereview.stackexchange.com — ThisSuitIsBlackNot, Dec 07 '15 at 16:57
As you can see @ikegami found this code to be incorrect (though in my specific case, that `foo` thing will never be the case, but code should be correct!), so I was not even sure what I was looking for... hmm, If I can give more then two checks for @ikegami :) but I will take your note and next time, for strict code-review I'll address the proper hall — lzc, Dec 07 '15 at 18:27
To understand recursion, you must first understand recursion. — Sobrique, Dec 07 '15 at 18:27

ikegami · Accepted Answer · 2015-12-10T19:48:36.430

4

Forget complexity. It's not even correct.

Some calls handles two levels of the data structure, so you should have duplicated code. But you don't. As a result, not all the single-element arrays in the following are eliminated:

{ foo => [ [ 3 ] ] }

Don't try to handle two levels in the same call.

sub reduce_1level {
    our $cds; local *cds = \shift;   # alias $cds = shift;

    my $reftype = ref($cds)
        or return;

    if ($reftype eq 'HASH') {
        reduce_1level($_) for values %$cds;
    }
    elsif ($reftype eq 'ARRAY') {
        if (@$cds == 1) {
            $cds = $cds->[0];
            reduce_1level($cds);
        } else {
            reduce_1level($_) for @$cds;
        }
    }
    else {
        die("Unsupported reference type $reftype\n");
    }
}

edited Dec 10 '15 at 19:48

answered Dec 07 '15 at 17:45

ikegami

367,544
15
269
518

you got it! That's exactly what I was looking for, the code is simpler and easier to follow. Although, I wonder if/why your code would not work if with `my $cds = shift` ? Thanks – lzc Dec 07 '15 at 18:23
1

Because it's passing the current level of the hash back into itself. You need to do it that way because you're modifying the structure as you go. – Sobrique Dec 07 '15 at 18:27
1

Consider `my $x = [ 4 ]; reduce_1level($x);`. You need to modify `$x`. `$x` is known as `$_[0]` inside the sub (since Perl passes by reference). You could modify `$_[0]`, but I figured it would be nicer to modify `$cds` instead. That requires making `$cds` the same variable as `$_[0]` and `$x`. – ikegami Dec 07 '15 at 18:40
Thinking ... what would happen if `$reftype = 'CODE'` ? I don't have recursion that well under my belt **yet**, but I'm afraid there would be run-time error on `reduce_1level($_) for @$cds;` (or maybe _infinite_ recursion?), pls clarify. Also, would it not be more efficient to check for `if ref` before recursing with `reduce_1level` on `values %$cds` or `@$cds` – lzc Dec 07 '15 at 19:52
I just assumed that wasn't possible, but that's trivial to fix. – ikegami Dec 07 '15 at 20:00
Sure, you can tweak performance, but that's the opposite of what the OP asked. – ikegami Dec 07 '15 at 20:01
An infinite loop is possible if you have a cyclic structure. `my $x = { x => undef }; $x->{x} = $x;` – ikegami Dec 07 '15 at 20:05
1

I found [this](http://stackoverflow.com/a/2975250/3299282) very helpful explaining how `local` and the `alias` concept works – lzc Dec 10 '15 at 18:56

Simplifying recursive function

1 Answers1