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

import Utils

CACHED_FIBONACCI = [1, 1]

def fibonacci(n) :
    if (n < 2) :
        return 1
    if (n < len(CACHED_FIBONACCI)) :
        return CACHED_FIBONACCI[n]
    RESULT = fibonacci(n - 1) + fibonacci(n - 2)
    CACHED_FIBONACCI.append(RESULT)
    return RESULT

# Begin Main
print("Fibonacci Sequence")
for n in range(1, 80 + 1) :
    print("{0:d}: {1:d}".format(n, fibonacci(n)))