''' CISC-121 2021F Section 001 - Assignment 4 Robin Dawes ''' # Part 1 # For each of the non-recursive functions given here, create # a recursive function that produces the same result # Example def product(x, y): ''' compute the product of x and y, where y is a positive integer ''' product = 0 while y >= 1: if (y % 2 == 1): product += x x *= 2 y //= 2 return product # ... can be replaced by this recursive function def product_rec(x,y): ''' compute the product of x and y, where y is a positive integer''' if y == 0: return 0 else: if (y % 2 == 1): return x + product_rec(x*2, y // 2) else: return product_rec(x*2, y // 2) # Problem 1: def exponent(x, y): # y is a positive integer ''' compute x^y, where y is a positive integer ''' result = x while y > 1: result = result*result if (y % 2 == 1): result *= x y = y // 2 return result # example of use print(exponent(3, 7)) #def exponent_rec(x, y): # you write this # Problem 2: def sublist_sum(a_list, target): ''' determine if list a_list has a consecutive sub-list that sums to target ''' for start in range(len(a_list)): sum = 0 for finish in range(start, len(a_list)): sum += a_list[finish] if sum == target: return True return False # example of use print(sublist_sum([4, 9, 3, 1, 7, 2, 4], 13)) # the result is True because of the consecutive sublist [9, 3, 1] #def sublist_sum_rec(a_list, target): # you write this # Problem 3: def prime_factors(n): ''' print the prime factorization of n''' while n > 1: candidate = 2 while candidate <= n: if n % candidate == 0: print(candidate, " ", end="") # this prints without starting a new line - very useful! n = n / candidate else: candidate += 1 print("\n") # example of use prime_factors(126) # def prime_factors_rec(n): # you write this # Problem 4: def matching_parentheses(a_string): ''' determine if string a_string contains properly matched parentheses (i.e. each right parenthesis is matched with an earlier left parenthesis) ''' left_parens = 0 right_parens = 0 for c in a_string: if c == '(': left_parens += 1 elif c == ')': right_parens += 1 if right_parens > left_parens: return False return (left_parens == right_parens) # example of use print(matching_parentheses("abc((ef)gh(ij()k)lm((()n)opq())rst)uvw(xyz)")) # def matching_parentheses_rec(a_string): # You write this # Part 2: # Each of these recursive functions is inefficient due to duplicated # effort. Improve them by storing the solutions to smaller problems that # are needed repeatedly. # Example: def fibonacci(n): '''compute the n-th number in the Fibonacci sequence''' if n <= 2: return 1 else: return fibonacci(n-1) + fibonacci(n-2) # This is extremely inefficient because computing fibonacci(n-1) # requires computing fibonacci(n-2), which we then compute again. And # each time we compute fibonacci(n-2), we compute both # fibonacci(n-3) and fibonacci(n-4), etc. # A much better solution is to create a list or dictionary # containing the fibonacci numbers we have already computed # so we can just look them up instead of recompute them. # To keep the interface as simple as possible, we hide the recursive # function - which now needs an extra parameter - behind a so-called # 'helper function' which sets things up and initiates the recursion def better_fibonacci(n): '''compute the n-th number in the Fibonacci sequence''' fibonacci_nums = [0, 1, 1] # the 0 is just a place-holder - I wanted to get the first Fibonacci number in position 1, etc. # to make the indexing easier to follow return better_fibonacci_rec(n, fibonacci_nums) def better_fibonacci_rec(n, fibonacci_nums): if n <= 2: return fibonacci_nums[n] elif len(fibonacci_nums) > n: return fibonacci_nums[n] # previously computed value else: fibonacci_nums.append(better_fibonacci_rec(n-1, fibonacci_nums) + better_fibonacci_rec(n-2, fibonacci_nums)) return fibonacci_nums[n] # newly computed value # Example of use: print(better_fibonacci(8)) # Problem 5 def collatz_up_to_n(n): ''' print the Collatz Sequence for each value from 1 to n ''' for i in range(n): collatz_rec(i+1) def collatz_rec(n): ''' print the Collatz Sequence for a single integer ''' print(n, " ", end="") if n == 1: print("\n") return else: if n % 2 == 0: n = n // 2 else: n = 3*n + 1 collatz_rec(n) # Example of use: collatz_up_to_n(10) # better_collatz_up_to_n(n): # you write this # Problem 6 def count_routes(n): ''' returns the number of different ways a robot can move forward a total of n metres, when the robot can only take steps that go forward either 2 metres or 3 metres. ''' if n <= 1: return 0 elif n <= 3: return 1 else: return count_routes(n-2) + count_routes(n-3) # Example of use: print(count_routes(7)) # better_count_routes(n) # You write this # Part 3 # Write non-recursive functions to produce the same results as these recursive functions # Example: look back at the example at the very top of this assignment ... but imagine I've # given you the recursive "product" function and asked you to write the non-recursive version. # Problem 7 def binary_search(a_list, target): ''' returns the location of target in a_list if target is in a_list, returns -1 if target is not in a_list a_list must be sorted prior to calling this function ''' return binary_search_rec(a_list, target, 0, len(a_list)-1) def binary_search_rec(a_list, target, first, last): if first > last: return -1 else: mid = (first + last) // 2 if a_list[mid] == target: return mid elif a_list[mid] > target: return binary_search_rec(a_list, target, first, mid-1) else: return binary_search_rec(a_list, target, mid+1, last) # Example of use print(binary_search([4, 7, 12, 15, 23, 28, 33, 34, 35, 100, 5280, 5281], 100)) # Problem 8 def gcd(a,b): ''' returns the greatest common divisor of a and b, which must be positive integers ''' if b == 0: return a else: return gcd(b, a % b) # Example of use print(gcd(8,20))