Associated Topics || Dr. Math Home || Search Dr. Math

### Recursive vs. Explicit Formulas

```
Date: 01/02/97 at 23:22:27
From: Carolyn Johnsen
Subject: Algebra II (2)

Could you please explain to me the difference between explicit and
recursive formulas?  I think I understand it, but then I get myself
more confused.

Thanks,
A Soon to be Satisfied Senior
```

```
Date: 01/03/97 at 00:54:21
From: Doctor Pete
Subject: Re: Algebra II (2)

Okay, let me try this.  Vaguely, a recursive formula has the
property of referencing itself.  In particular, the following formula
is recursive:

F[n] = F[n-1]

This means that if you want to know what F[5] is, you plug in 5 for
n to get F[5-1] = F[4].  But that's not much of an answer, is it?
Well, what's F[4]?  We use the above formula again and we get
F[4] = F[4-1] = F[3].  In fact, we see that:

F[n] = F[n-1] = F[n-2] = F[n-3] = ...

While we don't know what all of these values are, the recursive
formula tells us that they are all the same.  But is it true that
F[n] = F[n-1/2]?  Not necessarily.  For example, let's add two
conditions:

F[0] = 0, F[1/2] = 1

Then clearly, F[n] = 0 for all integers n, and F[n+1/2] = 1 for all
integers n.  Also, it is important to note that simply because we
have defined F[0] and F[1/2], F[n] for other values of n is not
necessarily determined from this and its recursive formula.  For
example, what is F[1/4]?  F[2/3]? F[3.14159]?  We simply don't know
from the information given thus far.  However, say we defined F[n] to
be:
F[n] = F[n-1]
F[x] = x for all real x greater or equal to 0 and less than 1

(We can write the second line as "F[x] = x for x in [0,1)" - the
[0,1) is an interval which includes all numbers greater than or equal
to 0 but less than 1.)  Then the graph of F[n] looks like this:

1_|
/|  /   /   /   /
/ | /   /   /   /
______________________/__|/___/___/___/______________ n
-1  0|   1   2   3
|
|

It is composed of a series of 45-degree angle segments.  Note that
F[1] = 0, but F[0.99999] = 0.99999; in fact, for a number b
"arbitrarily close to" 1 but less than it, F[b] = b.

Anyway, I digress.  This isn't about limits or weird functions, but
the difference between recursive and explicit formulas.  To this end,
I will give you the explicit formula for the same function F[n],
defined for all real values n.  It is

G[n] = n - Floor[n],

where Floor[n] is the greatest integer less than or equal to n.  So if
n = -1, G[-1] = -1 - Floor[-1] = 0.  Similarly:

G[-3.5] = -3.5 - Floor[-3.5] = -3.5 - (-4) = 0.5

If we calculate this using the recursive formula:

F[-3.5] = F[-2.5] = F[-1.5] = F[-0.5] = F[0.5] = 0.5

So they are the same!

Notice, then, that the two definitions:

F[n] = F[n-1], F[x] = x for x in [0,1)

and

G[n] = n - Floor[n],

are quite different, not only in notation but in how their values are
calculated.  The first (recursive) relies on some set of initial
conditions (F[x] = x for x in [0,1)) and a relation which allows you
to travel this "path" to the initial condition.  The second is very
straightforward, and does not rely on any information other than how
to manipulate the input value to get the value of the function.  In
particular, it "does not rely on itself."

Another example, on nonnegative integers n, is:

Recursive:  F[n] = n*F[n-1], F[0] = 1
Explicit:   G[n] = n!

They are the same function, the factorial function, and I will leave
it as an exercise for you to determine why.

A third example, also defined on nonnegative integers n:

Recursive:  F[n] = F[n-1] + F[n-2], F[0] = 0, F[1] = 1
Explicit:   G[n] = (((1+Sqrt[5])/2)^n - ((1-Sqrt[5]))^n)/Sqrt[5]

These are also the same function, this time for the Fibonacci numbers,
0, 1, 1, 2, 3, 5, 8, 13, ....  To show that these are indeed the same
is quite easy; one need only verify that G[0] = 0, G[1] = 1, and
G[n] = G[n-1] + G[n-2], just like F.  This I also leave as an
excercise.

I hope that this gives you an idea of what the difference between a
recursive and explicit formula is.  The former usually "refers" to
itself -- notice that in each case, the function F appears on both
sides of the equation, albeit for different values.  The latter,
however, does not in general have this property.  Note however that

G[n] = G[0] + n*G[1]

is not a recursive function, because G[0] and G[1] are constants which
do not depend on n.

-Doctor Pete,  The Math Forum
Check out our web site!  http://mathforum.org/dr.math/
```
Associated Topics:
High School Fibonacci Sequence/Golden Ratio
High School Sequences, Series

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search