Module 7: Discrete Mathematics
702 : Recursion
Gregory Moore
P U R P O S E
In this module, we'll examine recursion in various forms and from symbolic, numeric, and geometric points of view.
_______________________________________________________________________________________
A. Explicit & Recursive Sequences
For a sequence to be defined explicitly, there must be a function or rule that allows the computation of any member of the sequence.
> restart;
> s := k -> 3*k +2;
> seq( s(k), k = 1..12);
The basic idea of a recursively defined sequence is that the defiition of each term depends on one or more previous terms. There are two basic components. First, you need a starting value which acts as a seed for the rest of the sequence. Next, you need a rule which tells you how to compute one term, given the previous one. Together these two components form the recursive definition.
> s||1 := 1;
> for k from 2 to 10 do s||k := 3*s||(k-1) +2; od;
In a sense, the explicitly defined sequence allows for random access to any element in the sequence with direct computatioin, while a recursive definition requires the computation of all of the elements prior to the desired element in a sequential manner. Clearly an explicit definition is more convenient in this way. However, many sequences are much more easily defined by recursive definitions. Here is an example of the Fibonacci numbers.
> FF||0 := 0; FF||1 := 1;
> for k from 2 to 10 do FF||k := FF||(k-1) + FF||(k-2); od;
There is an explicit formula for this sequence, which we will see later in this module, however, it is a not an extremely simple not easily found formula.
B. Resolving 1st Order Recurrences
One of our goals is to take recursively defined sequences, or recurrences, and find explicit definitions for the same sequence. We will start with "1st order recurrences" which are recurrences which only depend on a single previous term at a time.
Maple has a specific command, rsolve, to solve recurrences. Lets see how it works. Here is the recursive definition of a sequence, followed by the rslove command. The final command, seq, is a way of then evaluting this function to find the first 20 elements of the sequence.
> { f(n) = f(n-1) + 9, f(0) = 7};
> rsolve( %, f(k));
> seq( subs( k = j, %), j = 0..20);
This can also be done in slightly more compact way as follows.
> rsolve( {f(n) = 3 * f(n-1), f(0) =1 }, f(k));
> seq(subs(k = j, %) , j = 0..10);
C. 2nd Order Recurrence
A 2nd recurrence is a recurively defined sequence which depends on two previous terms to find each additional term. Many of these sequences have more complicated formulas. The method is essentially the same. One difference is that there needs to be two seed values to start the process.
> rsolve( { f(n) = f(n-1) + 2*f(n-2), f(0..1) = 1}, f(k));
> seq( subs( k =j, %), j = 0..10);
D. Recursive Procedures
Another aspect to recursion is its application to computer programming and Maple programming. As in most computer languages ( such as Pascal , C++, and Fortran ) its possible to define procedures or functions. Maple allows for this same capability. In particular, we can use this method to define recursive procedures and examine how they work.
Here is an example of a recursive procedure to compute the factorial of a number. For example, 5 factorial is 5! = 5 4 3 2 1 = 120. Of course, Maple already has this command built in, but we,re going to use it as an example of defining our own procedures. The procedure should be entered in its entirety at one command prompt. You can enter multiple lines without executing by hitting RETURN ( Macitosh ) or SHIFT - RETURN (Windows ).
> fact := proc(n) if n = 0 then 1; else n*fact(n-1); ; fi; end:
The name of the procedure is fact. It receives a value of n and if that value is 0 , it returns the value of 1. Otherwise, it returns n times the value of the procedure evaluated at n - 1. In Maple, the if - then - else - fi is a decision command that allows one of two outcomes depending on the condition - in this case the whether or not n = 0 is a true statement. Lets see what happens when we use this procedure.
> fact(5);
> fact(1);
> fact(10);
As you can see, this procedure apparently computes the factorial of what ever number we give it. Here is another version of the procedure. This version makes the same computation, but also prints out the intermediate values and the current value of n. This provides a window to what is going on inside the procedure.
> fact := proc(n) local x; print( cat("n=",n)); if n = 0 then print("- - - bottom of the heap - - -"); 1; else x := fact(n-1); print( cat("n=", n, " fact(",n,")=", x)); n*x; fi; end:
>
The procedure works its way down to the bottom where n = 0, then works it way back up gradually forming the product that will be the final result.
Here is an example of a procedure to create the Fibonacci sequence which shows its inner working.
> fib := proc(n) print(n); if (( n = 1) or ( n = 2)) then print(` - - - bottom of the heap - - - n = ` ,n); 1; else fib(n - 1) + fib(n - 2); fi; end:
> fib(4);
> fib(6);
E. Recursive Expressions & Fixed Points
Related to this concept, there are also expressions which are recursively defined such as This can be thought of as a recursively defined sequence such as ,.... . We can express this as a recurrence f(n) = where f( 1 ) = 0 :. Unfortunately, the rsolve command can not resolve this kind of recurrence. However, we can deal with this in another way. We can simply define a function based on this recurrence, then iterate the function - that is repeatedly compose the function with itself and evaluate at 1.
> f := x -> sqrt( 1 + x);
> f(f(0));
> f(f(f(0)));
We can iterate the function 10 times by repeatedly composing it with itself in this way.
> (f@@10)(x);
In fact, we can see what is happening by doing this in a loop.
> for k from 1 to 12 do (f@@k)(0) = evalf( (f@@k)(0)); od;
> for k from 1 to 12 do evalf( (f@@k)(0) ); od;
It appears that the values are converging to a number around 1.618033989. But how can we find the exact value o the expression? Suppose for a moment that the values of f( n ) where identical. Lets say x = f(n) = f(n+1) = ...... Then the recursion would become x = , or more generally, f(x) = x. If we simply solve that equation for x, we will have our answer.
> f(x) = x;
> solve( %,x); evalf(%);
A value for which f(x) = x, is called a fixed point .
F. Newton's Method
An example of a recursive formula is Newton's Method for finding roots of a function. This method requires that you be familiar with a little bit of Calculus. Newton's Method is to start with a guess for what a root may be. The initial guess is x0 , then repeatedly apply this formula
to get better and better guesses. In many cases, the formula will converge to the value of a root fairly quickly. Lets start with a function f(x), and then define the function N(x) to give the next guess according to Newton's method
> f := x -> x^2 -2;
> N := x -> x - f(x)/ D(f)(x);
Like any recursive definition, we start with
> x||0 := 1;
> for k from 1 to 10 do x||k := evalf( N(x||(k-1))) od ;
The values seem to converge quite quickly. The actual solution is this.
> sqrt(2) : % = evalf(%);
G. Geometric View of Recursive Convergence
The subject of fixed points of recursions is an interesting one for many reasons and one we can investigate algebraically, numerically, and geometrically. We will need the following special plot function.
> restart; with(plots):
Warning, the name changecoords has been redefined
> rec_plot := proc( f1, a , b, x0) local x1, x2, y1, y2, i , p1, p2, p3, n, a1,a2; x2 := x0; y2:= 0; n :=10; for i from 1 to n do x1 := x2; y1 := y2; y2:=f(x1); x2 := y2; p1[i] := plot( [[x1, y1], [x1, y2]], x = a..b, color =red): p2[i] := plot( [[x1, y2], [x2, y2]], x = a..b , color = yellow): od: display( plot( f1(x), x = a..b, thickness = 3, color = blue), plot(x, x = a..b, thickness = 1, color = black), seq( p1[i], i = 1..n), seq( p2[i], i = 1..n) ); end:
Here is a recursive formula.
> f := x -> (x+6)/2;
> x||0 := 2;
> for k from 1 to 16 do x||k := evalf( f(x||(k-1) )); od;
It appears to converge but to where exactly? We can use the same method of finding the fixed point as used above.
> f(x) = x; solve(%, x);
A geometric view of this situation will show not only the convergence but also the steps leading to the convergence.
> left := 0; right := 7; start:=2;
> rec_plot( f(x), left, right, start);
The thick blue line is the function f(x). The thin black line is the line y = x. Each of the vertical red lines indicates a new xk. The yellow lines show how the y values "bounce" off of the black y = x line to become new xk values. Finally the green oval indicates where the values converge within a small distance of one another.
