[OCLUG-devel] Perl and Recursion

[Christopher Smith]

James Colannino wrote:
>    $look_for_rpm = sub {
> 
>        #If it wasn't found and we've reached the end of directories we
> can search,
>        #we must return 0 to indicate our failure to find the package.
> 
>        if ($dirs2check_elements <= -1) {return 0;}
> 
>        while (files exist in $dirs2check[$dirs2check_elements]) {
> 
>            examine file;
> 
>            if match found, {
>                install older version of package;
>                return 1;
>            }
> 
>            else {
>                --$dirs2check_elements;
>                &$look_for_rpm();
>            }
>        }
>    };

Okay, the biggest problem I see with this code is that it isn't using a
return statement for all of it's exit points. Technically that can work
with Perl, but probably not the way you want it to.

So, just for clarity I'd do "return &$look_for_rpm();", but you still
have the case where you fall out of the while loop. I'm guessing you
want to return "0" for that case.

Generally with recursion you want to structure things as such:

sub recursiveFunction(arguments) {
    if (atEndOfRecursion) {
        return someAppropriateValue;
    } else {
        return recursiveFunction(someChange(arguments));
    }
}

The way to think of it is you can prove correctness of the code via
induction. For some end case you can prove the function returns the
correct value. Then for all other cases it returns the correct value as
long as some reduced form (i.e. n-1) of the recursive function returns
the correct value.

--Chris