My Fibonacci sequence as a recursive function is an infinite loop

Question

The following function is infinitely recursive, and I don't understand why. It is included in conditional statements, but does not seem to end with a statement return.

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);
    }
}

Answer 1

Your loop does not require infinite recursion, it is just too long with input 100. Try the 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);
  }
}

Answer 2

You can make the code more concise and speed up massively by saving it.

A module Memoizeis the easiest and clearest way to memoize (cache results) a routine.

. - , , , , .

use strict;
use warnings;

use Memoize;
memoize('fibonacci');

print fibonacci(100);

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

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

Answer 3

. .

, -, , .

fibonacci . ,

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

, , .

fibonacci(100), perl:

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

1 , 31 .

Memoize

, , - Memoize

use Memoize;
memoize('fibonacci');

. , 1.14e21 101 .

, 100 , perldiag

• "% s"

  (W recursion) ( ) 100 , . , , , , - .

  100 perl, C PERL_SUB_DEPTH_WARN .

-

.

:

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];
}

:

3.54224848179262e+20

.