An Exercise In Recursion:
I rarely have the need to create a recursive program, but I have always been interested in the concept. My introduction to recursion was in my COC3110 class at the University of Florida in 1983. The problem was called "Eight Queens". The challenge was to place eight queens on a chessboard without ever being in danger of being taken by another (previously placed) queen.
This is a great example of a problem requiring "brute force". There is no fast and logical formula to determine where the eight queens should be placed. They just have to be placed on the chessboard, one at a time. Coding this by hand would get tedious and confusing after the first several placements. Fortunately that's just the kind of thing computers are built for!
Here is a flow chart for the "Eight Queens" problem:
Thus far, I have only had the opportunity to develop recursive programs when I need to document a complex structure of nested objects with any number of levels (or depth) possible. An example where recursion is a good programming choice would be in a system that finds links and relationships among a database of criminals, using some common criteria like phone numbers and known locations. For this exercise I will show how to display everything "under" a menu that conforms to the UniVerse menu subsystem.
Start with the following series of menus, paragraphs, and programs:
Note: All programming displayed on this site is for illustrative purposes only. Use at your own risk.
>.L MAIN.MENU
MAIN.MENU
001 M
002 APP.MENUS
003 MAIN.MENU
>MENUS
...
DISPLAY.MENU: CONTENTS OF THE MENU =--> MAIN.MENU ON =--> APP.MENUS
DESCRIPTION............................. ACTION..............
Data Entry DATA.ENTRY
Reports REPORTS
Administration ADMINISTRATION
1 records listed.
DISPLAY.MENU: CONTENTS OF THE MENU =--> DATA.ENTRY ON =--> APP.MENUS
DESCRIPTION............................. ACTION..............
A/R Data Entry AR.DATA.ENTRY
A/P Data Entry AP.DATA.ENTRY
1 records listed.
DISPLAY.MENU: CONTENTS OF THE MENU =--> REPORTS ON =--> APP.MENUS
DESCRIPTION............................. ACTION..............
A/R Detail Report AR.DETAIL.REPORT
A/R Summary Report AR.SUMMARY.REPORT
A/P Detail Report AP.DETAIL.REPORT
A/P Summary Report AP.SUMMARY.REPORT
1 records listed.
DISPLAY.MENU: CONTENTS OF THE MENU =--> ADMINISTRATION ON =--> APP.MENUS
DESCRIPTION............................. ACTION..............
Table Maintenance TABLE.MAINT.MENU
Printer Maintenance PRINTER.MAINT.MENU
User Maintenance USER.MAINT.MENU
1 records listed.
DISPLAY.MENU: CONTENTS OF THE MENU =--> TABLE.MAINT.MENU ON =--> APP.MENUS
DESCRIPTION............................. ACTION..............
Import from spreadsheet IMPORT.FROM.SPREADSHEET
Table Data Entry TABLE.DATA.ENTRY
1 records listed.
DISPLAY.MENU: CONTENTS OF THE MENU =--> PRINTER.MAINT.MENU ON =--> APP.MENUS
DESCRIPTION............................. ACTION..............
Set Default Printer SET.DEFAULT.PRINTER
Set Report Printer SET.REPORT.PRINTER
Set Check Printer SET.CHECK.PRINTER
Configure Default Printer CONFIG.DEFAULT.PRINTER
Configure Report Printer CONFIG.REPORT.PRINTER
Configure Check Printer CONFIG.CHECK.PRINTER
1 records listed.
DISPLAY.MENU: CONTENTS OF THE MENU =--> USER.MAINT.MENU ON =--> APP.MENUS
DESCRIPTION............................. ACTION..............
Add User ADD.USER
Modify User MODIFY.USER
Delete User DELETE.USER
1 records listed.
Admittedly the following program is overkill if the task at hand is to determine what a single menu or series of menus is doing. Even going through each of the menus, sub-menus, VOC items, and programs manually (with the EDitor) would be quicker than writing a program. Where this proves helpful is if the same type of task needs to be performed over and over again, with differently configured systems.
SUBROUTINE MENU.CRAWLER (out, atid, atrecord, offset, menu.cnt, menu.level)
*
* This is meant to be run from a VOC or VOCLIB I-type in a production account.
* The program will start with the paragraph or menu indicated by the @ID and
* recursively drill down and parse through any and all menus and paragraphs in
* a report and display the "external" components (paragraphs, programs, etc.).
*
* For example:
* LIST VOC "MAIN.MENU" EVAL 'SUBR("MENU.CRAWLER",@ID,@RECORD,0,1,1)' FMT "132L" ID.SUP COL.SUP HDR.SUP
*
* Arguments
* out : I-type display text
* atid : @ID is the record key
* atrecord : @RECORD is the menu/paragraph contents
* offset : Indentation factor
* menu.cnt : Menu item number
* menu.level: Anything greater than one is not a menu-level item
*
com /DISPMENU/ init,F.VOC,F.MENUS,F.NEWACC
equ true to 1
equ false to 0
default.menu.file = "APP.MENUS"
if not(init) then
*
* The first time through open files and initialize the output variable...
*
init = 1
out = ""
open '','VOC' to F.VOC else out<-1> = "Unable to open VOC!"; return
open '',default.menu.file to F.MENUS else out<-1> = "Unable to open ":default.menu.file:"!"; return
open '','NEWACC' to F.NEWACC else out<-1> = "Unable to open NEWACC!"; return
end
convert @VM to "" in atrecord ;* don't break on embedded valuemarks in column headings in LIST statements
first.line.processed = false ;* keep track of whether or not the first line of object has been processed
*
* Loop through the object, line by line, looking for known objects (menus, paragraphs) to drill down into...
*
loop
remove line from atrecord setting more
line = trim(line)
if len(line) then
*
* Account for everything in the object we DO NOT want to display...
*
begin case
case line[1,2] = "* " or line = "*"
case upcase(line) matches "'IF '1X0X"
case upcase(line) matches "'GO '1X0X"
case upcase(line) matches "1A0X':'0X" ;* Internal labels
case upcase(line) matches "'DISPLAY '1X0X" or upcase(line) = "DISPLAY"
* case upcase(line[1,7]) = "SELECT " ;* This may be something TO display
case upcase(line[1,11]) = "CLEARSELECT"
case upcase(line[1,5]) = "DATA "
case upcase(line[1,5]) = "SLEEP"
case upcase(line[1,1]) = "M" and not(first.line.processed) ;* Object is a menu
*
* Drill down into the menu...
*
first.line.processed = true
remove menu.file.name from atrecord setting dummy ;* Line two of menu record
remove menu.name from atrecord setting more ;* Line three of menu record
menu.read.error = false
if menu.file.name = default.menu.file then
read menu.record from F.MENUS, menu.name else
menu.read.error = true
out<-1> = "Unable to read ":default.menu.file:" '":menu.name:"'!"
end
end else
*
* This is not the default menu file. Open it and read the menu record...
*
open '',menu.file.name to F.TEMP.MENU then
read menu.record from F.TEMP.MENU, menu.name else
menu.read.error = true
out<-1> = "Unable to read ":menu.file.name:" '":menu.name:"'!"
end
end else
menu.read.error = true
out<-1> = "Unable to open ":menu.file.name:"!"
end
end
if not(menu.read.error) then
*
* Display the menu object...
*
menu.line = menu.cnt:" ":trim(menu.record<1>):" (":trim(menu.name):") (m)"
out<-1> = space(offset):menu.line
out<-1> = space(offset):str("=",len(menu.line))
*
* Iterate through the menu items...
*
menu.items = dcount(menu.record<3>,@VM)
for valcnt = 1 to menu.items
menu.item.name = menu.record<2,valcnt>
menu.item.cmd = menu.record<3,valcnt>
read dummy from F.NEWACC, menu.item.cmd then
*
* Command is a UniVerse delivered keyword or verb. Display it...
*
out<-1> = space(offset):menu.cnt:".":valcnt:" ":trim(menu.item.cmd)
end else
*
* Command is NOT a UniVerse delivered keyword or verb...
*
read voc.item from F.VOC, menu.item.cmd then
*
* Recursively drill down into the VOC item, increasing the indentation.
* Pass a literal one as the last argument to force the prefix of a menu #.
*
call MENU.CRAWLER(out, menu.item.cmd, voc.item, offset+2, valcnt, 1)
if false and out<dcount(out,@FM)> <> "" then ;* Remove false-flag for space between menu items
out<-1> = "" ;* blank line between menus
end
end else out<-1> = "Unable to read VOC, '":menu.item.cmd:"'!"
end
next valcnt
end
more = false
case upcase(trim(line[1,2])) = "PA" and not(first.line.processed)
*
* Display the paragraph name, and continue displaying any subsequent lines of interest...
*
first.line.processed = true
if menu.level < 2 then prefix = menu.cnt:" " else prefix = ""
out<-1> = space(offset):prefix:atid:" (pa)"
case upcase(line)[1,1] = "V" or upcase(line)[1,1] = "S" and not(first.line.processed)
*
* Verbs and Sentences always have the command in field two...
*
first.line.processed = true
if menu.level < 2 then prefix = menu.cnt:" " else prefix = ""
out<-1> = space(offset):prefix:atid:" (":downcase(line)[1,1]:")"
if atrecord<2> matches "'*'1X0X'*'1X0X" then
cmd = field(atrecord<2>,"*",3)
end else cmd = atrecord<2>
out<-1> = space(offset+2):" ":cmd
more = false
case 1
*
* Likely the rest of a paragraph. Look for standard verbs or paragraphs...
*
paragraph.cmd.word = field(line," ",1)
read dummy from F.NEWACC, paragraph.cmd.word then
*
* Command is a UniVerse delivered keyword or verb. Display it...
*
if len(line)+offset+2 > 100 then
line = line[1,97-(offset+2)]:"..." ;* indicate there is more that is not displayed
end
out<-1> = space(offset+2):line
end else
read voc.item from F.VOC, paragraph.cmd.word then
*
* Recursively drill down into the VOC item. Indicate another level deeper
*
call MENU.CRAWLER(out, paragraph.cmd.word, voc.item, offset+2, menu.cnt, menu.level+1)
end else
if len(line)+offset+2 > 100 then
line = line[1,97-(offset+2)]:"..." ;* indicate there is more that is not displayed
end
out<-1> = space(offset+2):line ;* Don't know what it is, but display it
end
end
end case
end
until not(more)
repeat
go exit
Exit:
*----
if offset = 0 then init = 0 ;* force reinitialization for subsequent runs (in the same session)
return
end
Based on the various menus, paragraphs, and programs that make up all of the nested structures "under" the main menu, the output of this subroutine is:
>LIST VOC "MAIN.MENU" EVAL 'SUBR("MENU.CRAWLER",@ID,@RECORD,0,1,1)' FMT "132L" ID.SUP COL.SUP HDR.SUP COUNT.SUP
1 Main Menu (MAIN.MENU) (m)
===========================
1 Data Entry (DATA.ENTRY) (m)
=============================
1 AR.DATA.ENTRY (s)
WINDOW AR.ENTRY
2 AP.DATA.ENTRY (s)
WINDOW AP.ENTRY
2 Reports Menu (REPORTS) (m)
============================
1 AR.DETAIL.REPORT (pa)
SET.REPORT.PRINTER (s)
SETPTR 0,80,58,1,1,1,BRIEF,NHEAD,NFMT,AT <<F(CONFIG.FILE,PRINTER.REPORT,1),Printer,1X0X>>
LIST ACCOUNTS.RECEIVABLE @DETAIL BY FUND BREAK.ON FUND BY ACCOUNT BREAK.ON ACCOUNT BY CREDI...
2 AR.SUMMARY.REPORT (pa)
SET.REPORT.PRINTER (s)
SETPTR 0,80,58,1,1,1,BRIEF,NHEAD,NFMT,AT <<F(CONFIG.FILE,PRINTER.REPORT,1),Printer,1X0X>>
LIST ACCOUNTS.RECEIVABLE @SUMMARY BY FUND BREAK.ON FUND BY ACCOUNT BREAK.ON ACCOUNT BY CRED...
3 AP.DETAIL.REPORT (pa)
SET.REPORT.PRINTER (s)
SETPTR 0,80,58,1,1,1,BRIEF,NHEAD,NFMT,AT <<F(CONFIG.FILE,PRINTER.REPORT,1),Printer,1X0X>>
LIST ACCOUNTS.PAYABLE @DETAIL BY FUND BREAK.ON FUND BY ACCOUNT BREAK.ON ACCOUNT BY CREDI...
4 AP.SUMMARY.REPORT (pa)
SET.REPORT.PRINTER (s)
SETPTR 0,80,58,1,1,1,BRIEF,NHEAD,NFMT,AT <<F(CONFIG.FILE,PRINTER.REPORT,1),Printer,1X0X>>
LIST ACCOUNTS.PAYABLE @SUMMARY BY FUND BREAK.ON FUND BY ACCOUNT BREAK.ON ACCOUNT BY CRED...
3 Administration (ADMINISTRATION) (m)
=====================================
1 Table Maintenance (TABLE.MAINT.MENU) (m)
==========================================
1 IMPORT.FROM.SPREADSHEET (v)
IMPORT.FROM.SPREADSHEET
2 TABLE.DATA.ENTRY (v)
TABLE.DATA.ENTRY
2 Printer Maintenance (PRINTER.MAINT.MENU) (m)
==============================================
1 SET.DEFAULT.PRINTER (s)
SETPTR 0,80,58,1,1,1,BRIEF,NHEAD,NFMT,AT <<F(CONFIG.FILE,PRINTER.DEFAULT,1),Printer,1X0X>>
2 SET.REPORT.PRINTER (s)
SETPTR 0,80,58,1,1,1,BRIEF,NHEAD,NFMT,AT <<F(CONFIG.FILE,PRINTER.REPORT,1),Printer,1X0X>>
3 SET.CHECK.PRINTER (s)
SETPTR 0,80,58,1,1,1,BRIEF,NHEAD,NFMT,AT <<F(CONFIG.FILE,PRINTER.CHECK,1),Printer,1X0X>>
4 CONFIG.DEFAULT.PRINTER (s)
WINDOW DEFINE.PRINTER "DEFAULT"
5 CONFIG.REPORT.PRINTER (s)
WINDOW DEFINE.PRINTER "REPORT"
6 CONFIG.CHECK.PRINTER (s)
WINDOW DEFINE.PRINTER "CHECK"
3 User Maintenance (USER.MAINT.MENU) (m)
========================================
1 ADD.USER (v)
ADD.USER
2 MODIFY.USER (v)
MODIFY.USER
3 DELETE.USER (v)
DELETE.USER
When there are repeated patterns with references to other data structures, and there is a varying number of nested references to have to contend with, then consider using recursion to do the heavy lifting.
No comments:
Post a Comment