Writing Recursive Functions

AQA 4.1.1.16 — Writing recursive functions

Retrieval: the previous lesson traced and debugged recursive functions someone else had already written. This lesson asks you to design your own from scratch — starting from a problem description, not starting from working code.

Key vocabulary

• Recursive design process — identifying the base case and recursive case before writing any code, not after.
• Shrinking step — the specific way each recursive call must move the problem measurably closer to the base case.

Understand — a repeatable design process

Every recursive function can be designed the same way, in this order: (1) identify the simplest possible input the function must handle directly — that's your base case; (2) for every other input, describe the answer in terms of "one step of work, plus the same function called on a smaller version of the problem" — that's your recursive case; (3) check explicitly that the smaller version genuinely gets closer to the base case, every single time. Skipping step 3 is exactly how "shrinking" recursive cases that don't actually shrink correctly sneak into otherwise-plausible-looking code.

Worked example — reversing a string recursively

Design first: the simplest string to reverse is an empty one (reversing it gives back an empty string — the base case). For any other string, its reverse is its last character, followed by the reverse of everything except the last character — a smaller version of the same problem.

def reverse_string(text):
    if text == "":                       # base case
        return ""
    return text[-1] + reverse_string(text[:-1])   # recursive case

print(reverse_string("hello"))   # "olleh"

Trace it — reverse_string("cat")

reverse_string("cat") = "t" + reverse_string("ca")
                       = "t" + ("a" + reverse_string("c"))
                       = "t" + ("a" + ("c" + reverse_string("")))
                       = "t" + ("a" + ("c" + ""))
                       = "tac"

Worked example — summing a list recursively

Design first: the simplest list to sum is an empty one (sum is 0 — the base case). For any other list, its sum is its first element, plus the sum of everything after it — again, a smaller version of the same problem.

def sum_list(numbers):
    if not numbers:                              # base case: empty list
        return 0
    return numbers[0] + sum_list(numbers[1:])    # recursive case

print(sum_list([4, 2, 7, 1]))   # 14

Debug it — diagnose, explain, fix, test, justify

A student attempts to write a recursive function that counts down from n to 1, printing each number, then stops:

def count_down(n):
    if n == 1:
        print(n)
    print(n)
    count_down(n - 1)

Testing it with count_down(3) prints 3, 2, 1 correctly — then keeps going into 0, -1, -2, ... until it crashes.

1. Diagnose: trace count_down(1) specifically — what does it actually do?
2. Explain: the base case condition (n == 1) is checked, and even prints correctly — so why doesn't the recursion actually stop there?
3. Fix: rewrite the function so it genuinely stops after printing 1.
4. Test: confirm count_down(3) now prints exactly 3, 2, 1 and returns, with no further calls.
5. Justify: explain the difference between a base case that's checked and a base case that's actually acted on (i.e. that prevents further recursion).

(count_down(1) prints 1 twice (once inside the if, once unconditionally below it) and then still calls count_down(0) regardless, because there's no return statement stopping execution after the base-case branch. The if branch needs a return (or the recursive call needs to be inside an else) so reaching the base case genuinely ends the function instead of merely printing something extra before continuing anyway.)

Common mistake

Writing a condition that correctly identifies the base case, without actually preventing the recursive call from still happening afterwards — as in the debug task above. Identifying the base case is necessary but not sufficient; the code must also structurally stop there (via return, or by putting the recursive call inside an else/elif so it's genuinely skipped).

Apply it — design two more recursive functions

Using the three-step design process above, write:

1. power(base, exponent) — returns base raised to exponent (a non-negative whole number), using repeated multiplication via recursion rather than Python's ** operator.
2. count_vowels(text) — returns how many vowels (a, e, i, o, u) are in text, using recursion rather than a loop.

For each, state your base case and recursive case explicitly before writing the code, exactly as the worked examples above did.

Challenge

Write a recursive function is_palindrome(text) that returns True if text reads the same forwards and backwards, and False otherwise, without using string slicing to reverse the whole string at once — instead, compare the first and last characters, then recurse on what's left in between.

Looking ahead: the next lesson (Recursive Algorithms) applies exactly this design process to an algorithm you already know from Year 12 — binary search — rewritten recursively instead of with a loop.