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 is, you plug in 5 for n to get F[5-1] = F. But that's not much of an answer, is it? Well, what's F? We use the above formula again and we get F = F[4-1] = F. 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, 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 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 = 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 = 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, F = 1 Explicit: G[n] = (((1+Sqrt)/2)^n - ((1-Sqrt))^n)/Sqrt 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, G = 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 + n*G is not a recursive function, because G and G are constants which do not depend on n. -Doctor Pete, The Math Forum Check out our web site! http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.