Chapter 4: Functions

Function = an abstract mechanism that hides details and allows us to view many things as just one thing ⇒ organises our codes more effectively

Eliminates redundant or repetitious code
E.g.

def sum(lower, upper):
result = 0
for number in range (lower, upper+1):
result += number
return result # returns sum of numbers between arguments [lower and upper bound] and including them
>>> sum(1,4)
10
>>> sum(50,100)
3825

Hides complicated details
A function call expresses the idea of a process to the programmer without forcing him/her to wade through the complex code that realises that idea
Functions support general methods with systemic variations
Algorithm = a general method for solving a class of problems
Problem instances = the individual problems that make up a class of problems
Algorithms should be general enough to provide a solution to many problem instances
Function should provide a general method with systemic variations
Functions support the division of labour
In a well-organised system, each part does its own job in collaborating to achieve a common goal
In a computer program, functions can enforce a division of labour
Each function should perform a single coherent task
Each of the tasks required by a system can be assigned to a function, including the tasks of managing or coordinating the use of other functions
Note: The function is infinitely recursive with the data value, if the call that decrements the argument is never reached. The function continues to print ___ until the system runs out of memory to support the recursion.
E.g.
def example(n):

if n > 0:
print (n)

example(n)

else:

example(n-1):
example(4)

Note: if print a function that has no return line, output will be ‘None’

Problem solving with top-down-design

Starts with a global view of the entire problem and breaks the problem into smaller, more manageable subproblems ⇒ problem decomposition
As each subproblem is isolated, its solution is assigned to a function
As functions are developed to solve subproblems, solution to overall problem is gradually filled out ⇒ stepwise refinement

Define simple functions

Syntax of simple function definitions
Function can be defined in a Python shell, but more convenient to define it in an IDLE window
Consists of header and body

def <function name>(<parameter-1>, …, <parameter-n>)):
<body>

E.g.
def square(X):         # note: define function – X here is parameter
return X*X
# To display docstring with info about what function does, enter help(square)
>>> square(2)         # call function – 2 here is argument

Parameters and arguments
Parameter = name used in function definition for an argument that is passed to the function when it is called
Arguments provide the function’s caller with the means of transmitting info to the function
Number and positions of arguments of a function call usually matches number and positions of the parameters in the definition
Some functions are defined with no parameters, expect no arguments
Can specify optional arguments with default values in any function definition:

def <function name>(<required argos>,
          <key-1> = <val-1>, … <key-n> = <val-n>)

Following the required arguments are 1 or more default or keyword arguments
When function is called with these arguments, default values are overridden by caller’s values
E.g.

def repToInt(repString, base): # convert repString to an int in the base and returns this int
decimal = 0
exponent = len(repString) - 1
for digit in repString:
decimal = decimal + int(digit) * base  exponent
exponent -= 1
return decimal

def repToInt(repString, base = 2): # base = 2 is set as default for binary
>>> repToInt(“10”, 10)
10
>>> repToInt(“10”, 8) # override the default to here
9
>>> repToInt(“10”, 2) # base 2 by default, not necessary to write (“10”, 2)
2
Length is 2
First digit is 1
Exponent = 2-1 = 1
Decimal  = 0 + 1*2*1 = 2
Second digit is 2
Exponent = 1-1 = 0
Decimal = 2 + 0*2*0 = 2
⇒ output = 2

The default arguments that follow can be supplied in 2 ways:
By position
By keyword

def example(required, option1 = 2, option2 = 3):
print required, option1, option2
>>> example(1) # use all defaults
1 2 3
>>> example(1, 10) # override 1st default
1 10 3
>>> example(1, 10, 20) # override all defaults
1 10 20
>>> example(1, option2 = 20) # override 2nd default
1 2 20
>>> example(1, option2 = 20, option1 = 10) # note order
1 10 20

The return statement
Placed at each exit point of a function when function should explicitly return a value
return <expression>
If function contains no return statement, Python transfers control to caller after last statement in function’s body is executed ⇒ special value None is automatically returned

def star(x):
print(‘*’ * x)
star(5)
print(star(5))

# output of star(5)
*****
# output of print(star(5))
*****
None

def square(x):
print(x*x) # should change to return x*x
# no return function here, so output is None
total = 0
for i in range(1,11):
  total += square(i) # error here
print(total)

TypeError: unsupported operand type(s) for +=: 'int' and 'NoneType'

Functions with multiple return variables
E.g.

# calculate sum and average of no.s between arguments and including them
def calc(lower, upper):
total = 0
count = 0
for number in range(lower, upper+1):
total += number
count += 1
average = total / count
return (total, average)
>>> calc(1,10)
(55, 5.5)
>>> calc(10,50)
(1230, 30.0)

Boolean functions
Usually tests its argument for presence or absence of some properties
Returns True if property is present; False otherwise
E.g.

def odd(x):
if x % 2 == 1:
return True
else:
return False
>>> odd(5)
True
>>> odd(6)
False

Main function
main serves as entry point for a script
Usually expects no arguments and returns no value
Definition of main and other functions can appear in no particular order in the script, as long as main is called at end of script
Script can be run from IDLE, imported into the shell, or run from a terminal command prompt

def main():
number = float(input(“Enter a number: ”))
result = square(number)
print(“The square of”, number, “is”, result)
def square(x):
return x*x
main()

Recursive functions
A procedure which keeps calling itself until a solution is found
Successive values of its local variables are all preserved
Thus disadvantage: takes more memory space
In a recursive subprogram, the body of the subprogram contains a call to itself
Used when original task can be reduced to a simpler version of itself
After a number of successive reductions, the reduced problem will eventually be simple enough to be solved directly, and its solution will be used to piece together a solution to the original problem
E.g. n! = n * (n-1)! ⇒ finding n! can be reduced to the simpler task of finding (n-1)!

Recursive solution	Iterative solution
A procedure which keeps calling itself until a solution is found	A loop which converges to a problem
Successive values of its local variables are all preserved	Successive values of its local variables are overwritten
Requires more amount of memory: if the recursion continues too long, the stack of return addresses may become full (i.e. no available memory is left) & the program will crash	Memory needed does not grow with the size of the problem’s data set
Can simplify design of algorithms and codes (shorter codes than non-recursive solutions)	Achieves same result with more/longer code
Recursive solutions can be difficult to follow and to debug
NOT always more efficient / execute faster than iterative solutions !

3 basic properties of a recursive function
A recursive algorithm must have base case(s)
It must call itself recursively
It must change its state and move toward the base case
Defining a recursive function with terminal case
Whenever a subprogram/recursive call has been completed, control is returned to the point at which the subprogram/recursive was called
For successive recursive calls to not continue indefinitely, the body of a recursive subprogram should include at least one terminal case – a case that contains no further calls to the recursive subprogram
Terminal cases are similar to loop exit conditions
E.g.

def FACT(n):
if n == 1: # terminal case
return 1
else:
return n * FACT(n-1)
def main():
n = int(input(“enter a positive integer: ”))
print(n, “ factorial is ”, FACT(n))
main()
>>> enter a positive integer: 4
4 factorial is 24

4 calls to the recursive function FACT ⇒ FACT(4) calls FACT(3), which calls FACT(2), which calls FACT(1)
Call to FACT(1) is the first call that can be completed, then computer winds back up and assigns FACT the value 1, etc

Trace diagram: (C = call, R = Return)
![[../_assets/image122.png]]

E.g. of winding back up to finish all the unfinished calls

def JOB(n):
if n == 1: # terminal case
print(“n = 1 GO  BACK”)
else: # recursive step
print(n, “ hi”)
JOB (n-1)
print(n, “ bye”)
>>> JOB(4)
4 hi
3 hi
2 hi
n = 1 GO BACK
2 bye
3 bye
4 bye
# note: order follows what was defined in the function

¹
Unfinished part of each call is marked with *

Defining a recursive function with base case
Uses selection statement to examine base case to determine whether to stop or to continue with another recursive step
E.g.

# not a recursive function
def displayRange(lower, upper): # output numbers from lower to upper
while lower <= upper:
print(lower)
lower = lower + 1

# recursive call
def displayRange(lower, upper): # output numbers from lower to upper
while lower <= upper:
print(lower)
displayRange(lower + 1, upper)

Using recursive definitions to construct recursive functions
Recursive definition consists of equations that state what a value is for one or more base cases and one or more recursive cases
E.g. Fibonacci sequence 1 1 2 3 5 8 13…

# Fib(n) = 1, when n = 1 or n = 2
# Fib(n) = Fib(n-1) + Fib(n-2), for all n >2
def fib(n): # returns nth Fibonacci sequence
if n < 3:
return 1
else:
return fib(n-1) + fib(n-2)

Infinite recursion
When fail to specify base case or to reduce size of problem in a way that terminates the recursive process
Python Virtual Machine (PVM) eventually runs out of memory resources to manage the process
PVM reserves an area of memory for the call stack
For each call of a function, the PVM must allocate on the call stack a stack frame, containing:
Values of arguments
Return address for the particular function call
Space for function call’s return value
When a call returns, return address is used to locate the next instruction, and stack frame is deallocated
E.g. picture shows memory allocated when we call the function displayRange(1,3)

Comments from the Word document

Infinite recursion
When fail to specify base case or to reduce size of problem in a way that terminates the recursive process
Python Virtual Machine (PVM) eventually runs out of memory resources to manage the process
PVM reserves an area of memory for the call stack
For each call of a function, the PVM must allocate on the call stack a stack frame, containing:
Values of arguments
Return address for the particular function call
Space for function call’s return value
When a call returns, return address is used to locate the next instruction, and stack frame is deallocated
E.g. picture shows memory allocated when we call the function displayRange(1,3)

Comments from the Word document

Comment by ANDREA TAN KAI XUAN HCI: why no need write whats printed ↩

Quartz 5

Explorer

05 Chapter 4 - Functions

Chapter 4: Functions

Chapter 4: Functions

Comments from the Word document

Comments from the Word document

Graph View

Table of Contents

Backlinks

Quartz 5

Explorer

05 Chapter 4 - Functions

Chapter 4: Functions

Chapter 4: Functions

Comments from the Word document

Comments from the Word document

Footnotes

Graph View

Table of Contents

Backlinks