HOWTO · Python

How to Implement Recursive Multiplication in Python

Learn how recursive multiplication works in Python with repeated addition, a halving strategy, and an accumulator-based tail-recursive example. Compare their call depth and understand why Python's built-in multiplication is usually the practical choice.

On this page

Python already multiplies integers with *, but writing multiplication recursively is a useful way to see how a problem can be reduced to smaller versions of itself. The examples below cover repeated addition, a halving strategy, and an accumulator-based variation. They are for learning; for ordinary application code, use the built-in operator.

Understanding Recursion

A recursive function solves a problem by calling itself with a smaller input. It needs a base case that returns a result without another call, and a recursive case that makes progress toward that base case. Each call waits for its child call to return; then the pending operations finish as the calls unwind.

For multiplication by repeated addition, the recursive case reduces the multiplier by one and adds the multiplicand to the returned result. The base case is reached when the multiplier is zero. Without a condition that eventually stops the calls, the function cannot produce a result.

Basic Recursive Multiplication

The straightforward version reduces the second input by one on each call, then adds the first input as the calls return.

Run this example:

def recursive_multiply(a, b):
    if b == 0:
        return 0
    if b < 0:
        return recursive_multiply(-a, -b)
    return a + recursive_multiply(a, b - 1)

print(recursive_multiply(5, 3))

The function adds a once for each positive unit of b. When b is negative, changing both signs lets it use the same positive-counting recurrence while preserving the product; this also supports negative multiplicands.

Each call reduces b by one until it reaches the base case. The calls then return in reverse order, adding a at each step. This makes the recurrence easy to follow, but it uses a number of calls proportional to the absolute value of the multiplier. A large multiplier can therefore exceed Python’s recursion limit.

Handling Negative Integers and Zero

The same function handles zero and all sign combinations. A zero multiplier returns zero immediately. For a negative multiplier, changing the signs of both operands converts the work to the positive-multiplier case while preserving the mathematical product.

def recursive_multiply(a, b):
    if b == 0:
        return 0
    if b < 0:
        return recursive_multiply(-a, -b)
    return a + recursive_multiply(a, b - 1)

for pair in ((5, 3), (-5, 3), (5, -3), (-5, -3), (5, 0)):
    print(pair, recursive_multiply(*pair))

The four signed cases produce products with the usual sign rule: operands with the same sign give a positive result, and operands with different signs give a negative result. A zero operand gives zero. The loop prints each input pair beside its product, making the sign behavior easy to compare.

Reduce Recursive Calls by Halving

Repeatedly subtracting one is unnecessary when the multiplier can be halved. For positive b, let half be the product of a and b // 2. If b is even, the full result is half + half; if it is odd, one additional a is needed. Integer division and the remainder test express this recurrence without bitwise operations.

def multiply_by_halving(a, b):
    if b == 0:
        return 0
    if b < 0:
        return multiply_by_halving(-a, -b)
    half = multiply_by_halving(a, b // 2)
    if b % 2 == 0:
        return half + half
    return half + half + a

print(multiply_by_halving(5, 3))

Each recursive step roughly halves the multiplier, so the call depth grows in proportion to the number of times the multiplier can be halved, rather than its magnitude. The method still performs additions and still uses Python’s call stack. It is a useful illustration of reducing a recurrence, though built-in multiplication is simpler for normal code.

Tail Recursion in Python

In a tail-recursive function, the recursive call is the final operation; an accumulator carries the result through the calls. This changes where the pending work is recorded, but Python does not optimize tail calls by reusing a single stack frame. The call-stack limitation therefore remains.

def tail_recursive_multiply(a, b, accumulator=0):
    if b == 0:
        return accumulator
    if b < 0:
        return tail_recursive_multiply(-a, -b, accumulator)
    return tail_recursive_multiply(a, b - 1, accumulator + a)

print(tail_recursive_multiply(5, 3))

The accumulator starts at zero and gains one a on each positive step. When the multiplier reaches zero, it holds the product. As with repeated addition, this version makes a linear number of calls in the multiplier’s magnitude, so tail-call style does not make large inputs safe in Python.

When Recursive Multiplication Is Useful

These implementations clarify base cases, recursive progress, and the difference between linear and logarithmic call depth. Repeated addition and the tail-recursive version have linear depth; the halving version has logarithmic depth. All still incur function-call and stack costs, and Python does not promise a fixed recursion-depth threshold across environments.

For practical integer arithmetic, prefer a * b: it is clearer and avoids the extra Python-level recursive calls. Use recursive multiplication when studying recursion or when a problem specifically calls for a recursive formulation, and keep inputs small enough for the chosen recurrence.