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):
    # TODO: implement the factorial function iteratively here
    # transform the pseudocode hints below into working code
    ...
    # check if n is negative or not an integer (invalid input)
    # start with 1, the empty product
    # multiply result by each integer from 1 through n
    ...
    # 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"""
    # 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):
    # TODO: implement the fibonacci function iteratively here
    # transform the pseudocode hints below into working code
    ...
    # check if n is negative or not an integer (invalid input)
    # start with the first two values of the Fibonacci sequence
    # add the two previous values to generate the next Fibonacci value
    ...
    # once implemented, change fibonacci (above) to call fibonacci_iterative
    # to verify that your iterative implementation passes all tests below


def fibonacci_recursive(n):
    # TODO: implement the fibonacci function recursively here
    # transform the pseudocode hints below into working code
    ...
    # check if n is negative or not an integer (invalid input)
    # check if n is one of the base cases
    # check if n is an integer larger than the base cases
        # call function recursively with smaller values of n
    ...
    # once implemented, change fibonacci (above) to call fibonacci_recursive
    # to verify that your recursive implementation passes all tests below


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):
    # TODO: implement linear search recursively here
    # transform the pseudocode hints below into working code
    ...
    # check if the current search index is valid for array
    # check if item is in array at the current search index
    # otherwise search array recursively at the next index
    ...
    # once implemented, change linear_search to call linear_search_recursive
    # to verify that your recursive implementation passes all tests below


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):
    # TODO: implement binary search iteratively here
    # transform the pseudocode hints below into working code
    ...
    # start with search range from first to last valid array index
    # loop until array search range has zero width
        # middle index is the average of search range ends
        # check if item is the middle value of array
            # return middle index
        # check if item is less than the middle value of array
            # search left half of array by decreasing right end of search range
        # check if item is greater than the middle value of array
            # search right half of array by increasing left end of search range
    ...
    # once implemented, change binary_search to call binary_search_iterative
    # to verify that your iterative implementation passes all tests below


def binary_search_recursive(array, item, left=None, right=None):
    # TODO: implement binary search recursively here
    # transform the pseudocode hints below into working code
    ...
    # set arguments to default starting values
    # check if the given search range has zero width
    # middle index is the average of search range ends
    # check if item is the middle value of array
        # return middle index
    # check if item is less than the middle value of array
        # search left half of array recursively, decreasing right end of range
    # check if item is greater than the middle value of array
        # search right half of array recursively, increasing left end of range
    ...
    # once implemented, change binary_search to call binary_search_recursive
    # to verify that your recursive implementation passes all tests below


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


def is_palindrome(text):
    """a string of characters is a palindrome if it reads the same forwards and
    backwards, ignoring punctuation, whitespace, and letter casing"""
    # implement is_palindrome_iterative and is_palindrome_recursive below, then
    # change this to call your implementation to verify it passes all tests
    # return is_palindrome_iterative(text)
    return is_palindrome_recursive(text)


def is_palindrome_iterative(text):
    # TODO: implement the is_palindrome function iteratively here
    # transform the pseudocode hints below into working code
    ...
    # a string with zero or one characters is trivially a palindrome
    # start with left and right indexes from first to last valid array index
    # loop until left and right indexes have met in the middle or crossed
        # skip any letters not in ASCII character set
        # check if letters at left and right indexes match ignoring letter case
        # check next pair by increasing left index and decreasing right index
    # all letters have been checked and all have matched
    ...
    # once implemented, change is_palindrome to call is_palindrome_recursive
    # to verify that your recursive implementation passes all tests below


def is_palindrome_recursive(text, left=None, right=None):
    # TODO: implement the is_palindrome function recursively here
    # transform the pseudocode hints below into working code
    ...
    # base case: a string with zero or one characters is trivially a palindrome
    # set left and right indexes if no arguments were given
    # check if left and right indexes have met in the middle or crossed
    # advanced feature: skip any letters not in ASCII character set
    # check if letters at left and right indexes match, ignoring letter case
        # call recursively, moving left index forward and right index backward
    # letters did not match
    ...
    # once implemented, change is_palindrome to call is_palindrome_recursive
    # to verify that your recursive implementation passes all tests below


class TestRecursion(unittest.TestCase):
    def test_factorial_with_small_integers(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)

    def test_factorial_with_large_integers(self):
        self.assertEqual(factorial(15), 1307674368000)
        self.assertEqual(factorial(20), 2432902008176640000)
        self.assertEqual(factorial(25), 15511210043330985984000000)
        self.assertEqual(factorial(30), 265252859812191058636308480000000)

    def test_factorial_with_negative_integers(self):
        # factorial should raise a ValueError for n < 0
        with self.assertRaises(ValueError, msg='function undefined for n < 0'):
            factorial(-1)
            factorial(-5)

    def test_factorial_with_floating_point_numbers(self):
        # factorial should raise a ValueError for non-integer n
        with self.assertRaises(ValueError, msg='function undefined for float'):
            factorial(2.0)
            factorial(3.14159)

    def test_fibonacci_with_small_integers(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)

    def test_fibonacci_with_large_integers(self):
        # 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)
        # you may need to be patient for these...
        # self.assertEqual(fibonacci(35), 9227465)
        # self.assertEqual(fibonacci(40), 102334155)

    def test_fibonacci_with_negative_integers(self):
        # fibonacci should raise a ValueError for n < 0
        with self.assertRaises(ValueError, msg='function undefined for n < 0'):
            fibonacci(-1)
            fibonacci(-5)

    def test_fibonacci_with_floating_point_numbers(self):
        # fibonacci should raise a ValueError for non-integer n
        with self.assertRaises(ValueError, msg='function undefined for float'):
            fibonacci(2.0)
            fibonacci(3.14159)

    def test_linear_search_with_items_in_list(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)

    def test_linear_search_with_items_not_in_list(self):
        # linear search can find items regardless of list order
        names = ['Adrian', 'Josh', 'Ignat', 'Jacob', 'Kevin', 'Dan', 'Alan']
        # 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_with_items_in_list(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)

    def test_binary_search_with_items_not_in_list(self):
        # binary search requires list values to be in sorted order
        names = ['Adrian', 'Alan', 'Dan', 'Ignat', 'Jacob', 'Josh', 'Kevin']
        # binary search should return None for any item not in the list
        self.assertIsNone(binary_search(names, 'Jeremy'))
        self.assertIsNone(binary_search(names, 'nobody'))

    def test_is_palindrome_with_palindromes(self):
        # test basic palindromes
        self.assertTrue(is_palindrome(""))  # base case
        self.assertTrue(is_palindrome("A"))  # base case
        self.assertTrue(is_palindrome("BB"))
        self.assertTrue(is_palindrome("LOL"))
        self.assertTrue(is_palindrome("noon"))
        self.assertTrue(is_palindrome("radar"))
        # test palindromes with whitespace and punctuation
        self.assertTrue(is_palindrome("taco cat"))
        self.assertTrue(is_palindrome("race fast, safe car"))
        # test palindromes with whitespace, punctuation and mixed letter casing
        self.assertTrue(is_palindrome("Was it a car or a cat I saw?"))
        self.assertTrue(is_palindrome("Go hang a salami, I'm a lasagna hog."))
        self.assertTrue(is_palindrome("A man, a plan, a canal — Panama!"))

    def test_is_palindrome_with_non_palindromes(self):
        # test strings that are not palindromes
        self.assertFalse(is_palindrome("AB"))
        self.assertFalse(is_palindrome("ABC"))
        self.assertFalse(is_palindrome("doge"))
        self.assertFalse(is_palindrome("monkey"))
        self.assertFalse(is_palindrome("chicken, monkey!"))


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