## Quick Reference

A statement describing some quantity such as *f*(*n*) (where *f* is some function and *n* is a positive integer) in terms of values of *f*(*m*), where *m* is a nonnegative integer smaller than *n*; initial values such as *f*(0) or *f*(1) can be assumed to be defined. The concept can be extended to include functions of several variables. A recurrence will then involve defining *f*(*m*,*n*), say, in terms of *f*(*m*′,*n*′) where in some sense (*m*′,*n*′) is smaller than (*m*,*n*); again initial values can be assumed. The numbers in the Fibonacci series can be defined by a recurrence.

In general, a recurrence can be considered as an equation connecting the values of the function at a number of related points. It has the form *g*(*n*, *f*(*n*), *f*(*n*−1),…, *f*(*n*−*k*) = 0*n* = *k*, *k* + 1,…, *N* Assuming initial values for *f*(0), *f*(1),…, *f*(*k*−1), values for other points *n* can be calculated.

*g*(*n*, *f*(*n*), *f*(*n*−1),…, *f*(*n*−*k*) = 0

*n* = *k*, *k* + 1,…, *N*

Equations of this type arise naturally in the discretization of continuous problems, and in a slightly different form, known as a difference equation, appear repeatedly in combinatorics.

**From:**
recurrence
in
A Dictionary of Computing »

*Subjects:*
Computing.

## Related content in Oxford Index

##### Reference entries

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content.