Functions and recursion

Introduction

A function is a named block of code that runs only when you call it. Each call gets its own frame: a private set of variables that disappears when the call returns.

Without functions, every program would be one long list of lines, and the same code would be copied again and again. A function gives a piece of work a name, so you can fix it in one place and read the main program almost like a list of steps.

How it works

Defining and calling a function

def add(a, b):
    x = a + b
    return x

total = add(5, 3)
print(total)

Step through it slowly:

1. Line 1 only defines add. Nothing inside it runs yet; the objects panel shows a function add(a, b).
2. Line 5 calls add(5, 3). A new frame for add appears on top of the call stack, with a = 5 and b = 3.
3. Inside the frame, x = a + b works out 5 + 3 → 8.
4. return x sends 8 back. The frame shows returns 8, then disappears, and line 5 finishes by storing 8 in total.

The variables a, b and x exist only inside add's frame. After the call, the global frame cannot see them.

Syntax

def add(a, b):
    return a + b

result = add(2, 3)

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

Example

A recursive function solves a problem by calling itself on a smaller version of it. It needs a base case that stops the calls.

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

print(factorial(4))

Watch the call stack grow: factorial(4) calls factorial(3), which calls factorial(2), then factorial(1). That is four frames of the same function, each with its own n. factorial(1) hits the base case and returns 1. Then each frame returns in turn: 1, 2, 6, 24.

Line by line

1. def factorial(n): defines the function. Nothing inside it runs yet.
2. The last line calls factorial(4), which needs factorial(3) before it can finish.
3. Each new call has its own n, and they wait on the stack until n is 1.
4. factorial(1) meets the base case and returns 1.
5. The waiting calls finish in turn, multiplying up to 2, 6 and finally 24.

Expected result

24

In the real world

Every button on a website runs a function, and libraries are collections of functions someone else wrote and tested. Recursion suits data that contains smaller copies of itself, such as folders inside folders or comments under comments.

Common mistakes

• No base case, or one that is never reached: the calls never stop and Python raises RecursionError.
• Forgetting return: the function gives back None, and the caller's variable becomes None.
• Expecting a variable created inside a function to exist outside it. It lives only in the function's frame.

Best practices

• Give each function one job, and a name that describes it.
• Return results rather than printing them inside the function.
• Check that each recursive call moves closer to the base case.

Summary

def creates a function, and each call gets a new frame with its own variables. return sends a value back, and a function without it gives None. A recursive function calls itself on a smaller problem and needs a base case.

Practice

Write a recursive function sum_to(n) that returns 1 + 2 + … + n. Visualize sum_to(4) and check that the stack holds four frames at its deepest point.

Mark lesson complete