recursion.py

#!python

import unittest


def factorial(n):
    """factorial(n) returns the product of the integers 1 through n for n >= 0,
    otherwise raises ValueError for n < 0 or non-integer n"""
    # implement factorial_iterative and factorial_recursive below, then
    # change this to call your implementation to verify it passes all tests
    # return factorial_iterative(n)
    return factorial_iterative(n)


def factorial_iterative(n):
    # TODO: implement the factorial function iteratively here
    if n < 0 or not isinstance(n, int):
        raise ValueError('factorial is undefined for n = {}'.format(n))
    result = 1
    for i in range(n, 1, -1):
        result = result * i
    return result

    # once implemented, change factorial (above) to call factorial_iterative
    # to verify that your iterative implementation passes all tests below


def factorial_recursive(n):
    # check if n is negative or not an integer (invalid input)
    if n < 0 or not isinstance(n, int):
        raise ValueError('factorial is undefined for n = {}'.format(n))
    # check if n is one of the base cases
    elif n == 0 or n == 1:
        return 1
    # check if n is an integer larger than the base cases
    elif n > 1:
        # call function recursively
        return n * factorial_recursive(n - 1)


def fibonacci(n):
    """fibonacci(n) returns the n-th number in the Fibonacci sequence,
    which is defined with the recurrence relation:
    fibonacci(0) = 0
    fibonacci(1) = 1
    fibonacci(n) = fibonacci(n - 1) + fibonacci(n - 2), for n > 1"""
    # check if n is negative or not an integer (invalid input)
    if n < 0 or not isinstance(n, int):
        raise ValueError('fibonacci is undefined for n = {}'.format(n))
    # implement fibonacci_recursive, _memoized, and _dynamic below, then
    # change this to call your implementation to verify it passes all tests
    return fibonacci_dynamic(n)
    # return fibonacci_memoized(n)
    # return fibonacci_dynamic(n)


def fibonacci_recursive(n):
    # check if n is one of the base cases
    if n == 0 or n == 1:
        return n
    # check if n is an integer larger than the base cases
    elif n > 1:
        # call function recursively
        return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)

cache_me_outside = {}

def fibonacci_memoized(n):
    # TODO: memoize the fibonacci function's recursive implementation here

    if n < 2:
        return n
    elif n in cache_me_outside:
        return cache_me_outside[n]
    else:
        cache_me_outside[n] = fibonacci_memoized(n - 1) + fibonacci_memoized(n - 2)
        return cache_me_outside[n]
    # once implemented, change fibonacci (above) to call fibonacci_memoized
    # to verify that your memoized implementation passes all test cases

def fibonacci_dynamic(n):
    # TODO: implement the fibonacci function with dynamic programming here
    cache_me_outside[0] = 0
    cache_me_outside[1] = 1
    for i in range(2, n + 1):
        cache_me_outside[i] = cache_me_outside[i - 1] + cache_me_outside[i - 2]
    return cache_me_outside[n]
    # once implemented, change fibonacci (above) to call fibonacci_dynamic
    # to verify that your dynamic implementation passes all test cases


def main():
    import sys
    args = sys.argv[1:]  # Ignore script file name
    if len(args) == 1:
        num = int(args[0])
        # result = factorial(num)
        # print('factorial({}) => {}'.format(num, result))
        result = fibonacci(num)
        print('fibonacci({}) => {}'.format(num, result))
    else:
        print('Usage: {} number'.format(sys.argv[0]))


if __name__ == '__main__':
    main()