A recurrence relation defines a solution for a larger problem in terms of solutions to smaller instances. It provides a mathematical blueprint for building solutions progressively, rather than solving the entire problem at once. section 6.1.2
The rule depends on what each problem requires:
- For knapsack, compare excluding an item with including it when it fits; retain the larger value. section 6.2.2
- For coin change, add the counts contributed by eligible denominations, taking care not to count permutations as distinct combinations. section 6.3.2
- For shortest routes, compare an established route with one passing through a newly permitted intermediate node. section 6.4.3
The Fibonacci recurrence makes the smaller-instance structure explicit: each term depends on the two preceding terms. section 6.1.2
A recurrence relation is not the same as a recurrent neural-network architecture. The former decomposes a problem into related subproblems; the latter repeatedly updates a hidden state across a sequence. section 12.3.2



