Counting with recursion

Overview

Counting recursions enumerate outcomes by summing over every valid first choice. Two representatives here: counting the ways d dice with f faces sum to a target, and counting compositions — the ordered ways to write n as a sum of positive parts. Both share the same skeleton: for each legal first choice, recurse on the remainder and add the results. And both illustrate the same practical point as the memoization lesson — the naive form recomputes heavily, so a cache (or a bottom-up table) is what makes them usable.

Why it matters

"In how many ways can this happen?" is the core question of discrete probability, and these counts feed directly into expected values and distributions. Dice-sum counts give exact probabilities for board games and risk models; compositions count how many ways a quantity can be split into ordered parts, which appears in partitioning, parsing and resource allocation.

Core concepts

Sum over first choices. ways(state) = sum over each legal choice c of ways(state after c). That is the whole pattern; the guards on "legal" are where the correctness lives.

Dice sums. With d dice of f faces, ways(d, t) = sum over face = 1..f of ways(d-1, t-face). Base cases: ways(0, 0) = 1 (no dice, target met) and ways(0, t != 0) = 0. Prune when t < 0.

Compositions. comp(n) = sum over k = 1..n of comp(n-k), with comp(0) = 1. The closed form is 2^(n-1) for n >= 1, which makes it an ideal self-check — if your code disagrees, the recurrence or a base case is wrong.

Base cases are the seeds of every count. comp(0) = 1 is what makes the sum non-zero at all; setting it to 0 collapses every result to 0.

Overlap demands a cache. comp(n) calls comp(n-1) down to comp(0) from many branches. Memoise with a sentinel, or build bottom-up.

Growth and overflow. 2^(n-1) passes 64-bit range around n = 64; dice counts grow quickly too. Use long long and apply any specified modulus.

Syntax notes

#include <stdlib.h>

/* compositions of n: memo[] pre-filled with -1 */
long long comp(int n, long long *m) {
    if (n == 0) return 1;              /* the empty composition */
    if (m[n] >= 0) return m[n];
    long long t = 0;
    for (int k = 1; k <= n; k++) t += comp(n - k, m);   /* every legal first part */
    return m[n] = t;
}

/* dice sums, bottom-up: dp[s] = ways to reach s with the dice seen so far */
long long dice(int d, int f, int t) {
    if (d < 0 || t < 0) return 0;
    long long *dp = calloc((size_t)t + 1, sizeof *dp);
    if (!dp) return -1;
    dp[0] = 1;                                  /* zero dice reach 0 exactly one way */
    for (int i = 0; i < d; i++)
        for (int s = t; s >= 0; s--) {          /* DOWNWARD: one die per pass */
            long long acc = 0;
            for (int face = 1; face <= f; face++)
                if (s - face >= 0) acc += dp[s - face];
            dp[s] = acc;
        }
    long long r = dp[t];
    free(dp);
    return r;
}

Key points:

• comp(0) = 1 seeds everything; without it all counts are 0.
• The dice sweep goes downward so each pass adds exactly one die.
• long long throughout, and calloc supplies the zeros the accumulation needs.

Lesson

Recursion counts configurations by summing over each first choice: dice sums add over each die face, and compositions add over each first part. Both are counting recurrences (memoized where needed).

Code examples

#include <stdio.h>
#include <stdlib.h>
static long long dice(int d,int f,int t){ if(d<0||t<0) return 0; long long*dp=calloc(t+1,sizeof(long long)); dp[0]=1; for(int i=1;i<=d;i++){ long long*nd=calloc(t+1,sizeof(long long)); for(int s=0;s<=t;s++) if(dp[s]) for(int v=1;v<=f&&s+v<=t;v++) nd[s+v]+=dp[s]; free(dp); dp=nd; } long long r=dp[t]; free(dp); return r; }
static long long comp(int n,long long*m){ if(n==0) return 1; if(m[n]>=0) return m[n]; long long t=0; for(int k=1;k<=n;k++) t+=comp(n-k,m); return m[n]=t; }
int main(void){
    printf("ways for 3 six-sided dice to total 10 = %lld\n", dice(3,6,10));
    long long m[9]; for(int i=0;i<9;i++) m[i]=-1;
    printf("compositions of 8 = %lld\n", comp(8,m));
    return 0;
}

Line by line

Common mistakes

Exponential recursion without memoization; miscounting the empty/base case.

Debugging tips

Compiler errors and warnings:

• -Wsign-compare at the calloc size; cast to size_t.
• Silent overflow if the accumulator is int.

Runtime symptoms:

• Everything returns 0. comp(0) returns 0 instead of 1, or dp[0] was never set to 1. The seed is what every count grows from.
• comp(n) does not equal 2^(n-1). The loop bound is wrong — the first part ranges over 1..n inclusive.
• Exponentially slow. The memo is missing or never read.
• Dice counts too high. The sweep runs upward, letting one die contribute more than once per pass.
• Counts go negative. 64-bit overflow around n = 64 for compositions; use a modulus if the problem specifies one.

Technique: compare comp(n) against 2^(n-1) for n = 1..20, and dice(2,6,7) against the known 6. Both are exact oracles that pinpoint a wrong base case immediately.

Memory safety

• Sentinel choice. The memo must be seeded to a value that cannot be a real count — -1, not 0, since 0 is a legitimate answer for unreachable states.
• Seed once, in a wrapper. Initialising the memo inside the recursive function resets it on every call and silently disables the cache.
• Allocation validation. t + 1 entries with t from input: reject negative t before the size_t cast, and check calloc for NULL.
• calloc is correct for the dice table because entries are accumulated into and must start at zero — the opposite of the memo case, where zero is ambiguous. Knowing which situation you are in is the point.
• Index guard. s - face >= 0 must be checked before indexing dp[s - face].
• Overflow. Signed overflow is undefined; counts here grow exponentially, so bound the input or apply a modulus.

Real-world uses

Concrete uses: Dice-sum distributions drive probability calculations in games, risk models and simulations. Compositions count ordered partitions — how many ways to split a job into consecutive batches, or a length into ordered segments. The same sum-over-first-choice pattern underlies counting parse trees, tilings, and paths through a DAG.

Professional best practices:

Beginner:

• Write the base case first and sanity-check the first few terms against a known formula.
• Use long long from the start.

Intermediate:

• Prefer bottom-up tables when the state space is small and dense; use memoised recursion when it is sparse or irregular.
• Validate counting code against a closed form or a brute-force enumeration for small inputs — counting bugs are invisible without an oracle.
• Apply the problem's modulus during accumulation rather than at the end.

Practice tasks

1. (Beginner) Compositions. Implement comp(n) with memoization and verify comp(n) == 2^(n-1) for n = 1..20. Example: comp(3) -> 4. Concepts: sum over first choices, base case seed.

2. (Beginner) Dice sums. Implement dice(d, f, t). Example: dice(2,6,7) -> 6; dice(2,6,1) -> 0. Concepts: per-die passes, downward sweep.

3. (Intermediate) Brute-force oracle. Enumerate all dice outcomes for d <= 4 and confirm the counts match. Concepts: validating counting code.

4. (Intermediate) Restricted parts. Count compositions using only parts of size 1 or 2, and confirm the result is the Fibonacci sequence. Concepts: restricting the choice set.

Summary

Counting recursions sum over every legal first choice, so the base case is the seed that every count grows from — comp(0) = 1 and dp[0] = 1 are what make the totals non-zero at all. Both examples overlap heavily, so a memo (seeded to a sentinel that cannot be a valid count, never 0) or a bottom-up table is what makes them practical. Validate against an exact oracle wherever one exists — compositions are 2^(n-1), two dice make 7 in six ways — because counting bugs are otherwise invisible, and use long long since these totals grow exponentially.

Practice with these exercises

• Dice sum ways
• Count compositions