liveBook · Manning

Recurrence

As explained in Timeless Algorithms, The Foundational Ideas

A rule that defines a quantity in terms of its values for other instances.

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
Fn=Fn-1+Fn-2

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

How Timeless Algorithms, The Foundational Ideas covers it

How deep it goes
Defines Fibonacci, knapsack, and coin-change recurrences, then connects recursive decomposition to tabulation and memoization.
Examples
Uses Fibonacci numbers, knapsack choices, coin-change combinations, and shortest routes through networks.
What it assumes
Assumes a problem can be represented through states and smaller subproblems, with optimal substructure for a global-optimum guarantee.
What you can do after
Understand how to express a problem as a recurrence and why exact evaluation can yield a global optimum when optimal substructure holds.
How it connects
Connects recurrence relations to dynamic programming, optimal substructure, overlapping subproblems, and recursive optimization.

Also explained in

Compare how 4 books explain recurrence →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Timeless Algorithms, The Foundational Ideas. The section links point to the parts of the book it draws on.