Recursion Problem

[swan2925]

sub fibonacci {
$arg = $_[0];

if ($arg < 2) {
return $arg;
}
else {
return(fibonacci($arg - 1) + fibonacci($arg - 2));
}
}

$input = <STDIN>;
print fibonacci($input);

------------------------------------------------------------

My little recursion script runs without stop..!!
I don't know what is going wrong, who can kindly teach me?

But when I replace the fibonacci subroutine with:
sub fibonacci {$_ [0] < 2 ? $_ [0] : fibo ($_ [0] - 1) + fibo ($_ [0] - 2)}

it works just fine!!

What are the differences between them?!

Thanks!!

 

[mikevh]

Your subroutine didn't run without stop when I tried it. However, it did return incorrect results. (I'm using ActiveState Perl v5.8.0 on Win XP.) The following fixed the problem.

#!perl
use strict;
use warnings;

sub fibonacci {
    [b]my $arg = shift;[/b]

    if ($arg < 2) {
        return $arg;
    } else {
        return fibonacci($arg - 1) + fibonacci($arg - 2);
    }
}
my $input = <STDIN>;
[b]chomp($input);[/b]
print fibonacci($input);

The chomp removes the line termination character(s) from $input.

It's good practice to always put use strict near the top of scripts and declare all variables with my.

The preferred method of "unpacking" arguments to a subroutine is my ($arg1, $arg2, ... $argn) = @_; when passing multiple arguments, my $arg = shift; for a single argument.

I'm not sure why I got the incorrect results I did when I tried the original version of your script, nor why it ran forever for you (but not me). However, I believe the above changes will solve your problem.

Perhaps someone else can shed some light on why the original version of the script did not work?

Suggested reading:
perldoc -f my
perldoc -f chomp
perldoc perlsub

HTH

 

[icrf]

Not sure why it'd run forever, but the incorrect results is likely due to $arg not being local. As a global variable, the nifty call stack of arguments that recursive functions depend on gets botched, as each new call overwrites the single global $arg that all instances see. So it probably never ran [tt]fibonacci($arg - 2)[/tt] correctly each time through, as $arg was always reset to something else when [tt]fibonacci($arg - 1)[/tt] was run right before it.

Note, I didn't actually test the code, but such makes sense in my head.

________________________________________
Andrew

I work for a gift card company!