Write a Recursive Function From Its Definition

Name the smallest input, say how a larger one reduces to it, then combine.

A recursive function can be written from a definition by answering three questions in turn: what is the smallest input, and its answer; what smaller input does a larger one reduce to; and how is the smaller answer turned into the larger one. This card covers those three questions applied to raising a number to a power, first one step at a time and then by halving, which makes far fewer calls.

The goal is power(x, n), x multiplied by itself n times, for every whole number n from 0 upwards. The definition is the familiar one: x to the 0 is 1, and x to the n is x times x to the n - 1. Each step below answers one question and writes the line of code it produces.

From the definition of a power to two recursive functions

The smallest input

The smallest n the function must accept is 0, and x to the 0 is 1. That is the base case, the input answered without a recursive call. Choosing n = 1 instead, returning x, would leave n = 0 with no answer: the calls would go 0, −1, −2 and on until the call stack ran out of room.

if n == 0:
    return 1

The smaller input

The definition reduces n to n - 1, which moves one step closer to 0 on every call. A recursive call on the same n, or on a larger one, would never arrive.

power(x, n - 1)

Combine

The smaller answer is x to the n - 1, and one more multiplication by x turns it into x to the n.

return x * power(x, n - 1)

A smaller input that shrinks faster

The second question has another answer. x to the n is x to the half of n, squared, so n can drop to n // 2, its half rounded down (// is Python's whole-number division). The base case does not change.

half = fast_power(x, n // 2)

Combine the halves

For an even n, half times half is the answer. For an odd n, rounding down lost one factor of x, so it is multiplied back in.

if n % 2 == 0:
    return half * half
return half * half * x

Put together, the two functions read as their definitions. The listing was run, and the highlighted lines are the recursive calls:

power.pypy

def power(x, n):
    if n == 0:
        return 1
    return x * power(x, n - 1)


def fast_power(x, n):
    if n == 0:
        return 1
    half = fast_power(x, n // 2)
    if n % 2 == 0:
        return half * half
    return half * half * x


print("power(2, 10) =", power(2, 10))
print("fast_power(2, 10) =", fast_power(2, 10))
print("fast_power(3, 5) =", fast_power(3, 5))

OutputRan with python:3.14.8-slim-trixie (Python 3.14.8)

power(2, 10) = 1024
fast_power(2, 10) = 1024
fast_power(3, 5) = 243

The two answers to the second question cost very differently. A run that counted the calls found that power(2, 10) makes 11 calls, with n going 10, 9, 8 and so on down to 0, while fast_power(2, 10) makes 5, with n going 10, 5, 2, 1, 0. fast_power(2, 1000) makes only 11. Shrinking by one makes n + 1 calls, which is O(n). Halving makes one call per halving, and the number of times n can be halved before it reaches 0 grows as O(log n). The same run checked both functions against Python's own x ** n for x from −3 to 3 and n from 0 to 20, and every result matched.

The three questions apply to any recursive definition, and the second decides the most: a different smaller input can change the cost of the whole function, while the base case and the combine step only follow from it.

← → move through sections and cards