Introduction

Recursive random sampling becomes useful when the data is naturally recursive, such as a tree, nested folders, or hierarchical categories. Instead of flattening the whole structure first, you can sample efficiently by storing subtree sizes and descending only into the branch that contains the randomly chosen position.

Sampling from a Recursive Structure

Suppose you have a tree and want to choose one node uniformly at random. A slow solution is:

1. traverse the whole tree
2. put every node into a list
3. call a random choice on that list

That works, but it costs extra memory and repeated full traversals if you sample often.

A better idea is to let each node store the number of nodes in its subtree. Then:

1. compute the total size once
2. draw a random integer from 0 to size - 1
3. recurse into the child subtree whose size range contains that index

This makes each sample proportional to the height of the tree instead of the total number of nodes.

A Concrete Tree Example

Here is a simple Python implementation:

1import random
2
3class Node:
4    def __init__(self, value, children=None):
5        self.value = value
6        self.children = children or []
7        self.size = 1
8
9    def compute_size(self):
10        self.size = 1
11        for child in self.children:
12            self.size += child.compute_size()
13        return self.size
14
15    def sample(self):
16        index = random.randrange(self.size)
17        return self._sample_by_index(index)
18
19    def _sample_by_index(self, index):
20        if index == 0:
21            return self.value
22
23        index -= 1
24        for child in self.children:
25            if index < child.size:
26                return child._sample_by_index(index)
27            index -= child.size
28
29        raise RuntimeError("Invalid subtree index")
30
31root = Node(
32    "A",
33    [
34        Node("B", [Node("D"), Node("E")]),
35        Node("C", [Node("F")]),
36    ],
37)
38
39root.compute_size()
40print(root.sample())

The key idea is that each node owns a contiguous index range:

• index 0 means the current node
• the next range belongs to the first child subtree
• then the second child subtree, and so on

Choosing a random index uniformly over the total subtree size guarantees a uniform sample over all nodes.

Why This Is Efficient

After the initial compute_size pass, a single sample only walks one path through the tree. If the tree height is small relative to the number of nodes, this is much cheaper than flattening on every call.

This pattern is especially useful when:

• the structure is large
• you need many repeated samples
• the data is already stored recursively

The tradeoff is that subtree sizes must stay correct. If the tree changes, you need to recompute sizes or update them incrementally.

Extending the Idea to k Samples

If you need several samples, the simplest option is to call sample() repeatedly. That samples with replacement, meaning the same node may appear more than once.

samples = [root.sample() for _ in range(5)]
print(samples)

If you need sampling without replacement, the problem becomes more complex. One approach is to remove chosen nodes logically and update subtree sizes after each selection. Another approach is to flatten once if k is large relative to the data size.

This is a good example of an algorithmic tradeoff:

• many samples with replacement: recursive indexed sampling is excellent
• many samples without replacement: flattening or a specialized structure may be simpler

Relation to Weighted Sampling

The same recursive idea works for weighted sampling. Instead of storing subtree node counts, store subtree weights.

For example, if each leaf represents a product with a probability weight, you can:

1. store the total weight of each subtree
2. draw a random number between 0 and total weight
3. descend into the child whose cumulative weight range contains that number

That turns the tree into a recursive weighted-choice structure.

Common Pitfalls

The most common bug is stale subtree sizes. If you add or remove nodes and forget to update sizes, the random index mapping becomes wrong and the sample is no longer uniform.

Another problem is calling recursive sampling on a very deep tree in a language with a shallow recursion limit. In that case, an iterative descent with a loop may be safer.

It is also easy to claim an algorithm is “efficient” while still recomputing sizes before every sample. The real gain appears when you compute metadata once and reuse it for many selections.

Summary

• Recursive random sampling is useful when the data itself is recursive.
• Store subtree sizes so one random index can be mapped to a node efficiently.
• After preprocessing, each sample follows one path instead of flattening the full structure.
• The same technique extends naturally from uniform sampling to weighted sampling.
• Keep subtree metadata up to date or the distribution becomes incorrect.