Recursive Function — Definition, Formula & Examples

A recursive function is a function that defines its output for a given input by referring back to its own output at one or more previous inputs. It always requires at least one starting value, called an initial condition or base case, to get the sequence going.

A recursive function $f$ on the natural numbers is defined by specifying (1) one or more initial values $f(1), f(2), \ldots$ and (2) a recurrence relation that expresses $f(n)$ in terms of $f(n-1), f(n-2), \ldots$ for all $n$ beyond the initial values.

Key Formula

a_n = f(a_{n-1},\, a_{n-2},\, \ldots), \quad \text{with given } a_1 \text{ (and } a_2, \ldots \text{ if needed)}

Where:

$a_n$ = The value of the function at position n
$a_{n-1}, a_{n-2}, \ldots$ = Previously computed values the current term depends on

How It Works

To evaluate a recursive function, you start from the given base case(s) and apply the recurrence relation step by step. Each new term depends on terms you have already computed, so you build the sequence forward one term at a time. For example, if

a_1 = 3

and

a_n = 2a_{n-1} + 1

, you find

a_2

from

a_1

, then

a_3

from

a_2

, and so on. You cannot skip ahead to

a_{10}

without first computing

a_2

through

a_9

(unless you convert the recursive rule into an explicit formula).

Worked Example

Problem: The Fibonacci sequence is defined by

F_1 = 1

F_2 = 1

, and

F_n = F_{n-1} + F_{n-2}

for

n \geq 3

. Find

F_6

Base cases: Write down the initial values.

F_1 = 1, \quad F_2 = 1

Compute forward: Apply the recurrence relation for each successive term.

F_3 = 1 + 1 = 2, \quad F_4 = 2 + 1 = 3, \quad F_5 = 3 + 2 = 5

Find F₆: Use the two most recent terms.

F_6 = F_5 + F_4 = 5 + 3 = 8

Answer:

F_6 = 8

Why It Matters

Recursive functions appear throughout discrete math, computer science, and financial modeling. Algorithms like merge sort and binary search are defined recursively. In precalculus and AP courses, you will often need to convert between recursive and explicit formulas for arithmetic and geometric sequences.

Common Mistakes

Mistake: Forgetting to state or use the base case, then trying to apply the recurrence relation indefinitely.

Correction: A recursive definition is incomplete without its initial condition(s). Always identify the base case first; without it, the function has no starting point and no term can be computed.