MEPX
Chapter 8 of 10All chapters
  1. 1Finding the rule
  2. 2Arithmetic sequences
  3. 3Geometric sequences
  4. 4Sequences worth knowing
  5. 5Primes and factors
  6. 6Writing the nth term
  7. 7Patterns from shapes
  8. 8Recursive rules
  9. 9Patterns outside mathematics
  10. 10Solving pattern puzzles

Chapter 8 of 10

Recursive rules

Defined in terms of itself.

Two ways to define

A closed form computes any term directly from n. A recursive rule says how to get the next term from previous ones. Fibonacci is naturally recursive and awkward in closed form.

  • Recursive rules need starting values, or they define nothing.
  • Computing recursively without storing results repeats enormous amounts of work.

In computing

This is exactly why memoisation exists: store each computed term so it is calculated once. It turns an exponential Fibonacci program into an instant one.