|
|
|
|
|
|
Section 10 - Recursion
It is possible for an HP program to call itself. This is called recursion. There are many cases in mathematics and computer science where recursion is an effective tool. Three classical examples are given below. The first two demonstrate effective uses of recursion, the third is an example of where recursion should NOT be used.
The first example is n factorial. This can be defined recursively as
0! = 1
n! = n(n-1)! for n = 1, 2, 3, ...
This can be coded recursively as follows:
<<IF DUP 0 == THEN DROP 1
ELSE DUP 1
- NFCT * END >>
Key this into your calculator and save it as NFCT. Try it with 0 and 6. You should get 1 and 720 respectively. This is
better than the built in factorial function (LS MTH NXT F1-PROB F3-!) because it always gives and integer answer. The
built in function converts to scientific notation at 15!, but it does give exact answers up to 17! because the missing digits are
all zeros. At 18!, however, this program gives the exact value of 6402373705728000 while the built in function gives
6.40237370573E15. The use of 
in sample program QDEQ was simply part of the output beautification process, but
in this program it is necessary to keep the calculator working in integer mode to get the extra accuracy.
The second example is a binary search, which is a very fast way for finding an element of an ordered list. The program is written to "guess" that the middle element is the one being sought. If it is, the task is finished. If it is not, then the element being sought is to the left or to the right of the middle, so we recursively search the left half or the right half of the list, as the case may be. Suppose, for example, that we have the following list of records in the calculator, where each record is a list consisting of a record number and a name. This file is on Web. To download it, click here.
NLST = { { 103 "BOB BUBBLES" } { 107 "DOLLY DULL" } { 123 "ANNY ANCHOR" } { 130 "QUINCY QUICK" } { 141 "LARRY LUCKY" } { 173 "HELEN HAPPY"} { 211 "ULMA UPSY" } { 229 "VIOLET VOCAL" } { 256 "OLGA OLF" } { 277 XAVIOR XANY" } { 282 "MARK MUMPS" } { 298 "WALTER WACKY" } { 317 "FRED FREEK" } { 333 "YOLANDA YELLER" } { 361 "NELL NURDY" } { 375 "TOM TALL" } { 380 "KATHY KRUNCH" } { 381 "PAT PICKLE" } { 382 "ZELDA ZILCH" } { 383 "JIM JELLY" } { 384 "SANDY SLIM" } { 385 "ED ELFY" } { 409 "CHUCK CHUNKY" } { 419 "RICH RAGS" } { 423 "IRMA IRKY" } { 431 "GUSS GUSHY" } }.
The objective is to write a program that will prompt the user for a record number and return the name of the corresponding person, or "NOT FOUND" if the number is not in the list. The solution is given below. The first program is a recursive binary search that takes the list, the first element to be searched, the last element to be searched, and the target number from the stack and returns the location of the required record, or zero if the record is not found. The second program prompts for the record number, sets up the stack to start the recursive process, and calls the search program. If the record was found it accesses the record and outputs the name, if the record was not found it outputs "NOT FOUND" to a message box.
<<s a b t << IF a b > THEN 0 ELSE a b + 2 / CEIL
c << s c GET 1 GET IF DUP t == THEN DROP c ELSE IF t > THEN s a c 1 - ELSE s c 1 + b END t BSCH END >> END >> >>
Save the above program as BSCH.
<< NLST DUP 1 SWAP SIZE "Enter record number" "" INPUTBSCH IF DUP 0 == THEN DROP "NOT FOUND" ELSE NLST SWAP GET 2 GET END MSGBOX >>
Save the above program as FIND. Enter the data set and try the program by pressing FIND. Study BSCH and make sure you understand how it works. Notice that BSCH will work on any list of records so long as the record number is the first element in the record. FIND, however, is specific to this particular list of records.
Another application of BSCH is to delete an element from the list. The following program prompts the user for a record number, sets up the stack for the recursive process and calls the search program. If the record was found, it is deleted from the list NLST. If the record is not found, "NOT FOUND" is output to the stack.
<< NLST DUP 1 SWAP SIZE "Enter record number" "" INPUTBSCH IF DUP 0 == THEN DROP "NOT FOUND" ELSE
n << CASE n 1 = THEN NLST TAIL END NLST SIZE n == THEN NLST REVLIST TAIL REVLIST END NLST 1 n 1 - SUB NLST n 1 + NLST SIZE SUB + END 'NLST' STO "RECORD DELETED" >> END MSGBOX >>
Save the above program as DELT. Save NLST with another name so you can restore it to the original after trying DELT, Be sure you understand how it all works.
The last example is using recursion to find the Fibonacci numbers. These are defined by
F0 = 0, F1 = 1, and Fn = Fn-1 + Fn-2 for n = 2, 3, 4, ...
This is easily coded as
<<n << IF n 1
THEN n ELSE 'FIBR(n-1)' EVAL n 2 - FIBR + END >> >>
Enter the above program and save it as FIBR. Notice that we have used two different methods for the recursive calls, algebraic: 'FIBR(n-1)' EVAL, and using RPN logic: n 2 - FIBR. There is no particular advantage of one method over the other, it was simply our intent to demonstrate both. Use the program to evaluate F6 = 8.
Any program that can be written recursively can also be written as a loop. Below is a version of the Fibonacci program written as a loop.
<<n << IF n 1
THEN n ELSE 0 1 2 n START SWAP OVER + NEXT SWAP DROP END >> >>
Enter the above program and save it as FIBL. It is not nearly as elegant or easy to follow as the recursive version, but try finding F10 with both programs and you will easily see the advantage of the loop version. When recursion applies, it usually makes programming much easier, but as this example shows, it must be used with caution.
EXERCISE SET 10
1. One source of recursive formulas in mathematics is in the infinite series solutions to differential equations. A typical case for a second order differential equation has the form
a0 = 1, a1 = 1, aj = f(j)aj-2 for j = 2, 3, 4, ...
where f(j) is some function of j. The solution of the differential equation is then
where b0 and b1 are given by the initial conditions.
(a) Write a recursive procedure called FNDA that will evaluate the a's given by
a0 = 1, a1 = 1, 
for j = 2, 3, 4, ...
(b) Write a program called FNDC that will prompt for the initial conditions b0 and b1 and output the values of the coefficients
through the coefficient of t9. The output should be tagged.
2. Alter BSCH so that given a new record number it returns the location where the new record should be inserted to maintain the list in order or a zero if the record number already exists. Call the new version SRHB. Write a program that prompts the user for the number and name of a new record. It should use SRHB to find where the new record should be inserted or if the record number already exists. It should then insert the new record into NLST or give an error message if the record number already exists. Call this program NSRT. Put NLST and all the programs associated with it into a directory and create a custom menu for that directory with FIND, NSRT, and DELT. See page 20-2 of UG for instructions on how to create a custom menu.
|
|
|
|
|
|