Last active
March 31, 2016 00:44
-
-
Save neptunius/99c7be9d24a8c7df9fd6 to your computer and use it in GitHub Desktop.
Comparison of iterative and recursive functions
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment