This function is passed a number and returns(number)! = (number)(number-1)(number-2)...(3)(2)(1). By definition, 0! = 1

Only a recursive solution will be accepted!

def factorial(number)

function 2:

Write the RECURSIVE function linear_search. linear_search() is passed a list of values and a key. If a matching key is found in the list, the function returns index of where the key was found. If the key is not found, the function returns -1.

NOTE: you are not allowed to use any of the built-in list functions for this problem. The only function you are allowed to use is len()

def linear_search(list, key)

HINT: you may need to write the actual recursive function with a different set of arguments to accomplish this task.

function 3:

Write the RECURIVE function binary_search. binary_search() is passed a sorted list of values and a key. If a matching key is found in the list, the function returns an index of where the key was found. If the key is not found, the function returns -1.

NOTE: you are not allowed to use any of the built in list functions for this problem. The only function you are allowed to use is len()

def binary_search(list, key)

HINT: you may need to write the actual recursive function with a different set of arguments to accomplish this task.

Part B Analysis

Perform an analysis of the following recursive functions.

function 1:

Analyze the following function with respect to number

def function1(value, number):
if (number == 0):
 return 1
elif (number == 1):
 return value
else:
 return value * function1(value, number-1)

function 2:

Analyze function2 with respect to the length of the mystring. Hint, you will need to set up two mathematical functions for operator counting. one for function2 and the other for recursive_function2

def recursive_function2(mystring,a, b):
if(a >= b ):
 return True
else:
 if(mystring[a] != mystring[b]):
  return False
 else:
  return recursive_function2(mystring,a+1,b-1)

def function2(mystring):
return recursive_function2(mystring, 0,len(mystring)-1)
 

function 3 (optional challenge):

Analyze the following function with respect to number

def function3(value, number):
if (number == 0):
 return 1
elif (number == 1):
 return value
else:
 half = number // 2
 result = function3(value, half)
 if (number % 2 == 0):
  return result * result
 else:
  return value * result * result
 

Part C Reflection

Describe how to a approach writing recursive functions, what steps do you take?

Describe the process of analyzing recursive functions. How does it differ from from analyzing non-recursive functions? How is it the same?

test_lab3.py

import unittest
from lab3 import factorial,linear_search,binary_search

class Lab1TestCase(unittest.TestCase):
   """These are the test cases for functions and classes of lab3"""
   
   def test_linear_search(self):
       mylist = [34, 1, 18, 20, 25, 30, 15, 16, 17, 22, 24, 31, 163, 9, 33, 55]
       self.assertEqual(linear_search(mylist,0), -1)
       self.assertEqual(linear_search(mylist,19), -1)
       self.assertEqual(linear_search(mylist,164), -1)
       curr = 0
       for i in mylist:
           self.assertEqual(linear_search(mylist,i),curr)
           curr+=1

   def test_factorial(self):
       self.assertEqual(factorial(0),1)
       self.assertEqual(factorial(1),1)
       self.assertEqual(factorial(19),121645100408832000)
       self.assertEqual(factorial(8),40320)

   def test_binary_search(self):
       mylist = [1, 2, 4, 5, 8, 10, 15, 22, 27, 29, 30, 33, 55, 81, 100, 108, 200, 205, 310, 315]
       self.assertEqual(binary_search(mylist,0),-1)
       self.assertEqual(binary_search(mylist,19),-1)
       self.assertEqual(binary_search(mylist,201),-1)
       self.assertEqual(binary_search(mylist,320),-1)
       curr = 0
       for i in mylist:
           self.assertEqual(binary_search(mylist,i),curr)
           curr+=1

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

lab3.py

def factorial(number):
return 0

def linear_search(list, key):
   return 0

def binary_search(list, key):
return 0

Objectives:

• learn to write recursive functions
• learn to analyze recursive functions

Setup

All files needed for this lab were created by doing the first task in lab 0. If you didn't do lab 0, do the first task to create  lab repository.

• All code is to be written in lab3.py
• All answers to non-coding questions and analysis is to be written in lab3.md

Resources

You may find the following parts of the notes useful:

• How to do  analysis in 5 steps
• How to do  recursive analysis

Part A Recursive functions

• Write the following Python functions recursively.
• A non-recursive solution that works will not be given credit (even if it passes testing)

Answer rating: 100% (QA)

ANSWER Part A Recursive Functions Function 1 Factorial Calculation def factorialnumber if number 0 return 1 else return number factorialnumber 1 Funct... View the full answer