Functions and Recursion, An Animated Lesson

Lesson by Adnan, computer science lecturer  ·  aitrendblend editorial team  ·  Computer Science Education  ·  October 2026  ·  Reading time about 22 minutes

Functions and Recursion
An Animated Lesson

Who this lesson is for and how to use it

This is the ninth lesson in our Computer Science Education series. It follows directly from Your First Program, which ended by promising functions, and it builds on the call stack idea from the data structures lesson. Students who have met variables, loops and conditions are ready for it. Those who have not should start with the programming lesson, or with How a Computer Works for the bigger picture.

The lesson suits grades nine to twelve and first year college students. Recursion has a reputation for being hard, but it is usually taught too abstractly. Here every idea has a picture first. Students can solve the Towers of Hanoi with their hands before they see why the recursive solution works, and they can watch every frame of the call stack instead of imagining it.

Learning objectives

After three periods, a student should be able to do the following five things without notes.

1. Write a function with parameters and a return value, and explain why functions reduce repetition.
2. Predict the result of composing two functions in either order.
3. Identify the base case and the recursive case in a recursive function.
4. Draw the call stack for a small recursive call such as factorial of 4.
5. Explain the recursive solution to the Towers of Hanoi and why it needs 2 to the power n minus 1 moves.

Functions, machines with names

A function is a named block of code that does one job. It takes inputs, called parameters, does some work, and hands back a result using the word return. Students have used functions from the start without noticing. In Python, print and len are functions written by someone else. Writing your own is how programmers stop repeating themselves.

The best mental picture is a machine. A number goes in one side, the machine does something to it, and a new value comes out the other side. The same input always gives the same output, which is what makes functions so easy to test. The idea is old. In 1951 Maurice Wilkes, David Wheeler and Stanley Gill described a library of subroutines for the EDSAC computer at Cambridge, reusable pieces of code that any program could call, and the trick Wheeler invented for jumping into a subroutine and back became a foundation of all later programming.

Pick two machines below, type a number and press Run. Then swap the order. Students are often surprised that double then square gives a different answer from square then double, which is an early lesson that the order of operations in a program matters as much as the operations themselves.

Recursion, a function that calls itself

Here is a definition that sounds like a trick. The factorial of a number, written with an exclamation mark, is that number multiplied by the factorial of the number below it. So 5 factorial is 5 times 4 factorial, which is 4 times 3 factorial, and so on down to 1 factorial, which is simply 1. A definition that refers to itself is called recursive, and a function written this way calls itself.

Two parts make recursion work. The recursive case breaks the problem into a smaller version of itself. The base case is the version so small it can be answered directly, without another call. Without a base case the function would call itself forever. Russian nesting dolls are the classic picture. Each doll contains a smaller doll, until you reach the tiny solid one in the middle, which is the base case.

Programming languages did not always allow this. LISP, created by John McCarthy at MIT in 1958, made recursion central to the way programs were written, and the ALGOL 60 language that followed brought it into the mainstream. Today every common language supports it.

Watching the call stack

How does a computer keep track of a function that has called itself five times and is still waiting for answers? It uses the call stack from our data structures lesson. Each call pushes a frame onto the stack recording its own value of n and where to continue. When the base case returns, the frames pop off one by one, each multiplying the answer it receives by its own n. Step through the lab below, then switch off the base case and watch what goes wrong.

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

With the base case on, the stack grows to five frames for factorial of 5 and then shrinks back to nothing as the answers flow upward, 1, 2, 6, 24 and finally 120. With the base case off, the function keeps calling itself with 0, then minus 1, then minus 2, and the stack grows until Python stops the program with a RecursionError. That error is the software version of the stack overflow students met in the data structures lesson.

To understand recursion, trust that the smaller call works, and focus only on the one step in front of you.From this lesson, period two

Towers of Hanoi, a puzzle made for recursion

In 1883 the French mathematician Édouard Lucas sold a puzzle with a legend attached. Monks in a temple, he said, were moving 64 golden discs between three pegs, one disc at a time, never placing a larger disc on a smaller one, and when they finished the world would end. Try the puzzle with four discs first. Click a peg to pick up its top disc, then click another peg to drop it.

The recursive solution is breathtakingly short. To move n discs from the left peg to the right peg, first move the top n minus 1 discs to the middle peg, using the same method. Then move the biggest disc to the right peg. Then move the n minus 1 discs from the middle onto it, using the same method again. The base case is a single disc, which simply moves. Three lines of logic solve the puzzle for any number of discs.

Counting the moves reveals something remarkable. Each extra disc doubles the work and adds one, so n discs need 2 to the power n minus 1 moves. Four discs need 15, ten need 1,023, and the monks’ 64 discs need more than eighteen quintillion moves. At one move per second that would take about 585 billion years, many times the age of the universe, so the legend’s prediction is safe.

Fractals, recursion you can see

Recursion is not only for numbers and puzzles. A tree can be drawn with one recursive rule. Draw a branch, then from its tip draw two smaller trees, one leaning left and one leaning right. Each of those does the same, and so on until the branches are tiny. Shapes built this way, where each part looks like a smaller copy of the whole, are called fractals, a word the mathematician Benoit Mandelbrot introduced in 1975. Ferns, rivers, lightning and the veins in a leaf all show this kind of pattern in nature.

Move the depth slider from 8 to 11 and the number of branches jumps from 255 to 2,047, while the code that draws them does not change by a single character. That is the power and the danger of recursion. A tiny rule can produce enormous output, which is wonderful for drawing trees and terrible if the work explodes when you did not expect it.

When recursion wastes effort

Recursion can also be shockingly inefficient if used carelessly. The Fibonacci sequence, 0, 1, 1, 2, 3, 5, 8 and onward, where each number is the sum of the two before it, appeared in Indian mathematics centuries before Leonardo of Pisa introduced it to Europe in his book Liber Abaci in 1202. Its definition is naturally recursive, and the obvious recursive function works, but it is painfully slow. To compute the 25th number it makes more than 240,000 calls, because it works out the same smaller numbers again and again.

The fix is called memoization, which simply means remembering answers you have already computed. With a small cache the same function finds the 90th Fibonacci number instantly. The companion code shows both versions side by side. This connects to the Big O ideas from our algorithms lesson. The naive version grows exponentially, while the remembering version grows in a straight line.

Where students meet these ideas

Functions are everywhere in real software. Every button in an app calls a function, and libraries such as the ones in our guide to open source machine learning frameworks are huge collections of functions written by other people. Recursion appears wherever data nests inside itself. File explorers walk folders inside folders recursively, web browsers read nested HTML recursively, merge sort and quick sort from our algorithms lesson split lists recursively, and the tree structures from our data structures lesson are searched recursively. Even neural networks from our AI lesson are built from layers of functions composed together, exactly like the machines in Lab 1, and our article on shallow ReLU networks studies networks that are, mathematically, compositions of simple functions.

Misconceptions students bring to class

• print and return do the same thing. print shows a value to a person. return hands it back to the code, which can keep using it.
• A recursive function runs all its calls at once. The calls happen one after another and wait on the stack, as Lab 2 shows.
• Recursion is always slow. It is slow only when it repeats work. With memoization, or a good design such as merge sort, it can be very fast.
• The base case is optional. Without it the function never stops, and the program crashes with a stack overflow.
• Anything recursive is too hard for beginners. Recursion is hard to imagine, not hard to understand. Seeing it step by step removes most of the mystery.

Where this lesson simplifies the truth

The function machines take one number and return one number, while real functions can take many parameters, return several values and change data outside themselves. The call stack lab shows only n and the waiting status, while real frames also store local variables and a return address, the same idea as the program counter in our first lesson. Python’s default limit on recursion depth is around a thousand calls, much more than the lab’s small demonstration, and other languages handle deep recursion differently.

The fractal tree uses a fixed angle and shrink ratio. Realistic trees in films and games add randomness and many more rules. None of these details change the central ideas, a named machine for functions, and a smaller copy plus a base case for recursion.

Bringing it all together

The main achievement of this lesson is two new tools for thinking. Functions let students name a piece of logic and reuse it, so programs become collections of small, trustworthy machines instead of one long list of instructions. Recursion lets them solve a problem by trusting a smaller version of the same problem, which turns puzzles that look impossibly complicated into three lines of logic.

The conceptual shift is from writing every step yourself to building on steps you have already defined. Professional software is written almost entirely this way, functions calling functions, some of them recursively, layered many levels deep. Once students see that, large programs stop looking like walls of code and start looking like trees of small, understandable pieces.

The ideas tie the series together. The call stack lives in the memory from How a Computer Works. Recursive splitting powers merge sort and quick sort. Trees from the data structures lesson and graph search are naturally recursive. And neural networks are compositions of functions trained by gradient descent, itself a loop of function calls.

The lesson has honest limits. It does not cover functions with several return values, functions that change shared data, or converting recursion into loops, each of which matters in larger programs. Teachers with stronger classes can extend period three by having students write a recursive function to sum a list or reverse a word, and teachers without computers can teach the whole unit with the human function game, nesting dolls and paper Towers of Hanoi.

A natural next lesson is data and files, reading and writing information so programs can remember things between runs. For now, the student who copied the same three lines into five places knows a better way, and she has watched a single rule grow a tree with two thousand branches.

Companion Python code for the classroom

The program below uses every idea from the lesson. It defines functions with parameters, a default value and return, composes functions in both orders, computes factorial recursively, compares a slow recursive Fibonacci with a remembering version, generates the full list of Towers of Hanoi moves, and counts the branches in a fractal tree.

# Functions and Recursion, companion code for the aitrendblend lesson
# Runs on any Python 3 installation. No extra libraries needed.
from functools import lru_cache


# Part 1. Functions are named, reusable machines
def celsius_to_fahrenheit(c):
    return c * 9 / 5 + 32


def grade(marks, pass_mark=40):          # pass_mark has a default value
    return "Pass" if marks >= pass_mark else "Fail"


def compose(f, g):
    """Feed the output of f straight into g, like joining two machines."""
    return lambda x: g(f(x))


double = lambda x: x * 2
square = lambda x: x * x


# Part 2. Recursion, a function that calls itself
def factorial(n):
    if n <= 1:                # base case, stop here
        return 1
    return n * factorial(n - 1)   # smaller version of the same problem


calls = 0


def fib_slow(n):
    global calls
    calls += 1
    return n if n < 2 else fib_slow(n - 1) + fib_slow(n - 2)


@lru_cache(maxsize=None)
def fib_fast(n):              # remembers answers it has already worked out
    return n if n < 2 else fib_fast(n - 1) + fib_fast(n - 2)


# Part 3. Towers of Hanoi
def hanoi(n, source="A", spare="B", target="C", moves=None):
    if moves is None:
        moves = []
    if n == 0:
        return moves
    hanoi(n - 1, source, target, spare, moves)    # clear the way
    moves.append((n, source, target))             # move the biggest disc
    hanoi(n - 1, spare, source, target, moves)    # stack the rest on top
    return moves


# Part 4. A fractal tree, counted rather than drawn
def branches(depth):
    return 0 if depth == 0 else 1 + 2 * branches(depth - 1)


# Smoke test
if __name__ == "__main__":
    print("30 C is", celsius_to_fahrenheit(30), "F")
    print("Grades:", grade(55), grade(35), grade(35, pass_mark=33))
    print("double then square of 3:", compose(double, square)(3),
          "| square then double:", compose(square, double)(3))

    print("\n5! =", factorial(5))
    n = 25
    slow = fib_slow(n)
    print(f"fib({n}) = {slow}, the slow version made {calls:,} calls")
    print(f"fib(90) with memory = {fib_fast(90):,}")

    moves = hanoi(3)
    print("\nHanoi with 3 discs:", len(moves), "moves", moves[:3], "...")
    print("Hanoi with 10 discs needs", len(hanoi(10)), "moves, which is 2^10 - 1")
    print("A fractal tree of depth 8 has", branches(8), "branches")

    assert celsius_to_fahrenheit(100) == 212
    assert compose(double, square)(3) == 36 and compose(square, double)(3) == 18
    assert factorial(5) == 120 and slow == 75025
    assert len(hanoi(10)) == 2 ** 10 - 1 and branches(8) == 255
    print("\nAll checks passed.")

When you run it, 30 degrees Celsius should convert to 86 Fahrenheit, double then square of 3 should give 36 while square then double gives 18, factorial of 5 should be 120, the slow Fibonacci function should make 242,785 calls to find the 25th number, Hanoi with 10 discs should take 1,023 moves, and the final line should report that all checks passed. A good extension task is to write a recursive function that counts down from any number to zero and then prints Lift off.

Check your understanding

Six questions cover the whole lesson. Choose an answer for each and press Check answers to see which were right, with a short explanation for each.

Frequently asked questions

Related reading on aitrendblend