[Israel.pm] What does this code do?

[Shlomi Fish]

On Wednesday 28 April 2004 15:57, Srikanth Madani wrote:

> > > General question - is recursion considered good programming practice?
>
> > I'd rather answer it to the list. Can I, or would you rather have a 
> > private answer?
>
> On list is even better!

Well, here goes. 

There are several types of recursion. One of them is tail-recursion. I'll 
exemplify it with the following Perl code that calculates the factorial: 

<<<
#!/usr/bin/perl -w

use strict;

sub fact_helper
{
    my ($n, $i, $prod) = @_;
    if ($i > $n)
    {
        return $prod;
    }
    else
    {
        return fact_helper($n, $i+1, $prod*$i);
    }
}

sub fact
{
    my $n = shift;
    return fact_helper($n, 1, 1);
}

my $n = shift;
print fact($n), "\n";
>>>

As you can see, fact_helper() returns either a constant or another unmodified 
call to itself with different arguments. Thus, what can be done is that the 
return statement would be a "goto" statement to the beginning of the function 
after modifying the arguments. Something like this:

<<<
sub fact_helper
{
    my ($n, $i, $prod) = @_;
fact_helper_start:
    if ($i > $n)
    {
        return $prod;
    }
    else
    {
        $prod *= $i;
        $i++;
        goto fact_helper_start;
    }
}
>>>

Some compilers or interpreters do this optimazation and it is called "proper 
tail recursion". Now, in some languages (like Scheme) this is the standard 
way to perform loops. 

Perl does not have proper-tail-recursion (at least not yet) and so this method 
results in a return flourish at the end, which makes it somewhat in-efficient 
speed-wise and time-wise. Instead this code can be implemented as:

<<<
sub fact
{
    my $n = shift;
    my $prod = 1;

    for(my $i=1;!($i>$n);$i++)
    {
        $prod *= $i;
    }
    return $prod;
}
>>>

Which is essentially the same as the version with the "goto" beforehand, just 
in a better style.

Another type of recursion is linear (non-tail) recursion. This can be 
exemplified in the following function for calculating the factorial function:

<<<
sub fact
{
    my $n = shift;
    if ($n == 0)
    {
        return 1;
    }
    else
    {
        return $n * fact($n-1);
    }
}
>>>

As you can see the type returned is an expression based on the result of 
another invocation of the function. Thus, even if we do have a proper tail 
recursion optimization, it won't help us. 

Finally, there's also tree recursion. This is what was demonstrated in the 
original ({0,1,2}**N) code example. This, and the two other kinds of 
recursion can be simulated without using procedure self-invocation by 
maintaining a stack of results and creating a loop that increments and 
decrements a pointer to the current place the calculation occurs.

You can see some discussion of these recursions, in Scheme, here:

http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html

Now, when to use recursion? Most of the tail-recursion and linear-recursion 
can be implemented as loops. Still, recursion is sometimes used to clearly 
illustrate the algorithm, make the code clearer, or calculate the complexity 
of the algorithm.

As for tree recursion, this can be implemented as procedural recursion for 
clarity. However if the depth is not known to be limited in advance, it is a 
good idea to implement it with a dedicated stack.

Perl will warn you if you have recursed a lot. (100 times if I remember 
correctly) if "use warnings" is specified. There would also be problems in 
debugging. A workaround can be found here:

http://vipe.technion.ac.il/~shlomif/lecture/LM-Solve/slides/exotic-bugs/recursion_limit.html

Regards,

	Shlomi Fish

-- 

---------------------------------------------------------------------
Shlomi Fish      shlomif at iglu.org.il
Homepage:        http://shlomif.il.eu.org/

Quidquid latine dictum sit, altum viditur.
        [Whatever is said in Latin sounds profound.]