FUNCTIONS Algorithms and Data Structures

Luis F. Teixeira
TOPICS OF INTRODUCTION Python Language
TO PROGRAMMING ­ Variables
­ Operators
­ Structured programming
­ Sequence
­ Selection (if-else)
­ Repetition (while, for)
­ Data structures
­ Functions
­ Classes
­ Inheritance
­ Polymorphism

2
 Functions form a fundamental part in the
FUNCTIONS construction of programs in Python
language (classes are the other
fundamental part).

Functions are usually conceived in the

context of a program, but they should
potentially be shared by different
programs.

Each function should perform a small and

well-defined task.

The function is an abstraction: it is not

necessary to know how it is implemented
to be used.

3
FUNCTIONS
def add(x,y):
return x + y

add(3,4)

¨ Colon (:) indicates start of a block

¨ Following lines are indented
¨ Function declaration does not specify return type, but
all functions return a value (None if not specified)
¨ Parameter types are not specified either
4
FUNCTIONS | STYLE
Blocks are denoted by indentation
­ problems may appear with spaces vs. tabs
­ spaces are usually preferable

Variable and function names are usually lower_case with underscores

separating words
Use comments adequately
­ Single line comments are denoted with # ...
­ Multi-line comments are denoted with """ ... """

Use docstrings to document what a function does:

def add(x,y):
"""Adds two numbers """
return x + y
5
 6

FUNCTIONS | CALL

def sqr(x):
a 1.2 return x * x
b 1.44
...
a = float(input("Write a number "))
b = sqr (a)
b=sqr(a)
print("The square of", a, "is", b)
...
x 1.2
The function receives variables with values, works with copies
return x*x of the variables (some caution is needed with references!), and
returns another value

6
 7

FUNCTIONS | CALL
def sqr(x):
aux = x * x
return aux

a = float(input("Write a number "))

aux = sqr(a)
print("The square of", a, "is", b)

Now with two auxiliary

variables aux
Although they have the
same name, they are
different
7
 8

FUNCTIONS | CALL
import math The argument can be an
expression
def sqr(x):
return x * x The function can receive the
result of another call to itself
a = float(input("Write a number "))
b = float(input("Write a number "))

print("The square of a+b is”, sqr (a + b))

print("The eighth power of a+b is”, sqr (sqr (sqr (a + b))))
print("The absolute value of a+b is”, math.sqrt (sqr (a + b)))

Write a number 2
Write a number 3
The square of a+b is 25.0
The eighth power of a+b is 390625.0
The absolute value of a+b is 5.0
8
 9

FUNCTIONS | SCOPE
def power (base, n): Variables created in a
i, p = 0, 1
while i < n: function are not accessible
p = p * base outside the function; they
i = i + 1
return p are created when the
function is called and are
i=0;
while i < 10: eliminated when the
print(i, power(2, i)) function ends.
i = i + 1

9
FUNCTIONS | SCOPE
>>> def foo(x):
... print(x)
... x=3
... print(x)
...
>>> x = 5
>>> foo(x)
5
3
>>> x
5

10
FUNCTIONS | SCOPE
>>> x = 5
>>> def foo():
... y=x+1
... x=0
... return y
...
>>> foo()
UnboundLocalError: local variable 'x' referenced before assignment

If a variable is assigned to in a block, then all uses of the variable in

the block refer to that assignment
But we attempted to use the variable “x” before it was assigned to
If we want to use the global variable, we need to specify global x
11
FUNCTIONS | ARGUMENTS
Function arguments can (1) have default values, and (2) be specified in
any order by using named arguments.
def func(val, first=5, last=7):
return first * val + last

­ “val” is a positional argument

­ “first” and “last” are keyword arguments
­ We can mix positional and keyword arguments, but keyword arguments must come last

12
FUNCTIONS | ARGUMENTS
def func(val, first=5, last=7):
return first * val + last

>>> func(2)
17
>>> func(2, first=1, last=1)
3
>>> func(2, 1, 1)
3
>>> func(2, last=5)
15
>>> func(first=7, 1)
SyntaxError: non-keyword arg after keyword arg

13
 math
MODULES sqrt
log A module is a file containing Python
cos definitions and statements

…
os
Definitions from a module can be
chdir
open
imported into other modules or into
read
the main module

…
The file name is the module name
myfunc1
mymodule with the suffix .py appended
myfunc2
myfunc3

14
MODULES
def myfunc1():
print("Hello from myfunc1")
mymodule.py
def myfunc2(a,b):
return a+b

import mymodule

mymodule.myfunc1 () main.py
print(mymodule.myfunc2 (5,7))

15
RANDOM NUMBERS
¨ The module random includes some functions to generate
pseudo-random numbers

>>> import random

>>> random.random() float between 0 and 1

0.41872335193283494
>>> random.randint(10, 20) int between 10 and 20

18

16
TYPICAL PYTHON FILE
A typical Python file (using only functions) has the structure below.

import module1
import module2

def function1(args1):
...

def function2(args2):
...

def main():
...

if __name__ == "__main__":
main()
17
SPECIAL ATTRIBUTES

Special attributes are used in Python to provide access to the

internal implementation
­ defined with two underscores before and after the name
In the previous example, __name__ evaluates to the name of
the current module
­ e.g. if your file is ex1.py, __name__ = "ex1"
But if your code is being run directly, via python ex1.py, then name =
"__main__"

18
FUNCTIONS | ITERATIVE VS. RECURSIVE

Create a function that calculates the factorial of a number.

Remember that: n! = n * n-1 * n-2 * … * 1

## iterative implementation
def factorial(x):
ans = 1
for i in range(2, x+1):
ans = ans * i
return ans

19
FUNCTIONS | RECURSION
Recursion is used when a function calls itself, either:
- directly (self-recursion; A calls A),
- indirectly, through the call of other functions
(mutual recursion; for example, A calls B and B calls A).

## recursive implementation
def factorial(x):
if x == 0:
return 1
else:
return x * factorial(x - 1)

20
FUNCTIONS | RECURSION
120
main() factorial(5)
24

factorial(4)
each factorial
6 function has its own
context
factorial(3)
2

factorial(2)
call
1
return
factorial(1)

21
FUNCTIONS | RECURSION
They must have the following characteristics:
the factorial of 1 is 1
1. A simple base case that has the solution and returns a
value (stopping condition). Sometimes, there is more
than one base case!
the factorial of n can
2. A way to bring the problem closer to the base case, be defined from the
i.e., a way to discard part of the problem to obtain a factorial of n-1
simpler problem.

3. A recursive call that passes a simpler problem to the

fatorial(n) =
same function. n*factorial(n-1)

22
FUNCTIONS | RECURSION
The key to thinking recursively is to find the solution to
the problem as a smaller version of the same problem:

Identify the base case(s) and what the base case(s) def factorial(n):
do(es). A base case is the simplest problem that the if n==1:
function can solve. Return the correct value for the
return 1
base case.
else
return n*factorial(n-1)
The recursive function will be reduced to an if-else
condition where the base case returns a value, and
the non-base case recursively calls the same function
with a smaller parameter or dataset.

23
TOWER OF HANOI
The goal is to build a program for this problem:
• three rods designated as L (left), M (middle), and R (right)
• on rod L, several disks of decreasing diameter are stacked
• the goal is to move the disks from L to R, such that, in each move of a disk, a larger
disk is never placed on top of a smaller one.

The ”Tower of Hanoi" problem has an intuitive recursive solution. On the other hand, it
is a problem that does not have an easy iterative solution.

L M R

24
TOWER OF HANOI
The solution can be decomposed in 3 parts
L M R

move N disks LàR

L M R L M R L M R

move N-1 disks LàM move 1 disk LàR move N-1 disks MàR

recursion 25
TOWER OF HANOI | PYTHON IMPLEMENTATION
# Move 1 disk from the initial rod (ini) to the final rod (fin)
def move_one(ini, fin):
rods = ["left", "middle", "right"]
print(f"Move disk from rod {rods[ini]} to rod {rods[fin]}")

# Recursive solution for the Tower of Hanoi for k disks with

# initial (ini) and final (fin) rods, using auxiliary rod (aux)
def move(k, ini, fin, aux):
if k > 1:
move(k - 1, ini, aux, fin) # Move k-1 disks from ini to aux
move_one(ini, fin) # Move the remaining disk from ini to fin
move(k - 1, aux, fin, ini) # Move k-1 disks from aux to fin
else:
move_one(ini, fin) # Base case: move 1 disk directly

# Main function
if __name__ == "__main__":
n = int(input("How many disks? "))
move(n, 0, 2, 1)
26