Functions and conditional statements

Section A.5 Functions and conditional statements

We already have a good, useable definition of functions in Definition A.3.5. That definition still actually holds for programming functions.

Definition A.5.1. Programming function.

Also called a subroutine, a function in computer programming is a sequence of program instructions encapsulated into a unit which can be references elsewhere in a program.

Any self-contained implementation of any algorithm can be considered as a subroutine, so we will use function specifically for those which are defined in Python using the def command.

Subsection A.5.1 `def`ining new functions

As hinted by the title of this subsection, the command in Python which allows functions to be defined is def.

Technology A.5.2. Defining functions with `def`.

In order to define a function in Python, we use the def block structure as follows:

def my_func(arg1, arg2, arg3=default_val):
    """The multiline string which comes immediately after a 'def' statement
    is the docstring, which is displayed when 'help(my_func)' is used at the
    Python console."""
    # Some procedure goes here
    #
    # Every function either explicitly returns a value or the program "falls
    # off" the end of the function, which effectively returns the value
    # None, of NoneType.
    return arg1

Listing A.5.3. An example of using a def block structure

The expression my_func is the name of the function, the values arg1, arg2, and arg3 are arguments to the function, and arg3=default_val indicates that the third argument is optional as a default value is provided. Whatever follows the return statement, or is passed to the return statement in parentheses, is the value sent back to the calling routine where the function was invoked.

Every piece of code that is written can be wrapped in a function with a memorable name and saved by a user in a single location for later use. This allows a programmer to efficiently reuse code that has already been written, rather than having to reimplement known algorithms repeatedly. Extremely common or basic-level functions are actually written into Python, and a list of these built-in functions is available at the Python documentation

¹²

docs.python.org/3/library/functions.html

website.

Subsection A.5.2 Controlling flow of programs

In order to write good, meaningful functions, we need to be able to emulate mathematical functions with piecewise definitions. Take for example the Kronecker delta function,

\begin{equation*} \delta(i,j) = \begin{cases} 1, \amp i=j, \\ 0, \amp i\neq j.\end{cases} \end{equation*}

The value of \(\delta(i,j)\) changes depending upon whether or not the input arguments \(i\) and \(j\) satisfy \((i,j)\in\set{(x,x):x\in\mathbb{R}}\text{.}\) The control of the flow of a program can also depend upon the value of variables, and the structure which enables this is the if:... elif:... else:... block structure.

Technology A.5.4. Conditional statements.

The if:... elif:... else:... structure permits a program to execute different subroutines depending upon the state of various conditional variables. Consider the following example.

if cond1:
    # If cond1 evaluate to True, do the following:
    opt_function1(...)
elif cond2:
    # If cond1 evaluates to False but cond2 evaluates to True, do the
    # following:
    opt_function2(...)
else:
    # If none of the conditions in the original if or any subsequent
    # elif statements evaluates to True, then do the following:
    else_function(...)

After an if:... elif:... else:... block executes, the program does not repeat it (because it is a conditional statement, not an iteration) but returns to the same level of indentation as the original if: and continues the execution.

We have now put together enough pieces of programming that we can look at some interesting mathematical problems!

Subsection A.5.3 The Collatz Conjecture

This problem was introduced by Lothat Collatz in 1937. Define a mathematical sequence by the following rule: begin with any positive integer \(n\text{,}\) and set \(c_0 = n\text{.}\) Subsequent terms in the sequence are determined from the preceding terms according to this rule:

\begin{equation*} c_{n+1} = \begin{cases} 3c_n + 1, \amp c_n\text{ is odd}\\c_n/2, \amp c_n\text{ is even.}\end{cases} \end{equation*}

Conjecture A.5.5. The Collatz Conjecture.

No matter the choice of \(c_0\text{,}\) any such sequence will eventually contain the number 1.

This simple statement gives an easy programming exercise but has an interesting conclusion: no one knows whether or not the Collatz Conjecture is true! It is an open problem in combinatorics, which has defied the attempts at proof of some of the greatest mathematicians of the last 100 years.

def iterative_collatz(n):
    """An iterative version of the Collatz sequence which
        runs a maximum of 10000 steps."""
    output = [ n ]
    current_value = n
    for i in range(10000):
        if current_value % 2 == 0:
            current_value = current_value // 2
        else:
            current_value = 3 * current_value + 1
        output.append( current_value )
        if current_value == 1:
            return( output )
    return( output )

Listing A.5.6. A Python implementation of the Collatz sequence using a for loop.

Type the previous listing into a file called collatz.py in your directory for Python files, and then open IDLE. At the prompt, run import collatz and then run collatz(39). What is your result?

Remark A.5.7. Typing vs. copying and pasting code.

One of the best ways to learn programming is to simply learn by experimentation, but a minimal working knowledge of syntax and programming methods is needed before that is possible. Another very good way to learn to program is to manually type in code from another source, seeking to explain and understand it along the way. If you transcribe another person’s program into your own, try to put an explanatory comment on every line to see if you understand what the program is doing!

What might seem a better way to write a Collatz-sequence program would be to start building a sequence at the input number n and continue as long as the last element of the sequence is not 1, but there are several serious problems with that approach. First and foremost, if the Collatz conjecture is actually false, there is some input n for which that program would never terminate! Since all current research indicates that the Collatz conjecture is probably true, the other worse problem is that generating a long sequence uses up system memory in the computer, and eventually (for a long enough sequence) you could run out of memory and crash Python! The good news is that running a computer out of memory in this way causes no long-term problems; quitting Python is usually enough to solve the problem and allow the operating system to reallocate that memory.

Prev Top Next