6. Functions¶
Open the notebook in Colab

(C) Copyright Notice: This chapter is part of the book available athttps://pp4e-book.github.io/and copying, distributing, modifying it requires explicit permission from the authors. See the book page for details:https://pp4e-book.github.io/

A function (or sometimes synonymously referred to as subroutine, procedure or sub-program) is a grouping of actions under a given name that performs a specific task. len(), print(), abs(), type() are functions that we have seen before. Python adopts a syntax that resembles mathematical functions.

A function, i.e. ‘named’ pieces of code, can receive parameters. These parameters are variables that carry information from the “calling point” (e.g. when you write N = len("The number of chars")) to the callee, i.e. the piece of code that defined the function (len() in our example). The life span of these variables (parameters) is as long as the function is active (for that call).

6.1. Why define functions?¶

There are four main reasons for using functions while developing solutions with a programming language:

1- Reusability

A function is defined at a single point in a program but it can be called from several different points. Assume you need to calculate the run-length encoding of a string (the example code from the previous chapter) in your program for \(n\) different strings in different positions of your code. In a programming language without functions, you would have to copy-paste that code piece in \(n\) different places. Thanks to functions, we can place the code piece in a function once (named encodeRunLen for example) and use it in \(n\) places via simple function calls like enc = encodeRunLen(inpstr).

If functions would not be present, even if we would have the piece of code that does the actions of the function, how would we return to the different calling points after the actions are completed? Something, that is theoretically possible but extremely painful.

2- Maintenance

Using functions makes it easier to make updates to the algorithm. Let us explain this with the run-length encoding example: Assume that we found a bug in our calculation or we have discovered a better algorithm than the one we are using. Without functions, you would need to go through all your code, find the locations where your run-length encoding algorithm is implemented, and update each and every one of them. This is impractical and very tedious. With functions, it is sufficient if you just change the function that implements the run-length encoding.

3- Structuredness

Let us have a look at a perfectly valid Python expression:

(b if b<c else c) if (a if a<b else b)<(b if b<c else c) else (a if a<b else b)

which certainly takes some time to parse and understand but it just performs the following:

max(min(a,b), min(b,c))

Assume instead of the long expression above, the one with min and max are used. Even if the definition of max and min are not given yet, still one can grasp what the expression is up to. It is not only because the expression is smaller, but because function naming can depict the meaning for the actions.

4- Benefits of the functional programming paradigm

If a programmer sticks to the functional paradigm, then he or she has to plot a functional decomposition so that the solution of the problem is obtained by means of functional composition, something that is well-known and understood through Mathematics. This type of a solution does not suffer from unexpected side effects or variable alterations; therefore, testing and debugging are easier. Another benefit of the functional paradigm is recursion: In other words, while defining a function, we can call the function that is being defined – we will cover this seemingly confusing concept below. Moreover, we can define higher-order functions that take functions as input and apply them to a sequence of data. All these benefits come free with using functions, as we will illustrate below.

Even when we do not limit ourselves to ‘functional programming’, it is essential to use functions in professional programming. General algorithms that are coded as functions are becoming very valuable because they can be reused again and again in new programs. Collections formed by such general purpose functions are called libraries. For almost all application areas libraries have been created over decades.

6.2. Defining functions¶

For defining a function, Python adopts the following syntax:

def \(\boxed{\color{red}{FunctionName\strut}}\) (\(\boxed{\color{red}{Parameter_1\strut}}\) ,\(\boxed{\color{red}{Parameter_2\strut}}\) ,\(\color{red}{\large\cdots}\) ) :\(\boxed{\color{red}{Statement\strut\ }}\)

The \(\color{red}{Statement}\), which can be replaced by multiple statements like we did with other compound statements, can make use of the \(\color{red}{Parameter_i}\)s to obtain the actual arguments sent to the function at call-time. If the function is going to give a value in return to the call, this value is provided by a return statement.

\(\color{red}{FunctionName}\) is the name of the function being defined. Python follows the same naming rules and conventions used for naming variables – if you do not remember them, we recommend you to go back and check the restrictions for naming variables in Chapter 4.

Here is a straightforward example. Let us assume that we want to implement the following function:

(6.2.1)¶\[F_{gravity}(m_1,m_2,r) = G\frac{m_1 m_2}{r^2}.\]

The following is the one-line Python code that defines it:

def F_gravity(m_1, m_2, r): return G * m_1 * m_2 / (r * r)

This function, F_gravity, returns a value. This is provided by the return statement. As you may have observed, the values \(m_1\), \(m_2\) and \(r\) are provided as the first, the second and the third parameters, named as m_1, m_2 and r, respectively.

But what about G? It is not provided in the arguments and used in the return expression for its value. If the definition were a multi-statement definition (indented multi-statements following the def line), then Python would seek for a defined value for G among them. But this is not even the case, so the last alternative is to seek a value in the global environment, the environment in which F_gravity is called.

Therefore, before we call F_gravity, we must make sure that a value for a global variable G (which apparently is the Gravitational Constant) is set. In the Scope of Variables section, we will be handling the rules of this to a greater extent.

def F_gravity(m1, m2, r): return G * m1 * m2 / (r * r)

G = 6.67408E-11
print(F_gravity(1000, 20, 0.5), "Newton")

5.3392640000000006e-06 Newton

6.3. Passing parameters to functions¶

When a function is called, first its arguments are evaluated. The function will receive the results of these evaluations. The parameter variables used in the definition are created, and set to the result of the argument evaluations. Then the statement that follows the column (:) after the argument parenthesis is executed. Certainly this statement can and will make use of the parameter variables (which are set to the result of the argument evaluations).

Let us look at an example:

def F_gravity(m_1, m_2, r): return G * m_1 * m_2 / (r * r)

G = 6.67408E-11

S = 100
Q = 2000

print(F_gravity(Q+S, Q-S, ((504.3-66.1)**2+(351.1-7.7)**2)**0.5))

8.59177215925003e-10

This is a legitimate piece of code that performs the following in order:

Defines the function F_gravity.
Sets the value of the global variable G and S and Q
Calls the (internally defined) print function which receives one argument. This argument is a function call to F_gravity. So, in order to have a value to print, this function call has to be performed.
A call to F_gravity is prepared: It has three arguments, each has to be evaluated and boiled down to a value. So, in a left-to-right order the arguments are evaluated:
- Q+S is evaluated, and the result is stored into m_1.
- Q-S is evaluated, and the result is stored into m_2.
- Euclidean distance, \(\scriptstyle\mathtt{\sqrt{(504.3-66.1)^2+(351.1-7.7)^2}}\), is evaluated and the result is stored into r.
Since all arguments are evaluated, the statement defining the function F_gravity can be executed.
This statement is return G * m_1 * m_2 / (r * r), which requires the expression following the return keyword to be evaluated and the result to be returned as the result of the function call.
Now the print function has got its parameter evaluated. The defining action of the print function can be carried out (This is an internally defined function, i.e. we cannot see its definition, but the documents defining the language explain it).

The bottom line is: Before the function is called, there is a preparation phase where all arguments are evaluated and hence converted to a value. This has a name in computer science and is coined as Call-by-value.

6.3.1. Default Parameters¶

While defining a function, we can provide default values to parameters as follows:

def \(\boxed{\color{red}{FunctionName\strut}}\) (\(\boxed{\color{red}{Parameter_1\strut}=\color{red}{Exp_1}}\) ,\(\boxed{\color{red}{Parameter_2\strut}=\color{red}{Exp_2}}\) , \(\color{red}{\large\cdots}\) ) :\(\boxed{\color{red}{Statement\strut\ }}\)

where \(\color{red}{Exp_i}\) is an expression. When calling the function, we may omit providing the parameters for which the function has default values.

Let us have a look at a simple example:

def norm(x1, x2, norm_type="L1", verbose=True):
  result = None
  if norm_type == "L1": result = abs(x1) + abs(x2)
  elif norm_type == "L2": result = (x1**2 + x2**2)**0.5
  elif verbose: print("Norm not known:", norm_type)

  if verbose: print(f"The {norm_type} norm of", [x1, x2], "is:", result)
  return result

norm(3, 4)                                      # CASE 1
norm(3, 4, "L2")                                # CASE 2
norm(3, 4, norm_type="L2")                      # CASE 3
norm(3, 4, verbose=False)                       # CASE 4: Does not print the value
norm(3, 4, verbose=True, norm_type="L1")        # CASE 5
norm(x2=3, x1=4, verbose=True, norm_type="L1")  # CASE 6

The L1 norm of [3, 4] is: 7
The L2 norm of [3, 4] is: 5.0
The L2 norm of [3, 4] is: 5.0
The L1 norm of [3, 4] is: 7
The L1 norm of [4, 3] is: 7

# Let us look at some cases that lead to errors:
>>> norm(3, 4, norm_type="L1", True)                # CASE 7
File "<ipython-input-19-128dc3e43256>", line 2
    norm(3, 4, norm_type="L1", True)                # CASE 7
                              ^
SyntaxError: positional argument follows keyword argument

In this example, you should notice the following crucial points:

We can call a function without providing any value for the parameters that have default values (CASE 1, .., CASE 4).
We can swap the order of default parameters when we are calling the function (CASE 5 and CASE 6).
When calling a function, we can give values to non-default parameters by using their names (CASE 6).
The parameters after the default parameters need to be given names as well, both while defining the function and calling the function (CASE 7).

6.4. Scope of variables¶

We extensively use variables while programming our solutions. Not all variables are accessible from everywhere. There is a governing set of rules for that determine which parts of a code can access a variable. The code part from which a variable is accessible is called its scope.

In Python, there are four categories of scopes. As will be explained shortly, they are abbreviated with their initials , which then combine to form the rule mnemonic LEGB standing for:

[\(\color{red}{L}\)ocal \(<\) \(\color{red}{E}\)nclosing \(<\) \(\color{red}{G}\)lobal \(<\) \(\color{red}{B}\)uilt-in]

1- Local Scope

Defining a variable in a function in Python makes it local.

Local variables are the most ‘private’ ones. Any code which is external to that function cannot see it. If you make an assignment anywhere in the function to a variable, it is registered as a local variable. If you attempt to refer to such a local variable prior to the assignment, Python will generate a run-time error.

The local variables are created each time the function is called (it is activated) and are annihilated (destructed) the moment the function returns (finishes).

2- Enclosing Scope

As we mentioned before, it is possible to define functions inside functions. They are coined as local functions and can refer (but not change) to the values of the local variables of its parent function (the function in which the local function is defined). The scope of the outer function is the enclosing scope for the inner function. Though the parent function’s variables are visible to the local function, the converse is not true. The parent function cannot access its local function’s local variables. Therefore, the accessibility is from inward to outward and for referring purposes only.

3- Global Scope

If a variable is not defined in a function then it is a global variable. It can be accessed outside as well as inside of any function. If a global variable is accessed inside a function, it cannot be altered there. If it is altered anywhere in the function, this is recognised at the declaration-time and that variable is declared (created) as a local variable. A local variable that has the same name with a global variable conceals the global variable.

If you want to change the value of a global variable inside a function, then you have to explicitly declare it as a global variable by a statement:

global \(\boxed{\color{red}{V\!ariable\strut}}\)

Then an assignment to \(\color{red}{V\!ariable}\) will not register it as a local variable but merely refer to the global \(\color{red}{V\!ariable}\). As said, since the system will recognize them automatically, there is no need to use the global statement for global variables which are referred to for their values only. However, it is a good programming habit to do so in order to enhance readability and prevent accidental local variable creations (due to careless assignments to global variables).

4- Built-in Scope

Built-in scope is a special Python scope that is created or loaded whenever you run a script or open an interactive session. This is actually the scope in which the Python interpreter starts. It contains names such as keywords, built-in functions, exceptions, and some other attributes. Entities in this scope are also available from everywhere in your code.

An Interactive Example for Scope

Please follow the Colab link at the top of the page for an interactive demo on scope of variables.

A variable occurrence has different meanings for different positions in the program:

First time occurrence of the variable at the left-hand side of an assignment: This tells Python to declare a variable in the current scope, the current function or the global scope. If there is a variable with the same name in an outer scope, it is hidden as long as the new variable is active. This declaration will be active for the scope it is created in including statements preceding it.
Second and later occurrences of the variable at the left-hand side of an assignment: They simply update the previously declared variable.
Occurrences of the variable at the right-hand side of an assignment or any other place in an expression: Python places value (content) of the variable in the expression position. Variable is searched in all scopes from inner to outer (local, then enclosing, then global, then built-in) and the first found variable is used. If the declaration of the variable is after its reference in current scope, Python will raise the error 'Reference before assignment'.

Note that global declaration changes the behaviour above. It makes all occurrences to refer to the global variable and does not declare a variable in the current scope with the globally defined names.

6.5. Higher-order functions¶

Python provides several flavours of the functional paradigm, one of the most powerful of which is the ability to easily pass functions as parameters to other functions. No special syntax or rule is used for this: If you use a parameter as if it is a function and when calling the higher-order function, pass a function name as a parameter, Python will handle the rest.

Python provides two very practical higher-order functions for us:

map function: The map function has the following syntax:

map(function, Iterator)

which yields an iterator where each element is function being applied on the corresponding element in Iterator. Here is a simple example:
```
>>> abs_it = map(abs, [10, -4, 20, -100])
>>> for x in abs_it: print(x)
10
4
20
100
```
filter function: The filter function has a similar syntax to the map function:

filter(predicate, Iterator)

where predicate is a function with a boolean return value. The filter function applies predicate to each element of the Iterator and only keeps the ones for which predicate returns True. For example:
```
>>> def positive(x): return x > 0
>>> for x in filter(positive, [10, -4, 20, -100]): print(x)
10
20
```

Of course, the functional capabilities of Python is more diverse than we can cover in this introductory textbook. The reader is referred to Python docs. The curious reader is especially recommended to look at lambda expressions and the reduce function.

6.6. Functions in programming vs. functions in Mathematics¶

It is to be noted that functions have a differentiated meaning compared to functions in Mathematics.

In Mathematics, a function is a mapping from a domain to a range (target); a function returns a value.

In Python: Functions may not return a value at all. If so, they are intended to code a parametrized action. A few examples to this are:
- Drawing a \(red\) line from \((x_0, y_0)\) to \((x_1, y_1)\).
- Printing a separating line made of \(n\) ‘minus’ signs.
- Turning off the lights.
- Sending a digital initialization string to a device connected through the USB port.
In Mathematics, a function definition is global. You do not have function definitions local to some function.

In Python: Since a function definition is done by a Python \(\color{red}{Statement}\) (or a group of statements – grouped by indentation), it is quite possible to have another definition as part of the defining statements. Such a function can only be usable in the \(\color{red}{Statement}\) group that defines the outer function and access its local variables and parameters. Outside of the function, this interior function (called a local function) will not be visible nor usable.
In Mathematics, an element from the domain is mapped to one and only one target element by the function. The mapping does not change. Moreover, a mathematical function returns a value that only depends on the arguments. Hence, for the same arguments, the result is the same.

In Python: Even if such a mapping exists (i.e. a function returns a value), it is possible that the function acts differently due to different settings of the variables (outside of the function) that can be accessed in the functions. Consider the F_gravity function above: A different setting for the G (the Gravitational Constant) will yield a different F_gravity result even when the parameters are the same.
In Mathematics, a function’s operation is reflected on the value it returns: It does not have side effects. In other words, a mathematical function does not change the mathematical environment that is external to it (variables or the ways other functions are evaluated).

In Python: This may not be true. Consider the G value of the F_gravity function above. Hypothetically, it is possible that, at each call of F_gravity, the G value is increased slightly (1% for example):

>>> def F_gravity(m1, m2, r):
...   global G        # since we alter it
...   G = 1.01 * G
...   return G * m1 * m2 / (r * r)

>>> G = 6.67408E-11

>>> print(F_gravity(1000, 20, 0.5), "Newton")
5.39265664e-06 Newton

>>> print(F_gravity(1000, 20, 0.5), "Newton")
5.4465832064e-06 Newton

>>> print(F_gravity(1000, 20, 0.5), "Newton")
5.501049038464e-06 Newton

In these aspects, a function defined in Python has a greater freedom. As previously stated, there are paradigms of programming. One of these paradigms, the functional paradigm, promotes the function’s usage to be restricted to the mathematical sense. In other words, the functional paradigm followers deliberately renounce the additional freedom programming languages like Python provides in function definitions and usages with respect to the mathematical sense. As a rule-of-thumb we can say that deviating from the mathematical sense makes your programming error prone.

6.7. Recursion¶

Recursion is a function definition technique in which the definition makes use of calls to the function being defined. Although it is difficult to grasp, it allows compact and more readable code for recursive algorithms, relations or mathematical functions.

It is customary to give the infamous example of the recursive definition of factorial. First, let us put it down in mathematical terms:

(6.7.1)¶\[\begin{split}\begin{array}{lll} N! & = & (N-1)!\times N, \qquad \textrm{for}\ N\in \mathbf{N}, \;\; N>0 \\ 0! & = & 1, \nonumber \end{array}\end{split}\]

Based on this, we can realize that:

\(6!\) is \(6\times5!\)
\(5!\) is \(5\times 4!\)
\(4!\) is \(4\times 3!\)
\(3!\) is \(3\times 2!\)
\(2!\) is \(2\times 1!\)
\(1!\) is \(1\times 0!\)
\(0!\) is \(1\)

Substituting any factorial value, based on this rule, one ends up with

(6.7.2)¶\[6! = 6\times 5\times 4\times 3\times 2 \times 1 \times 1.\]

Making use of \((N-1)!\) while we are defining \(N!\) is making a recursive definition. The Python equivalent of the above given recursive mathematical definition of the factorial would be:

def factorial(N):
    if N == 0: return 1
    else: return N * factorial(N-1)

High-level languages are designed so that each call to the factorial function does not remember any previous call(s) even if they are still active (unfinished). For every new call, fresh positions for all local variables are created in the memory without forgetting the former values of variables for the unfinished calls.

From the programmers point of view, the only concern is the algorithmic answer to the question:

“Having the recursive call returned the correct answer to the smaller problem, how can I cook up the answer to the actual problem?”

It requires a kind of ‘stop thinking’ (leap of faith) action: ‘Stop thinking how the recursive call comes up with the correct answer’. Just concentrate on the next step paraphrased in the quotation above.

Not to get into an infinite, non-stopping recursive loop, you should be careful about two aspects:

The recursive call should be made with a decrescent (getting smaller) argument. In the factorial example, calculation of \(N!\) recursively called \((N-1)!\), i.e. a smaller value than \(N!\).
The function definition must start with a test for the smallest possible argument case (in the factorial example, this was 0 (zero)) where a value for this case is directly returned (in the factorial example this was 1 (one)). This is called the termination or base condition.

Let us consider another example: We have a list of unordered numbers. Nothing is pre-known about the magnitude of the numbers. The problem is to find the maximum of the numbers in that list.

Let us say you are given a list of, say, 900 numbers. For a second, assume that you have a very loving grandpa. Your grandpa has a rule of his own: not to corrupt you, he will not solve the problem for you but, if you reduce the problem slightly, his heart softens and provides the answer for the smaller problem.

Presumably, the simplest ‘reduction’ that you can do on a 900-element list is removing an element from it and making it a list of 899 numbers. As far as Python lists are concerned, the simplest of the simple is to remove the first element: If L is your list, L[0] is the first element and L[1:] is the list of remaining elements. So, the trick is to remove the first element, take L[1:] to your grandpa (that is making the recursive call), and ask for the solution. Your grandpa is very cooperative and gives you the solution (the biggest number) for the list (L[1:]) you passed to him.

However, we are not finished: On one hand you have what your grandpa returned to you as the biggest number of the slightly reduced list (L[1:]), and on the other hand, you have the removed (first) element L[0]. Now, which one will you return as the solution of the 900 number list? Think about it!

Here is the solution in Python:

def find_max(L):
    if len(L) == 1: return L[0]   # Terminating condition
    else:
            grandpa_result = find_max(L[1:])   #recursion is on L with the 0th element removed
            if grandpa_result > L[0]: return grandpa_result
            else: return L[0]

# Let's try with a simple list -- try changing M and check the result
M = [-100, 10, -10, 100]
print("The maximum element of M is:", find_max(M))

The maximum element of M is: 100

As you may have recognized, the definition started with testing for the smallest case. That is a single element list for which the result (the biggest number in the list) is that single number itself.

Recursion helps writing elegant functions. However, it does not come for free. The price is in the time and memory overhead spent on creating a new function call. Time may be something tolerable but memory is limited. For functions that make thousands of recursive calls, you should better seek algorithmic solutions that do not lean on recursion. Python has a default for recursion depth, which is set to 1000. This can be altered. As said, it is better to seek a non-recursive solution unless you know very well of what you are doing.

Any recursive function can be implemented using iterations. The reverse is also true: Any iterative function can be implemented using recursion. The definition of the problem or the algorithm generally provides hints for whether recursion or iteration is better for implementing your solution.

6.8. Function Examples¶

Example 1: Computing average and standard-deviation

In the previous chapter, we provided iterative definitions for calculating the average and the standard-deviation of a list of numbers. Let us look at these definitions again with functions. For the sake of ease, the mathematical definitions are provided again. Moreover, we will use this opportunity to talk more about iterations as well.

Average of a set (\(S\)) of numbers is calculated by dividing the sum of the values in the set by their number. So, if we have a set \(S\):

(6.8.1)¶\[avg(S) = \frac{1}{|S|}\sum_{x\in S} x,\]

which can be coded as:

def avg(S):
  sum = 0.0
  for x in S: sum += x
  return sum/len(S)

S = [11, 2, 9, 6]
print("The avg of S:", avg(S))

The avg of S: 7.0

This is quite elegant. As you see it works at a higher abstraction level. This can be done because the in operator comes in very handy and when used as an iterator, it iterates over the elements of the list.

Sometimes it is more desirable to work with the indices to reach out to each element. Remember that indexing of container elements start at zero. So, a more index-based formulation of the same formula would be:

(6.8.2)¶\[avg(S) = \frac{1}{|S|}\sum_{i=0}^{|S|-1} S_i\]

The following implements this definition:

def avg(S):
  sum = 0.0
  for i in range(0, len(S)): sum += S[i]
  return sum/len(S)

S = [11, 2, 9, 6]
print("The avg of S:", avg(S))

This is almost okay but not perfect. len is a built-in function that returns the element count of any container (string, list, tuple). As you have observed len(S) is calculated twice. This is inefficient. Function calls have a price, time-wise and space-wise, and therefore, unnecessary calls should be avoided. To fix this, we change the code to do computation once and store the result for further usages.

def avg(S):
  sum = 0.0
  length = len(S)
  for i in range(0, length): sum += S[i]
  return sum/length

S = [11, 2, 9, 6]
print("The avg of S:", avg(S))

The avg of S: 7.0

sum, length, i and the parameter S are all local variables of the function avg. In contrary to many other programming languages, in Python we do not have to declare locals. They are automatically recognized. This comes in very handy.

One point to note about the code is that the \(|S|-1\) is missing. It is not necessary because the range iterator excludes the end value, as we discussed in the previous chapter.

Now let us also introduce the code for standard deviation. First the mathematical definition:

(6.8.3)¶\[std(S) = \sqrt{\frac{1}{|S|}\displaystyle\sum_{i=0}^{|S|-1}(S_i - avg(S))^2}\]

This time we bear in mind that unnecessary function calls should be avoided:

def avg(S):
  sum = 0.0
  length = len(S)
  for i in range(0, length): sum += S[i]
  return sum/length

def std(S):
  sum = 0.0
  length = len(S)
  average = avg(S)
  for i in range(0, length): sum += (S[i] - average)**2
  return (sum/length)**0.5

S = [11, 2, 9, 6]
print("The avg of S:", avg(S))
print("The std of S:", std(S))

The avg of S: 7.0
The std of S: 3.391164991562634

We gave the solution in terms of explicit indexing. As given below this particular problem can be coded without an iteration over indices. Such problems are rare. Problems that require operations over vectors and matrices or problems that aim optimizations usually require explicit index iterations.

For sake of completeness we state the index-less solution of the average and standard-deviation problem:

def avg(S):
  sum = 0.0
  length = len(S)
  for x in S: sum += x
  return sum/length

def std(S):
  sum = 0.0
  length = len(S)
  average = avg(S)
  for x in S: sum += (x - average)**2
  return (sum/length)**0.5

S = [11, 2, 9, 6]
print("The avg of S:", avg(S))
print("The std of S:", std(S))

The avg of S: 7.0
The std of S: 3.391164991562634

Example 2: Computing check digit

A Standard Definition from Wikipedia:

“A check digit is a form of redundancy check used for error detection on identification numbers, such as bank account numbers, which are used in an application where they will at least sometimes be input manually. It consists of one or more digits computed by an algorithm from the other digits (or letters) in the sequence input.

With a check digit, one can detect simple errors in the input of a series of characters (usually digits) such as a single mistyped digit or some permutations of two successive digits.”

Middle East Technical University, our university, also implements a check digit algorithm for student numbers. A student number has exactly six digits. The algorithm to generate the checkdigit is as follows:

\(sum \leftarrow 0\)
For each digit in the student number (the leftmost digit is the named as the ‘first’) that has an odd position (first, third, fifth), take the digit and add it to the \(sum\).
For each digit in the student number that has an even position (second, forth, sixth) take twice the digit. If this result of doubling is a two digit number, then add each of these digits to the \(sum\), otherwise add the result of the doubling (which is a single digit number itself) to the \(sum\).
The one digit number, which when added to the \(sum\) results in a multiple of 10, is the check digit.

Take as example the student number 167912:

Fig. 6.8.1 How checksum is calculated for a student number.¶

The check digit of the student number 167912 is found to be 5. As you all well know, this is written as 167912-5. That is called the student-id.

Below you will find the code that computes the checkdigit for a student number, given as a string. We encourage you to investigate it. A very good technique to understand how a code progresses when it runs is to insert print statements to points of interest. You can start by inserting:

print(digit, sum)

right after the line of else: (left-aligned with the else).

def checksum(S):
    sum = 0
    for i in range(0, len(S)):
        digit = int(S[i])
        if i%2 == 0: sum += digit
        else: sum += (9 if digit==9 else (2*digit) % 9)
    n = sum % 10
    return 0 if n == 0 else 10 - n

print(checksum("167912"))

A few notes about the code:

Remember indexing starts in Python at zero. One group of digits, namely (first, third, fifth) are actually at S[0], S[2] and S[4]. Their indices are even. Or in mathematical terms, they are (modulo 2) zero.
Summing the digits of a number is a trick we learned in primary school. It is actually nothing else but a quick way to do (modulo 9). So, we are actually taking the (modulo 9) of the doubled digit. With one exception: If the digit is 9, the double is 18 where we have to add a 1+8=9 to the sum. But (18 % 9) would give us zero (not 9). So, here we have to insert an exception: For all digits except 9, we can use (2*digit) % 9. For 9, we ought to add a 9 to the sum.
The rule of constructing the check digit from the sum has a similar exception case for sum being a multiple of 10 (i.e. n (modulo 10) = 0). In that case we would have a checkdigit of 10 (because 10-0 = 10) which is not a digit, but two digits. The designers decided to use a zero as the checkdigit for this particular case.

Now let us see how the checkdigit can be used to recover a missing digit of the student id.

Let us assume you have a student ID as: 1🁢9503-7. Now, can we discover what the (🁢) digit is?

For this purpose we will write a function find_q_mark() that will take a string as an argument, in which the missing digit is indicated by a (?) (question mark). We are expecting that a call of find_q_mark("1?9503-7") will recover the missing digit and return the demystified string: “139503-7”.

Note that the checksum() definition of above is still effective.

# places digit in the place of '?' in the string S
def replace_q_mark(S, digit):
    new_S =""
    for c in S: new_S += str(digit) if c=='?' else c
    return new_S

# finds the value for the position with '?'
def find_q_mark(MissingStdID):      # MissingStdID is something like "1?7912-5"
    six_digit_string = MissingStdID[:6]  # "1?7912"
    checksum_digit = int(MissingStdID[7])
    for missing_digit in range(0, 10):
        candidate = replace_q_mark(six_digit_string, missing_digit)
        if checksum(candidate) == checksum_digit: return candidate + MissingStdID[6:]

print(find_q_mark("1?7912-5"))

167912-5

A few notes about the code:

replace_q_mark() function is called by find_q_mark(). It is only called once, therefore its actions could have been migrated into find_q_mark(). Efficiency-wise there would be no change. But seperating it out, making it into a function and naming it accordingly makes the code more readable.
The first two lines that define find_q_mark() actions are merely dissecting the string into a student-id and a checkdigit part.
What we do in the for loop in find_q_mark() (on Lines 11-13) is coined in Computer Science as brute force. Practically, it is trying every possible case for being a solution. In this problem, the (?) mark can be any digit in the range [0,9]. The for loop tries each of these possibilities out until the computed checksum becomes the same as the checkdigit appearing in the input string.

Example 3: Sequential Search

Searching an item in a list or any other container is a frequently performed operation required while solving world problems. For the sake of simplicity, let us just focus on situations where only numbers are involved; i.e. the searched item is a number and the list includes only numbers. Extension to other data types is trivial.

In a search problem, we have a query item (let’s call it x) and a list of items (let’s call it L). If x is a member of L, then we want the search algorithm to return True, optionally by returning its index in L. If x is not a member of L, we expect the algorithm to return False.

Consider the example list below:

(6.8.4)¶\[\begin{split}\begin{array}{|c|c|c|c|c|} \hline 109 & -48 & 25 & 4 & -13 \\ \hline \end{array}\end{split}\]

If x is 4, the search algorithm should return True. If it is 5, the answer should be False.

Let us start with the simplest algorithm we can use: Sequential Search. In sequential search, we start with the beginning of the list, go over each item in the list and check if the query is equal to any item that we go over. Here is the algorithm:

Algorithm: Sequential Search with While Iterations
----------------------------
Input: x -- the query number
       L -- the list of numbers
Output: True (if x is in L) or False (if x is not in L)
----------------------------
Step 1: Create a variable named Index with initial value 0
Step 2: Create a variable named N with value length(L)
Step 3: While Index < N is True, execute Steps 4 and 5:
Step 4:    If x is equal to L[Index], then return True as the result
Step 5:    Index = Index + 1
Step 6: Return False as the result

Let us implement this simple algorithm in Python:

# Sequential Search with while statement
def seq_search(x, L):
  index = 0                          # Step 1
  N = len(L)                         # Step 2
  while index < N:                   # Step 3
    if x == L[index]: return True    # Step 4
    index = index + 1                # Step 5
  return False                       # Step 6


# Now let us test the function with examples:
L = [109, -48, 25, 4, -13]
x = 4
print(f"seq_search({x}, {L}): ", seq_search(x, L))
x = 5
print(f"seq_search({x}, {L}): ", seq_search(x, L))
x = 5
L = []
print(f"seq_search({x}, {L}): ", seq_search(x, L))

seq_search(4, [109, -48, 25, 4, -13]):  True
seq_search(5, [109, -48, 25, 4, -13]):  False
seq_search(5, []):  False

That looks nice. However, we can have a more compact solution using for loops:

# Sequential Search with for statement
def seq_search(x, L):
  for y in L:
    if x == y: return True
  return False

# Now let us test the function with examples:
L = [109, -48, 25, 4, -13]
x = 4
print(f"seq_search({x}, {L}): ", seq_search(x, L))
x = 5
print(f"seq_search({x}, {L}): ", seq_search(x, L))
x = 5
L = []
print(f"seq_search({x}, {L}): ", seq_search(x, L))

seq_search(4, [109, -48, 25, 4, -13]):  True
seq_search(5, [109, -48, 25, 4, -13]):  False
seq_search(5, []):  False

That’s the beauty of Python. These two are iterative solutions. Let us have a look at a recursive solution. First, let us have a look at the algorithm. The idea is essentially the same: We compare with the first item and return True if they match. Otherwise, we continue our search with the remaining items.

Algorithm: Sequential Search with Recursion
----------------------------
Input: x -- the query number
       L -- the list of numbers
Output: True (if x is in L) or False (if x is not in L)
----------------------------
Step 1: If L is empty, return False
Step 2: If x is equal to the first item of L (L[0]), return True
Step 3: Make a recursive call on L[1:N], and return its answer

And here is the implementation in Python:

# Sequential Search with recursion
def seq_search(x, L):
  if L == []: return False      # Step 1: We have exhausted the list, x was not found
  if x == L[0]: return True     # Step 2: x was at the beginning of the list, yay!
  return seq_search(x, L[1:])   # Step 3: Search in the remaining items since x != L[0]

# Now let us test the function with examples:
L = [109, -48, 25, 4, -13]
x = 4
print(f"seq_search({x}, {L}): ", seq_search(x, L))
x = 5
print(f"seq_search({x}, {L}): ", seq_search(x, L))
x = 5
L = []
print(f"seq_search({x}, {L}): ", seq_search(x, L))

seq_search(4, [109, -48, 25, 4, -13]):  True
seq_search(5, [109, -48, 25, 4, -13]):  False
seq_search(5, []):  False

Exercise

Write down the pseudocode for the Python function seq_search with for statement.

Exercise

Extend the recursive implementation of seq_search to search for an item x in a list L in cases where L can be nested. In other words, the extended search algorithm shoud return True for:

seq_search_nested(5, [10, [4, [5]], -84, [3]])

and False for:

seq_search_nested(8, [10, [4, [5]], -84, [3]])

Example 4: Binary Search

If the list of items (numbers in our case) is not sorted, sequential search is the only option for searching for an item. If, however, the numbers are sorted (in an increasing or decreasing order), then we have a much more efficient algorithm called binary search.

Assuming that L, our list of numbers, is sorted in an increasing order: In binary search, we make our first comparison with the number that is at the center (middle) of the list. If the middle number is equal to x, then we obviously return True. Otherwise, we compare x with the middle number: If x is smaller, then it has to be to the left of the middle number – we can continue our search on the left part of L. If, on the other hand, x is larger than the middle number, it has to be on the right side of the middle number – we can continue our search on the right part of L. This is illustrated in the following figure.

Fig. 6.8.2 Binary search algorithm.¶

Here is the pseudocode that describes this algorithm:

Algorithm: Binary Search with Recursion
----------------------------
Input: x -- the query number
       L -- the list of numbers
Output: True (if x is in L) or False (if x is not in L)
----------------------------
Step 1: If length(L) is zero then return False since the list is empty
Step 2: Create a variable Mid_index with value length(L)/2
Step 3: If x = L[Mid_Index], return True, we found the item
Step 4: If x < L[Mid_index] then make recursive call with L[0:Mid_index] and return its answer
Step 5: Otherwise (x > L[Mid_index]) then make a recursive call with L[Mid_index+1:] and return its answer

The following is the implementation in Python:

# Binary search with recursion
def bin_search(x, L):
  if len(L) == 0: return False                                # Step 1: Terminating condition
  Mid_index = len(L) // 2                                     # Step 2: Uses integer division
  if x == L[Mid_index]: return True                           # Step 3
  if x < L[Mid_index]: return bin_search(x, L[0:Mid_index])   # Step 4
  if x > L[Mid_index]: return bin_search(x, L[Mid_index+1:])  # Step 5: Can drop if statement

# Now let us test the function with examples:
L = [-48, -13, 4, 25, 109]
x = 4
print(f"bin_search({x}, {L}): ", bin_search(x, L))
x = 5
print(f"bin_search({x}, {L}): ", bin_search(x, L))
x = 5
L = []
print(f"bin_search({x}, {L}): ", bin_search(x, L))

bin_search(4, [-48, -13, 4, 25, 109]):  True
bin_search(5, [-48, -13, 4, 25, 109]):  False
bin_search(5, []):  False

Exercise

Implement binary search using while statements.

Exercise

Identify the complexity of sequential search and binary search in the following cases:

Best case: When the item that we are making our first comparison with is the one we were looking for.
Worst case: The item we are looking for is the last item with which we performed the comparison.
Average case.

Example 5: Sorting

Sorting pertains to ordering a list of items (\(L\)) so that each item in \(L\) satisfies the following constraint:

(6.8.5)¶\[L_i < L_{i+1},\]

which leads to an ascending (increasing) order of items in \(L\) and this is called ascending sort. If the order of the constraint is changed to \(L_i > L_{i+1}\), the outcome is a descending (decreasing) order of items in \(L\) and this is called descending sort.

An algorithm that can perform ascending sort can easily be changed to descending sort; therefore, we will just focus on one of them, namely, ascending sort. Moreover, we will focus on sorting a list of numbers; however, the same algorithms can be applied on other data types as long as an ordering constraint (< or >) can be defined.

Bubble Sort

Let us have a look at a very simple though inefficient sorting algorithm, called Bubble Sort. In Bubble Sort, we start from the beginning of the list and check whether the constraint \(L_i < L_{i+1}\) is violated for an \(i\) value. If it is, we swap \(L_i\) with \(L_{i+1}\). When we hit the end of the list, we start from the beginning of the list again and continue checking the constraint \(L_i < L_{i+1}\). Once at the end of the list, we again go back to the beginning and continue checking the constraint for each \(i\). This continues until no \(i\) value violates the constraint \(L_i < L_{i+1}\), which means that the numbers are sorted.

Therefore, in Bubble Sort, we have two loops, one outer loop that continues until all numbers are sorted and an inner loop that goes through the list and checks the constraint. Here is a pseudo-code for this:

Algorithm: Bubble Sort
----------------------------
Input: L -- the list of numbers (not sorted)
Output: L -- the sorted list of numbers (ascending order)
----------------------------
Step 1: Create a varible Is_sorted with value False
Step 2: Create a variable N with value length(L)
Step 3: Create a variable Index
Step 4: While Is_sorted is False, repeat Steps 5-11:
Step 5:     Set Is_sorted to True
Step 6:     Set Index to zero
Step 7:     While Index < (N-1), repeat Steps 8-11
Step 8:         If L[Index] > L[Index+1], then execute Steps 9 & 10:
Step 9:              Swap L[Index] and L[Index+1]
Step 10:             Set Is_sorted to False
Step 11:        Index = Index + 1
Step 12: return L

One outer iteration of the algorithm is illustrated on a small list of numbers below:

Fig. 6.8.3 One outer iteration of the Bubble Sort algorithm.¶

With one outer iteration, the list appears to be one step closer to a sorted list. In the example above, the largest number has found its correct place after one outer iteration. With a second one, the second largest number will find its place. With a third iteration, the third largest number will find its place etc.

And here is the implementation in Python:

# Bubble Sort

def bubble_sort(L):
  Is_sorted = False                                       # Step 1
  N = len(L)                                              # Step 2
  Index = 0                                               # Step 3: Can be removed in Python

  while Is_sorted is False:                               # Step 4
    Is_sorted = True                                      # Step 5
    Index = 0                                             # Step 6
    while Index < (N-1):                                  # Step 7
      if L[Index] > L[Index+1]:                           # Step 8
        (L[Index], L[Index+1]) = (L[Index+1], L[Index])   # Step 9
        Is_sorted = False                                 # Step 10
      Index = Index + 1                                   # Step 11
  return L                                                # Step 12

# Let us test our implementation with some sample lists
L = [109, -13, 4, -48, 25]
print(f"bubble_sort({L}): ", bubble_sort(L))

L = [-48, -13, 4, 25, 109]
print(f"bubble_sort({L}): ", bubble_sort(L))

L = []
print(f"bubble_sort({L}): ", bubble_sort(L))

bubble_sort([109, -13, 4, -48, 25]):  [-48, -13, 4, 25, 109]
bubble_sort([-48, -13, 4, 25, 109]):  [-48, -13, 4, 25, 109]
bubble_sort([]):  []

6.9. Programming Style¶

With the topics covered in this chapter, we started working with longer and more elaborated Python codes. Up to now, we have introduced crucial aspects that can be arranged differently among programmers:

Naming variables and functions.
Indentation.
Function definition.
Commenting.

Longing for brevity and readability, the creators of Python have defined some guidelines of style for those interested: Python Style Guide.

There are alternative styles and we strongly recommend you to choose one and stick to it as a programming style.

6.10. Important Concepts¶

We would like our readers to have grasped the following crucial concepts and keywords from this chapter (all related to Python):

Defining functions.
Function parameters and how to pass values to functions.
Default parameters.
Scopes of variables.
Local, enclosing, global and built-in scopes.
Higher-order functions.
Differences of functions between programming and Mathematics.
Recursion.

6.11. Further Reading¶

Functional tools of Python: https://docs.python.org/3/howto/functional.html
A more comprehensive coverage on recursion: https://link.springer.com/chapter/10.1007/978-3-7091-1343-1_4
Python style guide: https://www.python.org/dev/peps/pep-0008/

6.12. Exercises¶

Write a Python function named only_numbers() that removes items in a list that are not numbers. E.g. only_numbers([10, "ali", [20], True, 4]) should return [10, 4]. Implement two versions: One using iteration and another using recursion.
Write a Python function named flatten() that removes nesting in a nested list and lists all elements in a single non-nested list. E.g. flatten([1, [4, 5, [6]], [["test"]]]) should return [1, 4, 5, 6, "test"].
Write a Python function named reverse() that reverses the order of elements in a list. E.g. reverse([10, 5, 0]) should return [0, 5, 10]. Implement two versions: One using iteration and another using recursion.
Write a Python function named greatest_divisor() that finds the greatest divisor of an integer. The greatest divisor of an integer \(n\) is an integer \(x < n\) that satisfies \(n = k \cdot x\) for some integer \(k\). E.g. greatest_divisor(12) should return 6.

6. Functions¶ Colab Open the notebook in Colab

6.1. Why define functions?¶

6.2. Defining functions¶

6.3. Passing parameters to functions¶

6.3.1. Default Parameters¶

6.4. Scope of variables¶

6.5. Higher-order functions¶

6.6. Functions in programming vs. functions in Mathematics¶

6.7. Recursion¶

6.8. Function Examples¶

6.9. Programming Style¶

6.10. Important Concepts¶

6.11. Further Reading¶

6.12. Exercises¶

6. Functions¶
Open the notebook in Colab