Comparison of iterative and recursive functions

recursion.py

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_recursive(n)


def factorial_iterative(n):
    factorial = 1
    if n < 0 or not isinstance(n, int):
        raise ValueError('factorial is undefined for n = {}'.format(n))

    for i in range(1, n+1):
        factorial *= i

    return factorial


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'''
    # implement fibonacci_iterative and fibonacci_recursive below, then
    # change this to call your implementation to verify it passes all tests
    ...
    # return fibonacci_iterative(n)
    return fibonacci_recursive(n)


def fibonacci_iterative(n):
    if n < 0 or not isinstance(n, int):
        raise ValueError('function undefined for n = {}'.format(n))
    if n == 0 or n == 1:
        return n
    prev = 0
    prev_curr = 1
    for i in range(n-1):
        next_seq = prev + prev_curr
        prev = prev_curr
        prev_curr = next_seq

    return prev_curr

def fibonacci_recursive(n):
    if n < 0 or not isinstance(n, int):
        raise ValueError('function undefined for n = {}'.format(n))
    if n == 0 or n == 1:
        return n
    else:
        return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)


def linear_search(array, item):
    '''return the first index of item in array or None if item is not found'''
    # implement linear_search_iterative and linear_search_recursive below, then
    # change this to call your implementation to verify it passes all tests
    ...
    # return linear_search_iterative(array, item)
    return linear_search_recursive(array, item)


def linear_search_iterative(array, item):
    # loop over all array values until item is found
    for index, value in enumerate(array):
        if item == value:
            return index  # found
    return None  # not found


def linear_search_recursive(array, item, index=0):
    if index >= len(array):
        return None
    if array[index] == item:
        return index
    else:
        return linear_search_recursive(array, item, index+1)


def binary_search(array, item):
    '''return the index of item in sorted array or None if item is not found'''
    # implement binary_search_iterative and binary_search_recursive below, then
    # change this to call your implementation to verify it passes all tests
    ...
    # return binary_search_iterative(array, item)
    return binary_search_recursive(array, item)
    # return binary_search_from_class(array, item)


def binary_search_iterative(array, item):
    iMax = len(array)-1
    iMin = 0

    while iMin <= iMax:
        mid = iMin + ((iMax - iMin)//2)
        if array[mid] == item:
            return mid
        elif array[mid] < item:
            iMin = mid+1
        else:
            iMax = mid-1



def binary_search_recursive(array, item, left=None, right=None):
    if left is None:
        left = 0
        right = len(array)-1
    if left > right:
        return None
    mid = left + ((right - left)//2)
    if array[mid] == item:
        return mid
    elif array[mid] < item:
        return binary_search_recursive(array, item, mid+1, right)
    else:
        return binary_search_recursive(array, item, left, mid-1)


def binary_search_from_class(array, item):
    '''Kevin's description of binary search:
    1. start in the middle of array
    2. check if item is the middle value
        return middle index
    3. if not, check if item is less than the middle value
        binary search the lower half of array (values left of the middle)
    4. if not, check if item is greater than the middle value
        binary search the upper half of array (values right of the middle)'''
    # check if array is empty
    if len(array) == 0:
        return None
    # middle index is half the array length
    middle = len(array) // 2
    # check if item is the middle value of array
    if item == array[middle]:
        return middle
    # check if item is less than the middle value of array
    elif item < array[middle]:
        # search left half of array recursively
        left_half = array[0: middle]
        result = binary_search(left_half, item)
        # ensure None is propogated upwards if item was not found recursively
        return None if result is None else result
    # check if item is greater than the middle value of array
    elif item > array[middle]:
        # search right half of array recursively
        right_half = array[middle + 1: len(array)]
        result = binary_search(right_half, item)
        # ensure None is propogated upwards if item was not found recursively,
        # otherwise adjust the returned index due to slicing the array in half
        return None if result is None else result + middle + 1


class TestRecursion(unittest.TestCase):
    def test_factorial(self):
        # factorial should return the product n*(n-1)*...*2*1 for n >= 0
        self.assertEqual(factorial(0), 1)  # base case
        self.assertEqual(factorial(1), 1)  # base case
        self.assertEqual(factorial(2), 2*1)
        self.assertEqual(factorial(3), 3*2*1)
        self.assertEqual(factorial(4), 4*3*2*1)
        self.assertEqual(factorial(5), 5*4*3*2*1)
        self.assertEqual(factorial(6), 6*5*4*3*2*1)
        self.assertEqual(factorial(7), 7*6*5*4*3*2*1)
        self.assertEqual(factorial(8), 8*7*6*5*4*3*2*1)
        self.assertEqual(factorial(9), 9*8*7*6*5*4*3*2*1)
        self.assertEqual(factorial(10), 10*9*8*7*6*5*4*3*2*1)
        # factorial should raise a ValueError for n < 0
        with self.assertRaises(ValueError, msg='function undefined for n < 0'):
            factorial(-1)
            factorial(-5)
            factorial(-20)
        # factorial should raise a ValueError for non-integer n
        with self.assertRaises(ValueError, msg='function undefined for float'):
            factorial(3.14159)

    def test_fibonacci(self):
        # fibonacci should return fibonacci(n-1) + fibonacci(n-2) for n >= 0
        self.assertEqual(fibonacci(0), 0)  # base case
        self.assertEqual(fibonacci(1), 1)  # base case
        self.assertEqual(fibonacci(2), 1)
        self.assertEqual(fibonacci(3), 2)
        self.assertEqual(fibonacci(4), 3)
        self.assertEqual(fibonacci(5), 5)
        self.assertEqual(fibonacci(6), 8)
        self.assertEqual(fibonacci(7), 13)
        self.assertEqual(fibonacci(8), 21)
        self.assertEqual(fibonacci(9), 34)
        self.assertEqual(fibonacci(10), 55)
        # these could run for a long time...
        self.assertEqual(fibonacci(15), 610)
        self.assertEqual(fibonacci(20), 6765)
        self.assertEqual(fibonacci(25), 75025)
        # self.assertEqual(fibonacci(30), 832040)
        # self.assertEqual(fibonacci(35), 9227465)  # you'll need to be patient
        # fibonacci should raise a ValueError for n < 0
        with self.assertRaises(ValueError, msg='function undefined for n < 0'):
            fibonacci(-1)
            fibonacci(-5)
            fibonacci(-20)
        # fibonacci should raise a ValueError for non-integer n
        with self.assertRaises(ValueError, msg='function undefined for float'):
            fibonacci(3.14159)

    def test_linear_search(self):
        # linear search can find items regardless of list order
        names = ['Adrian', 'Josh', 'Ignat', 'Jacob', 'Kevin', 'Dan', 'Alan']
        # linear search should return the index of each item in the list
        self.assertEqual(linear_search(names, 'Adrian'), 0)
        self.assertEqual(linear_search(names, 'Josh'), 1)
        self.assertEqual(linear_search(names, 'Ignat'), 2)
        self.assertEqual(linear_search(names, 'Jacob'), 3)
        self.assertEqual(linear_search(names, 'Kevin'), 4)
        self.assertEqual(linear_search(names, 'Dan'), 5)
        self.assertEqual(linear_search(names, 'Alan'), 6)
        # linear search should return None for any item not in the list
        self.assertIsNone(linear_search(names, 'Jeremy'))
        self.assertIsNone(linear_search(names, 'nobody'))

    def test_binary_search(self):
        # binary search requires list values to be in sorted order
        names = ['Adrian', 'Alan', 'Dan', 'Ignat', 'Jacob', 'Josh', 'Kevin']
        # binary search should return the index of each item in the list
        self.assertEqual(binary_search(names, 'Adrian'), 0)
        self.assertEqual(binary_search(names, 'Alan'), 1)
        self.assertEqual(binary_search(names, 'Dan'), 2)
        self.assertEqual(binary_search(names, 'Ignat'), 3)
        self.assertEqual(binary_search(names, 'Jacob'), 4)
        self.assertEqual(binary_search(names, 'Josh'), 5)
        self.assertEqual(binary_search(names, 'Kevin'), 6)
        # binary search should return None for any item not in the list
        self.assertIsNone(binary_search(names, 'Jeremy'))
        self.assertIsNone(binary_search(names, 'nobody'))


if __name__ == '__main__':
    unittest.main()