My Fibonacci sequence as a recursive function is a

问题:

The following function recurses infinitely and I don't see why. It enters the conditional statements but doesn't seem to be terminating with the return statement.

use strict;
use warnings;

print fibonacci(100);

sub fibonacci {

    my $number = shift;

    if ($number == 0) {
        print "return 0\n";
        return 0;
    }
    elsif ($number == 1) {
        print "return 1\n";
        return 1;
    }
    else {
        return fibonacci($number-1) + fibonacci($number-2);
    }
}

回答1:

Your loop does not recurse infinitely, it just takes way too long with an input of 100. Try a memoized version:

{ my @fib;
  sub fib {
    my $n = shift;
    return $fib[$n] if defined $fib[$n];
    return $fib[$n] = $n if $n < 2;
    $fib[$n] = fib($n-1) + fib($n-2);
  }
}

回答2:

You code can be made much more concise, and speeded up massively by memoizing it.

The Memoize module is by far the simplest and clearest way to memoize (cache the results of) a subroutine.

I suggest this version. It still warns about deep recursion but it produces a value that I presume is correct.

use strict;
use warnings;

use Memoize;
memoize('fibonacci');

print fibonacci(100);

sub fibonacci {
    my ($n) = @_;
    $n < 2 ? $n : fibonacci($n-1) + fibonacci($n-2);
}

output

Deep recursion on anonymous subroutine at E:\Perl\source\fib.pl line 11.
Deep recursion on anonymous subroutine at E:\Perl\source\fib.pl line 11.
3.54224848179262e+020

回答3:

Your recursive function call is not infinite. It's just going to take a long time.

One should beware recursive functions, as it's often better to code something using a loop if it can be designed as such.

In this case, your number of recursive calls to fibonacci are growing exponentially. You can test this out yourself very easily by simply adding up the lower level calls

• fibonacci(0) = 1 call
• fibonacci(1) = 1 call
• fibonacci(2) = 1 call + calls for fibonacci(1) + calls for fibonacci(0) → 3
• fibonacci(3) = 1 call + calls for fibonacci(2) + calls for fibonacci(1) → 5
• fibonacci(4) = 1 call + calls for fibonacci(3) + calls for fibonacci(2) → 9
• fibonacci(5) = 1 call + calls for fibonacci(4) + calls for fibonacci(3) → 15
• fibonacci(N) = 1 call + calls for fibonacci(N-1) + calls for fibonacci(N-2) → ?

As you can see there is a fibonacci like growth for the number of subroutine calls.

To determine the number of calls for fibonacci(100) we can simply create a quick perl one-liner:

$ perl -e '
    @c = (1, 1); 
    $c[$_] = 1 + $c[$_-1] + $c[$_-2] for (2..100);
    print $c[100]
  ' 
1.14629568802763e+21

At 1 trillion calls a second, that's still going to take more than 31 years to finish.

Fix using Memoize

One fix that has already been proposed is to use the core library Memoize

use Memoize;
memoize('fibonacci');

This module will wrap around your subroutine call and cache the calculation of values. This will therefore reduce your number of function calls from 1.14e21 to literally 101 calculations.

However, because you are recursing more than 100 times, you will get the following warning per perldiag

• Deep recursion on anonymous subroutine

• Deep recursion on subroutine "%s"

  (W recursion) This subroutine has called itself (directly or indirectly) 100 times more than it has returned. This probably indicates an infinite recursion, unless you're writing strange benchmark programs, in which case it indicates something else.

  This threshold can be changed from 100, by recompiling the perl binary, setting the C pre-processor macro PERL_SUB_DEPTH_WARN to the desired value.

Create a loop instead - avoid recursion

Your algorithm can be redesigned very easily from a top down approach to calculation to a bottom up approach.

This removes the need for recursion entirely and reduces the code to the following:

use strict;
use warnings;

print fibonacci(100), "\n";

sub fibonacci {
    my $number = shift;

    my @fib = ( 0, 1 );

    for ( $#fib + 1 .. $number ) {
        $fib[$_] = $fib[ $_ - 1 ] + $fib[ $_ - 2 ];
    }

    return $fib[$number];
}

Outputs:

3.54224848179262e+20

No warnings will be given.