#!/usr/bin/env perl
use utf8;
###############################################################################
# This program computes Fibonacci Numbers using recursion and memoization.
# 
# Copyright © 2021 Richard Lesh.  All rights reserved.
###############################################################################

use Utils;
use strict;
use warnings;

our $CACHED_FIBONACCI = [1, 1];

sub fibonacci {
    my ($n) = @_;
    if ($n < 2) {
        return 1;
    }
    if ($n < scalar(@{$CACHED_FIBONACCI})) {
        return $CACHED_FIBONACCI->[$n];
    }
    my $RESULT = fibonacci($n - 1) + fibonacci($n - 2);
    push(@{$CACHED_FIBONACCI}, $RESULT);
    return $RESULT;
}

MAIN:
{
    print "Fibonacci Sequence\n";
    for (my $n = 1; $n <= 80; ++$n) {
        print Utils::messageFormat("\{0:d\}: \{1:d\}", $n, fibonacci($n)), "\n";
    }
}