Functions and Algorithms
While functions denote a specific object in Python programming with which we can order and factor our programs, the term algorithm typically refers to the general organization of a sequence of logic to process its given input data. In data science and scientific computing, algorithms are ubiquitous, commonly taking the form of machine learning models that are used to process data and potentially make predictions.
In this section, we will discuss the concept and syntax of Python functions and then tackle some example algorithm-design problems.
Functions
In its most abstract definition, a function is simply an object that can take in an input and producing an output, according to a given set of instructions. A Python function is of the following form:
def func_name(param1, param2, ...):
[…]
return […]
The def keyword denotes the start of a Python function. The name of a function can be anything, though the rule is to avoid special characters at the beginning of the name and to use snake case. Between the parentheses are the parameters that the function takes in, which are separated by commas and can be used inside the indented code of the function.
For example, the following function takes in a string (though this requirement is unspecified) and prints out a greeting message:
>>> def greet(name):
... print(f'Hello, {name}!')
Then, we can call this function on any string that we want and achieve the effect that we intended with the instruction inside the function. If we somehow mis-specify the arguments that a function takes in (for example, the last statement in the following code snippet), the interpreter will return an error:
>>> greet('Quan')
Hello, Quan!
>>> greet('Alice')
Hello, Alice!
>>> greet()
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: greet() missing 1 required positional argument: 'name'
It is important to note that any local variables (variables declared inside a function) cannot be used outside of the scope of the function. In other words, once a function finishes its execution, none of its variables will be accessible by other code.
Most of the time, we would want our functions to return some sort of value at the end, which is facilitated by the return keyword. As soon as a return statement is executed, the execution of a program will exit out of a given function and return to the parent scope that called the function. This allows us to design a number of dynamic logic sequences.
For example, imagine a function that takes in a Python list of integers and returns the first element that is pisible by 2 (and returns False if there is no even element in the list):
def get_first_even(my_list):
[...]
return # should be the first even element
Now, the natural way to write this function is to loop through the elements in the list and check for their 2-pisibility:
def get_first_even(my_list):
for item in my_list:
if item % 2 == 0:
[...]
return # should be the first even element
However, if and when the condition is met (that is, when the current element we are iterating over is pisible by 2), that very element should be the return value of the function, since it is the first element in the list that is pisible by 2. This means we can actually return it within the if block (and finally return False at the end of the function):
def get_first_even(my_list):
for item in my_list:
if item % 2 == 0:
return item
return False
This approach is to be contrasted with an alternative version where we only return the element that satisfies our condition at the end of the loop, which will be more time-consuming (execution-wise) and require an additional check as to whether there is an even element in the input list. We will examine a variation of this logic in depth in the next exercise.
Exercise 1.05: Finding the Maximum
Finding the maximum/minimum of an array, or list, is a common exercise in any introductory programming class. In this exercise, we will consider an elevated version of the problem, in which we need to write a function that returns the index and the actual value of the maximum element within a list (if tie-breaking is needed, we return the last maximum element).
Perform the following steps to complete this exercise:
- Create a new Jupyter notebook and declare the general structure of our target function in a code cell:
def get_max(my_list):
...
return ...
- Create a variable that keeps track of the index of the current maximum element called running_max_index, which should be initialized to 0:
def get_max(my_list):
running_max_index = 0
...
return ...
- Loop through the values in the parameter list and their corresponding indices using a for loop and the enumerate operation:
def get_max(my_list):
running_max_index = 0
# Iterate over index-value pairs.
for index, item in enumerate(my_list):
[...]
return ...
- At each step of the iteration, check to see if the current element is greater than or equal to the element corresponding to the running indexing variable. If that is the case, assign the index of the current element to the running maximum index:
def get_max(my_list):
running_max_index = 0
# Iterate over index-value pairs.
for index, item in enumerate(my_list):
if item >= my_list[running_max_index]:
running_max_index = index
return [...]
- Finally, return the running maximum index and its corresponding value as a tuple:
def get_max(my_list):
running_max_index = 0
# Iterate over index-value pairs.
for index, item in enumerate(my_list):
if item >= my_list[running_max_index]:
running_max_index = index
return running_max_index, my_list[running_max_index]
- In a new cell, call this function on various lists to test for different cases. An example of this is as follows:
>>> get_max([1, 3, 2])
(1, 3)
>>> get_max([1, 3, 56, 29, 100, 99, 3, 100, 10, 23])
(7, 100)
This exercise helped us review the general syntax of a Python function and also offered a refresher on looping. Furthermore, variations of the logic that we considered are commonly found in scientific computing projects (for example, finding the minimum or an element in an iterator that satisfies some given conditions).
Note
To access the source code for this specific section, please refer to https://packt.live/2Zu6KuH.
You can also run this example online at https://packt.live/2BUNjDk.
Next, let's discuss a very specific style of function design called recursion.
Recursion
The term recursion in programming denotes the style of solving a problem using functions by having a function recursively call itself. The idea is that each time the function is called, its logic will take a small step toward the solution of the problem, and by doing this many times, the original problem will be finally solved. The idea is that if we somehow have a way to translate our problem into a small one that can be solved in the same way, we can repeatedly break down the problem to arrive at the base case and ensure that the original, bigger problem is solved.
Consider the problem of computing the sum of n integers. If we somehow already have the sum of the first n - 1 integers, then we can simply add the last number to that sum to compute the total sum of the n numbers. But how can the sum of the first n - 1 numbers be computed? With recursion, we once again assume that if we have the sum of the first n - 2 numbers, then we add in that last number. This process repeats until we reach the first number in the list, and the whole process completes.
Let's consider this function in the following example:
>>> def find_sum(my_list):
... if len(my_list) == 1:
... return my_list[0]
... return find_sum(my_list[: -1]) + my_list[-1]
We can see that, in the general case, the function computes and returns the result of adding the last element of the input list, my_list[-1], to the sum of the sublist without this last element my_list[: -1], which is in turn computed by the find_sum() function itself. Again, we rationalize that if the find_sum() function can somehow solve the problem of summing a list in a smaller case, we can generalize the result to any given non-empty list.
Handling the base case is therefore an integral part of any recursive algorithm. Here, our base case is when the input list is a single-valued one (checked by our if statement), in which case we should simply return that very element in the list.
We can see that this function correctly computes the sum of any non-empty list of integers, as shown here:
>>> find_sum([1, 2, 3])
6
>>> find_sum([1])
1
This is a somewhat basic example, as finding the sum of a list can be easily done by maintaining a running sum and using a for loop to iterate over all the elements in the input list. In fact, most of the time, recursion is less efficient than iteration, as there is significant overhead in repeatedly calling function after function in a program.
However, there are situations, as we will see in the following exercise, where, by abstracting our approach to a problem to a recursive algorithm, we can significantly simplify how the problem is solved.
Exercise 1.06: The Tower of Hanoi
The Tower of Hanoi is a well-known mathematical problem and a classic application of recursion. The problem statement is as follows.
There are three disk stacks where disks can be placed in and n disks, all of different sizes. At the beginning, the disks are stacked in ascending order (the largest at the bottom) in one single stack. At each step of the game, we can take the top disk of one stack and put it at the top of another stack (which can be an empty stack) with the condition that no disk can be placed on top of a disk that is smaller than it.
We are asked to compute the minimum number of moves necessary to move the entire stack of n disk from one stack to another. While the problem can be quite complex if we think about it in a linear way, it becomes simpler when we employ a recursive algorithm.
Specifically, in order to move the n disks, we need to move the top n - 1 disks to another stack, move the bottom, biggest disk to the last stack, and finally move the n - 1 disks in the other stack to the same stack as the biggest disk. Now, imagine we can compute the minimum number of steps taken to move (n - 1) disks from one stack to another, denoted as S(n - 1), then to move n disks, we need 2 S(n - 1) + 1 steps.
That is the recursively analytical solution to the problem. Now, let's write a function to actually compute this quantity for any given n.
Perform the following steps to complete this exercise:
- In a new Jupyter notebook, define a function that takes in an integer named n and returns the quantity that we arrived at previously:
def solve(n):
return 2 * solve(n - 1) + 1
- Create a conditional in the function to handle the base case where n = 1 (note that it only takes one step to move a single disk):
def solve(n):
if n == 1:
return 1
return 2 * solve(n - 1) + 1
- In a different cell, call the function on different inputs to verify that the function returns the correct analytical solution to the problem, which is 2n - 1:
>>> print(solve(3) == 2 ** 3 - 1)
True
>>> print(solve(6) == 2 ** 6 - 1)
True
Here, we are using the == operator to compare two values: the returned value from our solve() function and the analytical expression of the solution. If they are equal, we should see the Boolean True printed out, which is the case for both comparisons we have here.
While the code in this exercise is short, it has illustrated the point that recursion can offer elegant solutions to a number of problems and has hopefully solidified our understanding of the procedure of a recursive algorithm (with the general step and a base case).
Note
To access the source code for this specific section, please refer to https://packt.live/2NMrGrk.
You can also run this example online at https://packt.live/2AnAP6R.
With that, we'll move on and start discussing the general process of algorithm design in the next section.
Algorithm Design
Designing algorithms is actually something that we have been doing all along, especially in this section, which is all about functions and algorithms: discussing what a functional object should take in, how it should process that input, and what output it should return at the end of its execution. In this section, we will briefly discuss some practices in a general algorithm-design procedure and then consider a somewhat complex problem called the N-Queens problem as an exercise.
While writing Python functions, some programmers might choose to implement subfunctions (functions within other functions). Following the idea of encapsulation in software development, a subfunction should be implemented when it is only called by instructions within another function. If this is the case, the first function can be viewed as a helper function of the second and therefore should be placed inside that second function. This form of encapsulation allows us to be more organized with our programs/code and ensure that if a piece of code does not need to use the logic within a given function, then it should not have access to it.
The next point of discussion involves recursive search algorithms, which we'll look at in the next exercise. Specifically, when an algorithm is recursively trying to find a valid solution to a given problem, it can reach a state in which there are no valid solutions (for example, when we are trying to find an even element in a list of only odd integers). This leads to the need for a way to indicate that we have reached an invalid state.
In our find-the-first-even-number example, we chose to return False to indicate an invalid state where our input list only consists of odd numbers. Returning some sort of flag such as False or 0 is actually a common practice that we will follow in later examples in this chapter as well.
With that in mind, let's jump into the exercise of this section.
Exercise 1.07: The N-Queens Problem
Another classic algorithm-design problem in mathematics and computer science, the N-Queens problem asks us to place n queen pieces in the game of chess on an n x n chessboard so that no queen piece can attack another. A queen can attack another piece if they share the same row, column, or diagonal, so the problem is essentially finding a combination of locations for the queen pieces so that any two given queens are in different rows, columns, and diagonals.
For this exercise, we will design a backtracking algorithm that searches for a valid solution to this problem for any positive integer, n. The algorithm is as follows:
- Given the requirements of the problem, we argue that in order to place n pieces, each row of the chessboard needs to include exactly one piece.
- For each row, we iteratively go through all the cells of that row and check to see whether a new queen piece can be placed in a given cell:
a. If such a cell exists, we place a piece in that cell and move on to the next row.
b. If a new queen piece cannot be placed in any cell in the current row, we know that we have reached an invalid state and thus return False.
- We repeat this process until a valid solution is found.
The following diagram describes how this algorithm works with n = 4:
Figure 1.3: Recursion with the N-Queens problem
Now, let's actually implement the algorithm:
- Create a new Jupyter notebook. In its first cell, declare a variable named N to represent the size of our chessboard, as well as the number of queen pieces we need to place on the board:
N = 8
- A chessboard will be represented as a 2D, n x n list with 0 representing an empty cell and 1 representing a cell with a queen piece. Now, in a new code cell, implement a function that takes in a list of this form and print it out in a nice format:
# Print out the board in a nice format.
def display_solution(board):
for i in range(N):
for j in range(N):
print(board[i][j], end=' ')
print()
Note that the end=' ' argument in our print statement specifies that instead of ending the printed output with a newline character, it should simply be a space character. This is so that we can print out the cells in the same row using different print statements.
- In the next cell, write a function that takes in a board, a row number, and a column number. The function should check to see whether a new queen piece can be placed on this board at the location given by the row and column numbers.
Note that since we are iteratively placing pieces rows to rows, each time we check to see whether a new piece can be placed at a given location, we only need to check for the rows above the location:
# Check if a queen can be placed in the position.
def check_next(board, row, col):
# Check the current column.
for i in range(row):
if board[i][col] == 1:
return False
# Check the upper-left diagonal.
for i, j in zip(range(row, -1, -1), \
range(col, -1, -1)):
if board[i][j] == 1:
return False
# Check the upper-right diagonal.
for i, j in zip(range(row, -1, -1), \
range(col, N)):
if board[i][j] == 1:
return False
return True
- In the same code cell, implement a function that takes in a board and a row number. This function should go through all the cells in the given row and check to see whether a new queen piece can be placed at a particular cell (using the check_next() function written in the preceding step).
For such a cell, place a queen in that cell (by changing the cell value to 1) and recursively call the function itself with the next row number. If a final solution is valid, return True; otherwise, remove the queen piece from the cell (by changing it back to 0).
If, after we have considered all the cells of the given row, no valid solution is found, return False to indicate an invalid state. The function should also have a conditional at the beginning to check for whether the row number is larger than the board size N, in which case we simply return True to indicate that we have reached a valid final solution:
def recur_generate_solution(board, row_id):
# Return if we have reached the last row.
if row_id >= N:
return True
# Iteratively try out cells in the current row.
for i in range(N):
if check_next(board, row_id, i):
board[row_id][i] = 1
# Return if a valid solution is found.
final_board = recur_generate_solution(\
board, row_id + 1)
if final_board:
return True
board[row_id][i] = 0
# When the current board has no valid solutions.
return False
- In the same code cell, write a final solver function that wraps around the two functions, check_next() and recur_generate_solution() (in other words, the two functions should be subfunctions of the function we are writing). The function should initialize an empty 2D n x n list (representing the chessboard) and call the recur_generate_solution() function with row number 0.
The function should also print out the solution at the end:
# Generate a valid solution.
def generate_solution():
# Check if a queen can be placed in the position.
def check_next(board, row, col):
[...]
# Recursively generate a solution.
def recur_generate_solution(board, row_id):
[...]
# Start out with en empty board.
my_board = [[0 for _ in range(N)] for __ in range(N)]
final_solution = recur_generate_solution(my_board, 0)
# Display the final solution.
if final_solution is False:
print('A solution cannot be found.')
else:
print('A solution was found.')
display_solution(my_board)
- In a different code cell, run the overarching function from the preceding step to generate and print out a solution:
>>> generate_solution()
A solution was found.
1 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1
0 0 0 0 0 1 0 0
0 0 1 0 0 0 0 0
0 0 0 0 0 0 1 0
0 1 0 0 0 0 0 0
0 0 0 1 0 0 0 0
Throughout this exercise, we have implemented a backtracking algorithm that is designed to search for a valid solution by iteratively making a move toward a potential solution (placing a queen piece in a safe cell), and if the algorithm somehow reaches an invalid state, it will backtrack by undoing its previous move (in our case, by removing the last piece we placed) and looking for a new move to make. As you can probably tell, backtracking is closely related to recursion, and that is why we chose to implement our algorithm using a recursive function, thus consolidating our understanding of the general concept.
Note
To access the source code for this specific section, please refer to https://packt.live/2Bn7nyt.
You can also run this example online at https://packt.live/2ZrKRMQ.
In the next and final section of this chapter, we will consider a number of administrative tasks in Python programming that are often overlooked, namely debugging, testing, and version control.