Lesson 8
Functions and recursion

1. Functions

Recall that in mathematics the factorial of a number n is defined as n! = 1 ⋅ 2 ⋅ ... ⋅ n (as the product of all integer numbers from 1 to n). For example, 5! = 1 ⋅ 2 ⋅ 3 ⋅ 4 ⋅ 5 = 120. It is clear that factorial is easy to calculate, using a for loop. Imagine that we need in our program to calculate the factorial of various numbers several times (or in different places of code). Of course, you can write the calculation of the factorial once and then using Copy-Paste to insert it wherever you need it:

None

# compute 3!
res = 1
for i in range(1, 4):
    res *= i
print(res)

# compute 5!
res = 1
for i in range(1, 6):
    res *= i
print(res)

However, if we make a mistake in the initial code, this erroneous code will appear in all the places where we've copied the computation of factorial. Moreover, the code is longer than it could be. To avoid re-writing the same logic in programming languages there are functions.

Functions are the code sections which are isolated from the rest of the program and executed only when called. You've already met the function sqrt(), len() and print(). They all have something in common: they can take parameters (zero, one, or several of them), and they can return a value (although they may not return). For example, the function sqrt() accepts one parameter and returns a value (the square root of the given number). The print() function can take various number of arguments and returns nothing.

Now we want to show you how to write a function called factorial() which takes a single parameter — the number, and returns a value — the factorial of that number.

None

def factorial(n):
    res = 1
    for i in range(1, n + 1):
        res *= i
    return res

print(factorial(3))
print(factorial(5))

We want to provide a few explanations. First, the function code should be placed in the beginning of the program (before the place where we want to use the function factorial(), to be precise). The first line def factorial(n): of this example is a description of our function; the word factorial is an identifier (the name of our function). Right after the identifier, there goes the list of parameters that our function receives (in parentheses). The list consists of comma-separated identifiers of the parameters; in our case, the list consists of one parameter n. At the end of the row, put a colon.

Then goes the function body. In Python, the body must be indented (by Tab or four spaces, as always). This function calculates the value of n! and stores it in the variable res. The last line of the function is return res, which exits the function and returns the value of the variable res.

The return statement can appear in any place of a function. Its execution exits the function and returns specified value to the place where the function was called. If the function does not return a value, the return statement won't actually return some value (though it still can be used). Some functions do not need to return values, and the return statement can be omitted for them.

We'd like to provide another example. Here's the function max() that accepts two numbers and returns the maximum of them (actually, this function has already become the part of Python syntax).

10
20

def max(a, b):
    if a > b:
        return a
    else:
        return b

print(max(3, 5))
print(max(5, 3))
print(max(int(input()), int(input())))

Now you can write a function max3() that takes three numbers and returns the maximum of them.

None

def max(a, b):
    if a > b:
        return a
    else:
        return b

def max3(a, b, c):
    return max(max(a, b), c)

print(max3(3, 5, 4))

The built-in function max() in Python can accept various number of arguments and return the maximum of them. Here is an example of how such a function can be written.

None

def max(*a):
    res = a[0]
    for val in a[1:]:
        if val > res:
            res = val
    return res

print(max(3, 5, 4))

2. Local and global variables

Inside the function, you can use variables declared somewhere outside of it:

None

def f():
    print(a)

a = 1
f()

Here the variable a is set to 1, and the function f() prints this value, despite the fact that when we declare the function f this variable is not initialized. The reason is, at the time of calling the function f() (the last string) the variable a already has a value. That's why the function f() can display it.

Such variables (declared outside the function but available inside the function) are called global.

But if you initialize some variable inside of the function, you won't be able to use this variable outside of it. For example:

None

def f():
    a = 1

f()
print(a)

We receive error NameError: name 'a' is not defined. Such variables declared within a function are called local. They become unavailable after you exit the function.

What's really charming here is what happens if you change the value of a global variable inside of a function:

None

def f():
    a = 1
    print(a)

a = 0
f()
print(a)

This program will print you the numbers 1 and 0. Despite the fact that the value of the variable a changed inside the function, outside the function it remains the same! This is done in order to «protect» global variables from inadvertent changes of function. So, if some variable is modified inside the function, the variable becomes a local variable, and its modification will not change a global variable with the same name.

More formally: the Python interpreter considers a variable local to the function, if in the code of this function there is at least one instruction that modifies the value of the variable. Then that variable also cannot be used prior to initialization. Instructions that modify the value of a variable — the operators =, +=, and usage of the variable as a loop for parameter. However, even if the changing-variable statement is never executed, the interpreter cannot check it, and the variable is still local. An example:

None

def f():
    print(a)
    if False:
        a = 0

a = 1
f()

An error occurs: UnboundLocalError: local variable 'a' referenced before assignment. Namely, in the function f() the identifier a becomes a local variable, since the function contains the command which modifies the variable a. The modifying instruction will never be executed, but the interpreter won't check it. Therefore, when you try to print the variable a, you appeal to an uninitialized local variable.

If you want a function to be able to change some variable, you must declare this variable inside the function using the keyword global:

None

def f():
    global a
    a = 1
    print(a)

a = 0
f()
print(a)

This example will print the output of 1 1, because the variable a is declared as global, and changing it inside the function causes the change of it globally.

However, it is better not to modify values of global variables inside a function. If your function must change some variable, let it return this value, and you choose when calling the function explicitly assign a variable to this value. If you follow these rules, the functions' logic works independent of the code logic, and thus such functions can be easily copied from one program to another, saving your time.

For example, suppose your program should calculate the factorial of the given number that you want to save in the variable f. Here's how you should not do it:

5

def factorial(n):
    global f
    res = 1
    for i in range(2, n + 1):
        res *= i
    f = res

n = int(input())
factorial(n)
print(f)
# doing other stuff with variable f

This is the example of bad code, because it's hard to use another time. If tomorrow you need another program to use the function "factorial", you will not be able to just copy this function from here and paste in your new program. You will have to ensure that that program doesn't contain the variable f.

It is much better to rewrite this example as follows:

5

# start of chunk of code that can be copied from program to program
def factorial(n):
    res = 1
    for i in range(2, n + 1):
        res *= i
    return res
# end of piece of code

n = int(input())
f = factorial(n)
print(f)
# doing other stuff with variable f

It is useful to say that functions can return more than one value. Here's the example of returning a list of two or more values:

return [a, b]

You can call the function of such list and use it in multiple assignment:

n, m = f(a, b)

3. Recursion

As we saw above, a function can call another function. But functions can also call itself! To illustrate it, consider the example of the factorial-computing function. It is well known that 0!=1, 1!=1. How to calculate the value of n! for large n? If we were able to calculate the value of (n-1)!, then we easily compute n!, since n!=n⋅(n-1)!. But how to compute (n-1)!? If we have calculated (n-2)!, then (n-1)!=(n-1)⋅(n-2)!. How to calculate (n-2)!? If... In the end, we get to 0!, which is equal to 1. Thus, to calculate the factorial we can use the value of the factorial for a smaller integer. This calculation can be done using Python:

None

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

print(factorial(5))        

The situation when function calls itself is called recursion, and such function is called recursive.

Recursive functions are powerful mechanism in programming. Unfortunately, they are not always effective and often lead to mistakes. The most common error is infinite recursion, when the chain of function calls never ends (well, actually, it ends when you run out of free memory in your computer). An example of infinite recursion:

def f():
    return f()

1. Incorrect stopping condition. For example, if in the factorial-calculating program we forget to put the check if n == 0, then factorial(0) will call factorial(-1), that will call factorial(-2), etc.
2. Recursive call with incorrect parameters. For example, if the function factorial(n) calls the function factorial(n), we will also obtain an infinite chain of calls.

Therefore, when coding a recursive function, it is first necessary to ensure it will reach its stopping conditions — to think why your recursion will ever end.