inf-bc-w15-python.md

Python 15: Higher Order & Recursive Functions.

Introduction: This document presents learning steps for Python 15. In Python 15, you will learn and practice higher order & recursive functions in Python. Recursive functions are the functions that call themselves. In majority of cases, you may implement a solution, non-recursively. There are cases that the definition is naturally recursive. In these cases, recursive functions can be easier to implement.

Note: In this phase, it is expected the learner can plan and run required learning process towards the goals of the week: making solutions to the given problems and product(s).

Materials:

The activities are designed based on these following references:

• BRef-01: Book, Bill Lubanovic; "Introducing Python: Modern Computing in Simple Packages"; Available here

• Free research.

Path:

Step: Functions Are First-Class Citizens.

Goals:

After taking this step, you will be able to:
	1. understand programs using: functions as parameters, generators and decorators.
	2. understand recursive functions.

What to learn?

Note: If this is the first time that you try recursion, it is very cruccial to start with small steps, small examples, seeing more samples and trying yourself. It will take time to feel confident in writing a solution recursively. Be patient.

1. Using BRef-01, Chapter 9 (Section: Recursion) make a plan for the week to learn basics of recursive functions in Python.
   • Read proposed book chapter and practice basic steps.
   • Make an overview of the provided problems and final product.
   • Plan what you need to learn in order to provide your solutions.
   • Read proposed book chapter and practice basic provided examples.
   • Read this resource and run provided examples.
   • Watch this video.

---

Exercises Higher Order Function:

1. Functions can be assigned to different variables. Read the code given below and write down the result of the program:

def f(x):
    return x*x
double = f
print(double(3) , f(5))

2. Functions can be collected within a structure. Read the code given below and write down the result of the program:

def f(x):
    return x**2

def g(x):
    return x**3
funcs = [f, g]
#accessing elements of the list separately
print(funcs[0](10), funcs[1](10))
# iterating over functions
for i in funcs:
    print(i(5))

3. Functions as arguments to functions. Read the code given below and write down the result of the program:

names = ['Ann','Benjamin','Alexander','Michael']
print(sorted(names)) # what will be printed here? Why?
print(sorted(names,key=len)) # what will be printed here? Why?
print(sorted(names,key=lambda x: x[1] if type(x) is str and len(x)>2 else None)) # what will be printed here? Why?

3. Generators. Read the code given below. Function power_n_range is implementing a generator. It will generate a sequence of x to the power of n where x is between first and last. Using a for-loop, iterate over the elements generated by power_n_range with different values for parameters.

def power_n_range(first=0,last=1,n=1):
    for x in range(first,last):
        yield x**n
# complete the code here

4. Decorators. Someone has implemented the following division function. If we test the functions carefully, we will realize that there will be an error if b==0 (why?), for example: division(10,0). Of course one solution is to change the implementation of the function. Another solution would be to decorate the currently existing one with a new feature that checks if it is not division by zero.

def division(a,b):
    return a/b

Complete the following template such that it decorates our division function with a check.

def division_fixed(func):
	def check_params(a,b):
		#todo: complete the code here
		pass

	return check_params


@division_fixed
def division(a,b):
    return a/b

print(division(10,2))
print(division(10,0)) # This must not raise an error

---

Exercises Recursive Function:

1. Play Tower of Hanoi.
2. From elementary school we know $5^3=5 \times 5 \times 5$. But, we can also define it recursively: $5^3 = 5 \times 5^2$. Or in general we can define the concept of $m^n$ recursively: $m^n=m \times m^{(n-1)}$. Check the implementation below. Try the code. There is something missing which makes it incorrect. Fix the implementation.

    def rec_power(m:int,n:int)->int:
        '''
        The function implements m to the power of n, recursively.
        '''
        return m*rec_power(m,n-1)

---