IB COMPUTER SCIENCE | B2.4.4 Recursion (HL)

Lesson objective

Explain recursion through base cases, smaller subproblems and call-stack behaviour, and connect its applications to advantages, time complexity and memory limitations.

Learn

B2.4.4 | RECURSION (HL ONLY)

01 | SOLVE A SMALLER VERSION OF THE SAME PROBLEM

Imagine counting the people in a queue. You could count everyone yourself, or ask the person behind you how many people remain from their position and add one. Each person asks the same question about a shorter queue, until the final person can answer directly.

Recursion occurs when a function calls itself, directly or through other functions. A recursive solution expresses a problem in terms of smaller instances of the same kind of problem.

This is an HL-only lesson. We explain the mechanism and its applications, including quicksort, tree traversal and fractal images. The next objective develops construction and tracing of simple non-branching recursive programs in more detail.

02 | TWO ESSENTIAL PARTS

Part Role Queue analogy
Base case Solve a sufficiently small case without another recursive call No one remains: count 0
Recursive case Reduce the problem and use the smaller result Count remaining people, then add 1

A base case stops further descent on that path. A recursive case must move toward a base case for the permitted inputs. Merely including an if statement somewhere does not establish termination.

Also check correctness: solving a smaller problem must actually help produce the required larger answer. A function can terminate and still return the wrong result.

03 | A FAMILIAR EXAMPLE: FACTORIAL

For a non-negative integer n, n! multiplies the positive integers from 1 to n. For example, 4! = 4 × 3 × 2 × 1 = 24. By definition, 0! = 1.

The useful recursive relationship is n! = n × (n − 1)! for n > 0. To find 4!, ask for 3!, then multiply its answer by 4. The smaller question has exactly the same form.

Here n is a non-negative integer. A negative value does not progress toward 0 by repeatedly subtracting 1; the input domain and progress rule must agree.

04 | READ THE FUNCTION ONE CASE AT A TIME

def factorial(n):
    if n < 0:
        raise ValueError("Use a non-negative integer")
    if n == 0:
        return 1
    return n * factorial(n - 1)

print(factorial(4))

The output is 24. This function assumes n is an integer and explicitly rejects negative integer values. n == 0 is the base case, returning 1. For positive n, the return expression requires the result of factorial(n − 1).

The caller cannot finish multiplying by n until the smaller call returns. Recursion is therefore more than restarting a loop: earlier calls can remain active with unfinished work.

Do not replace return n * factorial(n − 1) with factorial(n − 1) alone. Calling the smaller function without using and returning its result would not produce the promised factorial answer.

05 | THE CALLER PAUSES, IT DOES NOT DISAPPEAR

Calling factorial(4) creates an active call with local n = 4. It needs 4 × factorial(3), so it pauses while factorial(3) runs. The second call has its own local n = 3.

The original n has not been overwritten by 3. These are separate local bindings in separate active calls of the same function. Each call retains the information needed to resume its calculation.

A stack frame records call-related state, such as parameters, local values and where to resume. Active calls are managed in a call stack.

06 | BUILDING THE CALL STACK

Call entered Local n Work waiting for smaller result
factorial(4) 4 4 × factorial(3)
factorial(3) 3 3 × factorial(2)
factorial(2) 2 2 × factorial(1)
factorial(1) 1 1 × factorial(0)
factorial(0) 0 No recursive work; return 1

At the deepest point, five factorial calls are active: n = 4, 3, 2, 1 and 0. The latest call is at the top of the stack and returns first.

A call stack follows last in, first out. Do not read this table as five independent tasks running in parallel; it is one chain of synchronous calls.

07 | UNWINDING: RETURN THROUGH THE WAITING CALLS

Call completing Smaller returned value Calculation Value returned
factorial(0) Not needed Base case 1
factorial(1) 1 1 × 1 1
factorial(2) 1 2 × 1 2
factorial(3) 2 3 × 2 6
factorial(4) 6 4 × 6 24

Unwinding means returning through the active calls as their remaining work completes. The result of factorial(0) is only the starting answer, not the answer to the original factorial(4) call.

Each return removes that call’s active frame and resumes its caller. Only when factorial(4) returns does the outer print receive 24.

08 | INTERACTIVE: SEE CALLS AND RETURNS

Choose a whole-number n from 0 to 7. Step into each call, reach the base case, then watch each multiplication complete. Frames are listed with the newest active call first. This models the supplied factorial function; it does not execute arbitrary code.

Before each step, predict whether the stack will grow or shrink. Notice that the deepest call has the smallest n, while the final returned result belongs to the largest original n.

09 | WHAT MAKES THE RECURSION SAFE TO FINISH?

For valid integer n ≥ 0, each recursive call reduces n by 1. This non-negative integer cannot decrease indefinitely without reaching 0, so the base case is eventually reached.

This argument establishes mathematical termination. In a real runtime, a very deep valid input can still exceed available stack resources or a recursion-depth limit before finishing.

A missing base case, an unreachable base case or a recursive argument that does not move toward it can all prevent normal termination. Check the domain, the reduction and every recursive path.

10 | RECOGNIZE BROKEN RECURSION

Mistake Why it fails Repair
Call factorial(n) again Problem size does not decrease Use a justified smaller argument
Stop only at 0 but allow negative inputs Subtracting 1 moves farther from the base Reject negatives or redesign the domain
Return 0 for factorial(0) All products become 0 Use the correct base result 1
Omit the return of the computed result Caller can receive None Return the promised answer
Assume the base ends the whole program Waiting calls still need to finish Trace unwinding as well as descent

An incorrect recursive function may raise an error, run too deeply or quietly calculate the wrong result. A base case is necessary for ordinary terminating recursion but does not by itself prove correctness.

11 | RECURSION AND ITERATION CAN EXPRESS THE SAME JOB

def factorial_iterative(n):
    if n < 0:
        raise ValueError("Use a non-negative integer")
    result = 1
    for value in range(1, n + 1):
        result = result * value
    return result

print(factorial_iterative(4))

Both factorial versions return 24 and assume integer input. The loop retains one running result, while the recursive version retains a chain of active calls with pending multiplications.

Under a unit-cost arithmetic model, both take O(n) time. The recursive version uses O(n) active-call space; the iterative version uses O(1) auxiliary variable space in that simplified model.

The integer result itself grows with n, so real big-integer arithmetic and storage are not constant-cost for arbitrarily large factorials. State the model when using these introductory bounds.

12 | WHEN RECURSION FITS THE PROBLEM

Recursion is especially useful when the data or task already has smaller self-similar parts: a tree has subtrees, a folder contains subfolders, and a fractal repeats a shape at smaller scales.

The function can express “perform the same operation on each smaller part” without manually writing logic for every possible depth. That can make a solution clearer and easier to maintain.

A simple fixed-count repetition may be clearer as a loop. Recursion is a design tool whose usefulness depends on the structure, clarity and resource constraints of the problem.

13 | A TREE CONTAINS SMALLER TREES

A binary tree consists of nodes, each with at most a left child and a right child. Either child can itself be the root of a smaller binary tree. An empty child reference represents no subtree.

This gives a natural recursive shape: stop when the subtree is empty; otherwise process the current node and recursively visit its child subtrees.

A leaf has no children. An empty subtree is not the same as a leaf: the leaf is still a real node that may need processing.

14 | TREE TRAVERSAL: VISIT EVERY NODE

Example structure Node label Children
Root A Left B; right C
Left subtree B Left D; no right child
Right subtree C No children
Left leaf D No children

A preorder traversal processes the node first, then its left subtree, then its right subtree. For this tree the order is A, B, D, C.

The base case is an empty subtree: do nothing and return. After visiting all of B’s subtree, the root’s waiting call continues with C.

Other traversal orders move the current-node action: inorder visits left, node, right; postorder visits left, right, node. An inorder traversal gives sorted keys only when the tree obeys the appropriate binary-search-tree ordering rule.

15 | TREE COST DEPENDS ON NODE COUNT AND HEIGHT

A complete traversal that does constant work per node is O(n) time for n nodes. The deepest active chain depends on tree height h, so a recursive depth-first traversal uses O(h) call-stack space.

A balanced tree has height O(log n), while a chain-like tree can have height O(n). Therefore the same traversal can need logarithmic or linear stack depth depending on the shape.

If you collect all visited labels in a new list, that output adds O(n) storage. Distinguish stack space from output storage when stating the memory cost.

16 | FRACTALS: REPEAT A SMALLER SHAPE

A branching image can be drawn by drawing one segment, then drawing two shorter branches from its endpoint. Each branch repeats the same rule at a smaller size.

A base case stops at a chosen depth or minimum segment length. Without that limit, a mathematical recursive description may imply endlessly smaller detail, which a finite display and runtime cannot produce.

Here depth 0 draws one segment; depth 1 draws that segment and two children. This convention matters when counting the branches.

17 | INTERACTIVE: A FINITE RECURSIVE TREE IMAGE

Select a depth to see the repeated branching rule. Each segment makes two shorter child segments unless its remaining depth is 0. The image is generated with exact geometric code, and the counts describe this particular two-branch rule.

At depth d, the segment count is 1 + 2 + … + 2ᵈ = 2^(d + 1) − 1. The total drawing work grows exponentially with depth for this branching rule, even though the longest active call chain grows only linearly with depth.

18 | QUICKSORT: PARTITION AND RECURSE

Quicksort is a divide-and-conquer sorting algorithm. Choose a pivot, partition the data according to that pivot, then recursively sort the resulting smaller parts. A partition with fewer than two items is already sorted.

For a conceptual three-way partition of [5, 2, 7, 3, 1] around pivot 3: smaller values are [2, 1], equal values are [3], and larger values are [5, 7]. Recursively sort the smaller and larger groups to obtain [1, 2], [3], [5, 7].

This is a conceptual grouping example, not a claim that all quicksort implementations allocate three new lists. In-place partition schemes rearrange an existing array and have different details.

19 | WHY BALANCED PARTITIONS HELP

When quicksort repeatedly divides the items into reasonably balanced parts, there are about log₂ n levels of recursive division. The total partition work across a level is O(n), giving O(n log n) time in the balanced case.

If a pivot repeatedly leaves one large part of size n − 1 and almost nothing on the other side, the work resembles n + (n − 1) + … + 1, giving O(n²) worst-case time.

Average or expected O(n log n) needs an appropriate input or pivot-randomization model. Recursion itself does not guarantee logarithmic depth or fast sorting.

20 | QUICKSORT MEMORY: NAME THE IMPLEMENTATION

For a standard in-place recursive quicksort that processes both partitions by ordinary recursion, balanced partitioning gives O(log n) call-stack space, while highly unbalanced partitioning can give O(n) stack space. The partitioning stage can use constant extra working storage.

Implementations that create new partition lists need additional storage beyond these stack figures. Special control strategies, such as recursing on the smaller side while iterating over the larger side, can limit stack depth differently.

State which version you are evaluating. “Quicksort always uses O(log n) memory” is not a safe general claim.

21 | FOLDERS AND RECURSIVE STRUCTURES

A folder contains files and possibly more folders. To total the size of a directory tree, process the files in the current folder and repeat the same task for each child folder. A folder with no subfolders ends that path of recursion.

The depth is not fixed in advance, so recursive decomposition matches the structure naturally. A loop with an explicit stack can perform a similar depth-first traversal.

Real filesystem relationships can include symbolic links or cycles. A practical traversal needs an explicit policy for following links, tracking visited locations and handling unavailable files; a pure tree example assumes those complications are absent.

22 | BRANCHING RECURSION CAN REPEAT WORK

A naive recursive Fibonacci function calls itself twice for many inputs, for example fib(n − 1) and fib(n − 2). Their subproblems overlap: the same smaller Fibonacci values are recomputed through several paths.

Its total call count grows exponentially, although the longest active chain has only linear depth. Total calls and maximum simultaneous calls measure different things.

Memoization stores solved subproblem results to reuse them, often improving time at the cost of extra memory. Alternatively, a loop can calculate the sequence using a small rolling state. Recursion is not inherently inefficient, but repeated subproblems can make a naive recursive design expensive.

23 | ADVANTAGES AND LIMITATIONS TO WEIGH

Potential advantage Why it matters Related limitation
Matches self-similar data Tree and fractal rules can be expressed directly Deep structures may exhaust stack resources
Small clear decomposition Each call solves a smaller familiar task A concise function can still hide large call counts
Natural divide-and-conquer structure Partitions can be solved independently Unbalanced partitions can worsen time and depth
Local state for each active call Pending work can be resumed correctly Frames consume memory and calls add overhead

A good explanation connects the advantage to the task. A good limitation identifies a cause and a consequence, for example “a long chain retains many active frames, therefore stack usage grows with depth”.

24 | TAIL RECURSION DOES NOT AUTOMATICALLY REMOVE FRAMES

A tail-recursive call is the final operation of a function’s recursive case: no additional work remains after that call returns. The shown n * factorial(n − 1) is not tail-recursive because multiplication is still pending.

Some languages or implementations can optimize certain tail calls to reuse execution state. Do not assume that a recursive program receives this optimization automatically.

For these Python teaching examples, analyse the ordinary retained call frames. Replacing a loop with a tail-recursive function does not automatically establish constant stack use.

25 | JAVA: THE SAME CONCEPT, TYPED METHODS

public class RecursionExample {
    static long factorial(int n) {
        if (n < 0 || n > 20) {
            throw new IllegalArgumentException("Use n from 0 to 20");
        }
        if (n == 0) {
            return 1;
        }
        return n * factorial(n - 1);
    }

    public static void main(String[] args) {
        System.out.println(factorial(4));
    }
}

The output is 24. Each invocation has its own n, and the base case returns 1 through the waiting multiplications. The stated 0–20 domain keeps the factorial result within signed long capacity.

Java’s fixed-width numerical types and stack limits differ from Python’s integer behaviour, but base cases, progress and returning through active calls remain the same concepts.

26 | EXPLAIN THE MECHANISM, THEN THE APPLICATION

For an Explain question, identify the smaller similar subproblem, the base case, the progress toward it and how the returned result helps the caller. Use the call stack to explain both descent and unwinding.

For an application, connect the recursive structure to the task: subtrees in a tree, smaller branches in a fractal, or partitions in quicksort. Then state the relevant time and memory assumptions.

Before choosing recursion, consider clarity, maximum depth, repeated work and possible iterative alternatives. The next lesson turns these concepts into detailed construction and traces of simple non-branching recursive algorithms.

MATCH THE RECURSION IDEA

Terminology

Terminology

Recursion

A function calling itself directly or indirectly to solve related subproblems.

Base case

A case solved without another recursive call on that path.

Recursive case

A case using one or more smaller recursive subproblems.

Problem reduction

Changing the recursive input toward a solvable base case.

Direct recursion

A function calling itself directly.

Indirect recursion

A cycle of calls through other functions returning to the original function.

Call stack

The structure managing active calls and where execution resumes.

Stack frame

Call-related state retained for an active invocation.

Local state

Parameters and local values belonging to a particular call.

Descent

Entering successive recursive calls toward a base case.

Unwinding

Returning through waiting calls and completing their remaining work.

Pending work

An operation waiting for a recursive result.

Maximum depth

The greatest number of recursive levels active at once under a stated convention.

Termination

Reaching completion rather than continuing indefinitely.

Factorial

For non-negative n, n! is the product 1 through n, with 0! = 1.

Iteration

Repetition controlled by a loop.

Self-similarity

A structure containing smaller parts of the same general form.

Binary tree

A node structure in which each node has at most two children.

Leaf

A node with no children.

Tree traversal

Systematically visiting the nodes of a tree.

Preorder

Process a node, then its left subtree, then its right subtree.

Fractal

A structure exhibiting repeated detail or patterns at different scales.

Divide and conquer

Divide a problem, solve smaller parts and combine or use their results.

Quicksort

A sorting algorithm using pivot-based partitioning and recursive subproblems.

Pivot

A selected value used to partition data in quicksort.

Balanced partition

A split into parts of comparable size.

Auxiliary space

Extra working memory beyond existing input under a stated convention.

Memoization

Store solved subproblem results for reuse.

Overlapping subproblems

The same smaller problem arising through multiple paths.

Tail recursion

A recursive call as the final operation, with no additional work afterwards.

Questions

Questions

CHECK YOUR UNDERSTANDING

Select all correct choices. Each exact set earns one point.

1. Which are essential for the factorial recursion shown?
2. Which statements about active calls are correct?
3. Which are true for factorial(4) with a base case at 0?
4. Which can prevent normal recursive completion?
5. Which applications naturally contain smaller similar parts?
6. Which describe a depth-first recursive traversal?
7. Which describe the two-branch image at depth d?
8. Which quicksort statements are correct?
9. Which are valid recursion trade-offs?
10. Which describe tail recursion accurately?

EXPLAIN AND COMPARE

Write your answers before revealing each sample.

1. Explain the fundamental idea of recursion.

2. Explain the roles of the base and recursive cases in factorial.

3. Describe the pending work in factorial(3).

4. Explain why recursive calls do not overwrite every caller’s local parameter.

5. Explain why a base case alone does not guarantee termination.

6. Compare recursive and iterative factorial under the stated unit-cost model.

7. Explain why recursion suits binary-tree traversal.

8. Explain how depth limits make a recursive fractal image finite.

9. Explain how quicksort uses recursive decomposition.

10. Explain why quicksort can have quadratic worst-case time.

11. Explain two limitations of recursion.

12. Explain why total calls and maximum stack depth are different measures.

EXPLAIN IT | COUNTING A TREE

Explain how recursion could count nodes in a binary tree. Identify an empty-subtree base case, how smaller problems arise, and how their answers are combined. Then explain time and call-stack space using node count n and height h.

Reveal an explanation

An empty subtree contributes 0. For a nonempty node, count its left and right subtrees recursively, then return 1 + left_count + right_count. Each child is a smaller subtree, so the same rule applies. On a finite acyclic tree, all paths reach empty children. Each node is processed once, giving O(n) time with constant work per node. Depth-first recursion retains O(h) stack frames, which can be O(log n) for a balanced tree or O(n) for a chain-like tree.

Flashcards

Flashcards

Click to flip. Select the ideas you need to revisit.

0 cards selected for revision.

Selections are kept while this page is open.

Workbook

Workbook

COMING SOON

The workbook for B2.4.4 Recursion (HL) is coming soon. Complete the matching task and written questions in your exercise book.