Recursion Patterns

The problem

Four unrelated-looking tasks land on your desk in one afternoon: print the numbers 1 to n, compute n!, find the greatest common divisor of two numbers, and raise a base to a power fast. You start writing four different loops, each with its own bookkeeping.

Halfway through the third loop you get a nagging feeling that you are typing the same shape over and over. And you are. Underneath, all four are the same recursive move dressed in different clothes. Learn the move once and you stop reinventing it.

A first attempt

Solve each one ad hoc and you get four loops that share nothing:

def power_slow(base, exp):
    result = 1
    for _ in range(exp):        # multiply exp times
        result *= base
    return result

That power loop is O(exp) — for 2^1000 it does a thousand multiplications. Worse, you have now written four separate control structures, each with a counter to initialize, advance, and test. There is no shared vocabulary, so every new "compute over the integers" task starts from scratch. The repetition is a hint that a single pattern is hiding.

The insight

Almost every one of these is a linear recursion: reduce the input by one step, recurse, and combine. And two of them — power and GCD — do something even better: they shrink the input by half or toward zero fast, which turns linear work into logarithmic work.

Three reusable skeletons cover the set:

• Do-then-recurse (or recurse-then-do): print n and recurse, or recurse and then print. Order controls ascending vs descending.
• Reduce-and-combine: factorial(n) = n * factorial(n - 1).
• Halve-the-problem: fast exponentiation squares a half-sized result; Euclid's GCD replaces (a, b) with (b, a mod b).

Once you see them as skeletons, you fill in the blanks instead of reinventing the loop.

How it works

Take fast exponentiation, the most rewarding of the four.

power(2, 10)
= power(2, 5)^2
= (2 * power(2, 2)^2)^2
= (2 * (power(2, 1))^2 ... )   -> log2(10) ≈ 4 levels, not 10

The code

def power(base, exp):          # O(log exp)
    if exp == 0:
        return 1
    half = power(base, exp // 2)
    if exp % 2 == 0:
        return half * half
    return half * half * base


def gcd(a, b):                 # Euclid, O(log min(a, b))
    if b == 0:
        return a
    return gcd(b, a % b)


print(power(2, 10))  # 1024
print(gcd(48, 36))   # 12

function power(base: number, exp: number): number {
  if (exp === 0) return 1;
  const half = power(base, Math.floor(exp / 2));
  if (exp % 2 === 0) return half * half;
  return half * half * base;
}

function gcd(a: number, b: number): number {
  if (b === 0) return a;
  return gcd(b, a % b);
}

console.log(power(2, 10)); // 1024
console.log(gcd(48, 36)); // 12

static long power(long base, int exp) {   // O(log exp)
    if (exp == 0) return 1;
    long half = power(base, exp / 2);
    if (exp % 2 == 0) return half * half;
    return half * half * base;
}

static int gcd(int a, int b) {            // O(log min(a, b))
    if (b == 0) return a;
    return gcd(b, a % b);
}

// power(2, 10) -> 1024,  gcd(48, 36) -> 12

long power(long base, int exp) {          /* O(log exp) */
    if (exp == 0) return 1;
    long half = power(base, exp / 2);
    if (exp % 2 == 0) return half * half;
    return half * half * base;
}

int gcd(int a, int b) {                   /* O(log min(a, b)) */
    if (b == 0) return a;
    return gcd(b, a % b);
}

/* power(2, 10) -> 1024,  gcd(48, 36) -> 12 */

long long power(long long base, int exp) {  // O(log exp)
    if (exp == 0) return 1;
    long long half = power(base, exp / 2);
    if (exp % 2 == 0) return half * half;
    return half * half * base;
}

int gcd(int a, int b) {                     // O(log min(a, b))
    if (b == 0) return a;
    return gcd(b, a % b);
}

// power(2, 10) -> 1024,  gcd(48, 36) -> 12

Complexity

The lesson of the table: shrinking the input by a step costs linear time, but shrinking it by half costs logarithmic time. Same skeleton, wildly different speed.

When to use it

Practice

Recap

• A handful of recursive skeletons — do-then-recurse, reduce-and-combine, halve-the-problem — cover most integer recursion.
• Order of work versus recursion controls direction; the rate of shrink controls complexity.
• Halving the input turns linear work into logarithmic work.