- Advanced Algorithms
|
The NetRexx Tutorial
- Advanced Algorithms
|
Introduction
Recursive Algorithms A question that usually crops up in discussion groups about languages (notably comp.lang.rexx) is : 'Can I implement a recursive algorithm using REXX?'. The answer is: 'Yes'. You can easily make your NetRexx (or REXX) code re-entrant, and in this way implement any recursive algorithm. You perform this with a method clause.
The towers of Hanoi. Text books usually provide as an example of recursive algorithm, the computation of a factorial (n!). This is probably not a good choice, as one can easily avoid recursion for this algorithm. I prefer to give the example of the 'Towers of Hanoi' [ KRUSE, 1984, 273 ]. The game is well known: one must move disks from one 'tower' (1) to a third (3), without placing a larger disk on top of a smaller.
(1) (2) (3)
| | |
# | |
### | |
##### | |
####### | |
######### | |
########### | |
---------------------------------------------------------
Towers of Hanoi
Using recursion, the solution is extremely simple. Taking the algorithm from the cited source, we can write this small REXX program.
+----------------------------------------------------------------------+
| class hanoi |01
| method move(n=rexx,a=rexx,b=rexx,c=rexx) public static |02
| if n>0 then |03
| do |04
| move(n-1,a,c,b) |05
| say 'Move disk from' a 'to' b '.' |06
| move(n-1,c,b,a) |07
| end |08
| |09
| method main(args=String[]) public static |10
| n = args[0] |11
| move(n,1,2,3) |12
| exit 0 |13
| |14
+----------------------------------------------------------------------+
hanoi.nrx
| 
|
Download the source for the hanoi.nrx example
Believe it or not, this is the solution you get from the program. Note that it is also the best possible solution.
...................................................................
rsl3pm1 (122) java hanoi1 4
Move a disk from 1 to 2 .
Move a disk from 1 to 3 .
Move a disk from 2 to 3 .
Move a disk from 1 to 2 .
Move a disk from 3 to 1 .
Move a disk from 3 to 2 .
Move a disk from 1 to 2 .
Move a disk from 1 to 3 .
Move a disk from 2 to 3 .
Move a disk from 2 to 1 .
Move a disk from 3 to 1 .
Move a disk from 2 to 3 .
Move a disk from 1 to 2 .
Move a disk from 1 to 3 .
Move a disk from 2 to 3 .
rsl3pm1 (122)
...................................................................
result of the hanoi1 program
|
In the section about the curses() interface we will see how to get a better output for the solution of the game.
Recursive sort algorithms
+----------------------------------------------------------------------+
| -- method......: partition |18
| -- purpose.....: |19
| -- |20
| method partition(l=rexx[],low=rexx,high=rexx) public static returns|21
| swap(l,low,(low+high)%2) -- swap pivot in 1st location |22
| pivot = l[low] |23
| lastsmall = low |24
| loop i = low+1 to high |25
| if l[i] < pivot then |26
| do |27
| lastsmall = lastsmall + 1 |28
| swap(l,lastsmall,i) -- move large to right, small to|29
| end |30
| end |31
| swap(l,low,lastsmall) -- put pivot into its proper pos|32
| pivotlocation = lastsmall |33
| return pivotlocation |34
| |35
+----------------------------------------------------------------------+
qsn.nrx(Method:partition)
|
|
Download the complete source for the qsn.nrx library
Removing recursion
+----------------------------------------------------------------------+
| -- method......: sort_qsnr |68
| -- purpose.....: sort the list using QuickSort Nonrecursive |69
| -- |70
| method sort_qsnr(l=rexx[]) public static |71
| |72
| maxstack = 20 -- up to 1,000,000 items |73
| lowstack = rexx[maxstack] -- arrays used for the st|74
| highstack = rexx[maxstack] |75
| |76
| low = 0 -- list bounds |77
| high = l.length - 1 |78
| |79
| nstack = 0 |80
| |81
| loop until nstack = 0 |82
| if nstack > 0 then |83
| do |84
| low = lowstack[nstack] -- pop the stack |85
| high = highstack[nstack] |86
| nstack = nstack - 1 |87
| end |88
| |89
| loop while low < high |90
| pivotloc = partition(l,low,high) |91
| |92
| -- push larger list into stack, and do the smaller |93
| -- |94
| if (pivotloc - low) < (high - pivotloc) then |95
| do |96
| -- stack right sublist and do left |97
| -- |98
| if nstack > maxstack then overflow() |99
| nstack = nstack + 1 |00
| lowstack[nstack] = pivotloc + 1 |01
| highstack[nstack] = high |02
| high = pivotloc - 1 |03
| end |04
| else |05
| do |06
| -- stack left sublist and do right |07
| -- |08
| if nstack > maxstack then overflow() |09
| nstack = nstack + 1 |10
| lowstack[nstack] = low |11
| highstack[nstack] = pivotloc - 1 |12
| low = pivotloc + 1 |13
| end |14
| end |15
| end |16
| |17
+----------------------------------------------------------------------+
qsn.nrx(Method:sort_qsnr)
|
|
Download the complete source for the qsn.nrx library
+----------------------------------------------------------------------+
| -- method......: main |44
| -- purpose.....: just test the main functions simply running |45
| -- "java qsn" |46
| -- |47
| method main(args=String[]) public static |48
| args = args |49
| |50
| l = rexx[100] |51
| build_list(l) |52
| display_list(l) |53
| sort_qsnr(l) |54
| display_list(l) |55
| |56
| exit 0 |57
+----------------------------------------------------------------------+
qsn.nrx(Method:main)
|
|
Download the complete source for the qsn.nrx library
*** This section is:*** and will be available in next releases
Summary Here is the usual resume' of some of the concepts we have encountered in this chapter:
*** This section is: