Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
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

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/