Skip to content

Recursion [mp]

Micro pattern

Description

Invoke the same operation on smaller structures, ranges, or remaining choices.

Problems

Backtracking recursion

Use calls for choices and undo mutable choices on return.

Structural tree recursion

Express tree operations using recursively processed subtrees.

Graph and grid recursion

Recursively process unvisited neighbors in a component.

Divide-and-conquer recursion

Recursively solve independent ranges before combining results.

Linked-list recursion

Pass the preceding node as state while consuming the remaining suffix.

Memoized recursion

Cache results so repeated calls reuse prior work.