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

## Question:

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)

**Related Book For**

## Introduction to Algorithms

ISBN: 978-0262033848

3rd edition

Authors: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest

**Posted Date:**