Functions & Recursion

Anatomy of a function

def area(width, height):        # header
    """Return the area of a rectangle."""
    result = width * height    # body (indented)
    return result              # send the answer back

print(area(3, 4))              # call: prints 12

You have been calling functions all year

print(), len(), input(), int(), and range() are all functions that someone else wrote. Now you get to write your own, and they work exactly the same way: a name, parentheses, arguments in, and (often) a value out.

A function is like a recipe card

Writing the card (def) does not cook anything. Cooking happens when you follow the card (call it), and you can follow the same card as many times as you want with different ingredients (arguments).

Naming tip: start function names with a verb, since functions do things: calculate_tax, print_report, is_even.

Defining is not running: you must call it

def greet():
    print("Hello!")
    print("Welcome to class.")

greet()     # runs the body
greet()     # runs it again
greet       # no parentheses: nothing happens

The order Python runs things

def greet():              # 1. creates greet; body skipped for now
    print("Hello!")       # 4. and 6. run only during a call
print("Start")            # 2. the first thing printed
greet()                   # 3. jump into greet, then come back
greet()                   # 5. jump in again, then come back
print("End")              # 7.

Python reads top to bottom, but a def just stores the function. The body runs only when the program reaches a call. After the body finishes, Python returns to the line right after the call and keeps going.

Without parentheses, greet just refers to the function, like saying a recipe's name without cooking it. In the interactive shell it shows something like <function greet at 0x...>.

Parameters and arguments

def greet(name, greeting="Hello"):
    return greeting + ", " + name + "!"

greet("Ava")                    # 'Hello, Ava!'
greet("Ava", "Hi")              # 'Hi, Ava!'
greet(greeting="Yo", name="Cy") # 'Yo, Cy!'

What happens at the moment of the call

For greet("Ava", "Hi"), Python does the equivalent of:

name = "Ava"        # first argument to first parameter
greeting = "Hi"     # second argument to second parameter
# ...then runs the body

The argument can be any expression: a variable, math, or even another call. greet(input("Name? ")) works: Python gets the input first, then passes it in.

Variable names do not have to match. If you call greet(student), the value of student is copied into the parameter name. The names outside and inside the function are separate.

return sends a value back

def add(a, b):
    return a + b          # gives the answer back

def show_sum(a, b):
    print(a + b)          # only displays it

total = add(2, 3)         # total is 5
print(total * 10)         # 50

result = show_sum(2, 3)   # prints 5
print(result)             # None

Why return is more useful than print

A returned value can be used again. You can combine calls in bigger expressions, store results, or pass one function's answer into another:

total = area(3, 4) + area(1, 2)    # 12 + 2 = 14
big = area(area(2, 3), 2)          # area(6, 2) = 12

A function that only prints is a dead end: the answer appears on screen, but your program cannot do anything else with it.

Returning more than one value

return low, high sends back a tuple. Unpack it at the call: smallest, largest = min_max(scores).

Using return to stop early:

def check_age(age):
    if age < 0:
        return "Invalid age"   # the function ends here
    return "OK"

No return? You get None

How None sneaks in

The most common way is a function with return only inside an if:

def grade(score):
    if score >= 90:
        return "A"
    elif score >= 80:
        return "B"

print(grade(75))    # None, because no return ran

Make sure every path through the function reaches a return. Adding an else: return "C or lower" (or a final return at the end) fixes it.

Spotting it: if you see None printed where you expected a value, or an error mentioning NoneType, a function on that line probably did not return anything.

Predict the output: value or None?

For each program, choose what Python prints, then click Check. Practice only; nothing is recorded.

How to predict

1. Find each call and trace into the function with the argument values.
2. Follow the ifs to see which lines actually run.
3. Did a return value run? That is the result. Otherwise the result is None.
4. Remember a print inside the function shows its text during the call, before the caller prints the result.

Local variables live inside the call

def double(n):
    answer = n * 2      # local
    return answer

print(double(5))       # 10
print(answer)          # NameError: name 'answer' is not defined

Why local variables are a good thing

Because each function keeps its own variables, you can use a name like total in ten different functions without them interfering with each other. Each function is a closed box: values go in through parameters and come out through return.

The UnboundLocalError trap

score = 0
def add_point():
    score += 1      # error: score is local here, but has no value yet

Because the function assigns to score, Python treats it as local, so it cannot read the outside score first. The clean fix is to pass it in and return it:

def add_point(score):
    return score + 1
score = add_point(score)

Docstrings: instructions for the user

def perimeter(width, height=1):
    """Return the perimeter of a rectangle.

    If height is left out, it is 1.
    """
    return 2 * (width + height)

What makes a good docstring

• Say what it returns or does, in one sentence: "Return the average of a list of scores."
• Mention the parameters if it is not obvious what they are: "scores is a list of numbers."
• Mention special cases: "Return 0 if the list is empty."

def average(scores):
    """Return the average of a list of numbers.

    Return 0 if scores is empty.
    """
    if len(scores) == 0:
        return 0
    return sum(scores) / len(scores)

Someone should be able to use your function correctly by reading only the docstring.

Reading docstrings with help() and __doc__

>>> help(area)
Help on function area in module __main__:

area(width, height)
    Return the area of a rectangle.

>>> area.__doc__
'Return the area of a rectangle.'

Why write docs you can print?

Professional programmers use other people's functions all day without reading their code. They type help(something) to find out what it does and what arguments it needs. When your functions have docstrings, they work the same way for your classmates (and for future you).

Try it on built-ins: help(print) shows that print has options like sep and end. help(str.upper) explains the string method you already know.

pydoc: documentation from the command line

Keeping test code from running

Programmers often put test calls under a special if so they run only when the file is run directly, not when it is imported (by pydoc or another program):

def area(width, height):
    """Return the area of a rectangle."""
    return width * height

if __name__ == "__main__":
    print(area(3, 4))     # runs only when you run this file itself

__name__ is a special variable that is "__main__" when the file is the one you ran, and the module's name when it is imported.

Recursion: a function that calls itself

def countdown(n):
    if n == 0:                 # base case
        print("Liftoff!")
        return
    print(n)
    countdown(n - 1)           # recursive case

countdown(3)

Trace countdown(3)

1. countdown(3): 3 is not 0, so it prints 3 and calls countdown(2).
2. countdown(2): prints 2, calls countdown(1).
3. countdown(1): prints 1, calls countdown(0).
4. countdown(0): base case! Prints Liftoff! and returns.
5. Each earlier call then finishes, in reverse order: 1, then 2, then 3.

Two questions for any recursive function: "What is the smallest case I can answer right away?" (the base case) and "How do I make the problem one step smaller?" (the recursive case).

Tracing a recursive call: factorial

def factorial(n):
    """Return n! for a whole number n of 1 or more."""
    if n == 1:
        return 1                      # base case
    return n * factorial(n - 1)       # recursive case

The "trust the smaller call" idea

When writing return n * factorial(n - 1), do not try to picture every call at once. Just trust that factorial(n - 1) gives the right answer for the smaller problem, and ask: "If I had that answer, how would I finish the job?" For factorial, multiply by n.

Another example: adding up a list

def total(nums):
    """Return the sum of a list of numbers."""
    if nums == []:
        return 0                        # empty list: sum is 0
    return nums[0] + total(nums[1:])    # first item + sum of the rest

print(total([4, 5, 6]))    # 15

The list gets one item shorter on every call, so it is guaranteed to reach the empty-list base case.

When recursion never stops

RecursionError: maximum recursion depth exceeded

Check every recursive function with this list

1. Is there a base case that returns without calling itself?
2. Does every call move closer to it? (n − 1 heading down to 1, a list getting shorter.)
3. Can any input skip past it? n == 1 misses 0 and negative numbers; n <= 1 catches them.

The loop version

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

Same answers, no call stack. For simple counting problems, a loop is usually the more practical choice; recursion is a powerful way of thinking that becomes very useful for problems shaped like trees, mazes, and folders inside folders.

Common mistakes

Sort the error

• NameError: the function is called before its def, the name is misspelled, or you used a local variable outside its function.
• TypeError ... argument(s): count the arguments in the call and the parameters in the def.
• TypeError ... NoneType: a function returned None (no return on that path, or it only printed).
• RecursionError: check the base case and the step toward it.
• Nothing happens: missing parentheses on the call.

Check yourself

Choose an answer, then click Check. Practice only; nothing is graded or recorded.

Cheat sheet

def area(w, h=1):
    """Return w times h."""
    return w * h

area(3, 4)        # 12
area(3)           # 3 (h=1)
area(h=2, w=5)    # 10
x = area(2, 2)    # store it

help(area)
area.__doc__
# terminal:
python -m pydoc shapes

def factorial(n):
    if n <= 1:        # base case
        return 1
    return n * factorial(n - 1)

Remember:

• def creates a function; parentheses call it
• Parameters are names in the def; arguments are values in the call
• If you need the answer later, return it, do not just print it
• Put a """docstring""" on the first line of every function
• Every recursive function needs a base case and a step toward it

Key words to know

def · call / invoke · parameter · argument (positional, keyword, default) · return · None · local / global · docstring · help() / pydoc · recursion · base case · call stack