A recursive sequence 
,
also known as a recurrence sequence, is a sequence of numbers 
indexed by an integer 
and generated by solving a recurrence
equation. The terms of a recursive sequences can be denoted symbolically in a
number of different notations, such as 
, 
, or f[
], where 
is a symbol representing the sequence.
The idea of sequences in which later terms are deduced from earlier ones, which is implicit in the principle of mathematical induction, dates to antiquity.
In the case of linear recurrence equations such as the recurrence
 |
(with 
)
generating the Fibonacci numbers, it is possible
to solve for an explicit analytic form of the 
th term of the sequence. Some special classes of recurrence
equations have analytic solutions for specific parameters, but solutions for
a general parameter is not known. An example of this type is the logistic
equation
 |
which has known exact solutions only for 
, 2, and 4. It is not known how to solve a general recurrence
equation to produce an explicit form for the terms of the recursive sequence, although
computers can often be used to calculate large numbers of terms through brute force
(combined with more sophisticated techniques such as caching, etc.).
Historically speaking, the Fibonacci numbers 
(left top figure), which are one of
the most well-known such sequences, predate Leonardo Fibonacci's 1202 discovery by
more than a millennium, having arisen around 200 BC in work by Pingala (Wolfram 2002,
pp. 890-891).
In the late 1800s and early 1900s, investigations into the foundations of mathematics
led to the formal definition of so-called recursive
functions. However, a systematic investigation of the types of possible behavior
was apparently not undertaken until the work of Wolfram (2002), with the exception
of a few isolated sequences such as Hofstadter's
Q-sequence 
in 1979 (right top figure) and the Hofstadter-Conway
$10,000 sequence 
in 1988 (bottom figure).
