Recursive BASIC Subroutines

Earl Wuchter
Catasauqua, PA

A simple game illustrating a most sophisticated topic. The idea of recursive subroutines is one of the more complex notions in programming — a subroutine which is its own subroutine. "Towers of Brahma," a child's game with pegs and disks, is used to illustrate how recursion works with versions here for PL/I and Microsoft (Commodore, Apple, OSI) and Atari BASICs.

Recursive (adj): of, relating to, or constituting a procedure that can repeat itself indefinitely, or until a specified condition has been met.

Subroutine (n): a sequence of computer instructions for performing a specified task that can be used repeatedly in a program or in different programs.

— Webster's New Collegiate Dictionary

Used together, these two words describe one of the most powerful, and most fascinating entities in programming, but it is a rare bird.

Recursive subroutines are most useful in compiled languages, but are seldom allowed. On the other hand, an interpreted language like BASIC can't help but allow a subroutine to reenter itself, but some serious problems must be overcome before the technique is of any use.

The problem with BASIC is that all variables are global. (When any variable is changed in a subroutine it is changed for the whole program.) To see what is missing in BASIC, look at a call statement and a subroutine statement in a typical compiled language. The variables in parentheses are called arguments or parameters:

CALL TRY (A,X)
SUBROUTINE TRY (A,Z)

When TRY is invoked, A and Z will take on the values of A and X from the calling routine. On return, A and X will receive the values of A and Z. Even though both routines use the variable A, the A in the calling routine will not be changed until a return is executed. The status (global or local) of other variables is normally up to the programmer.

BASIC subroutines do not have arguments. The normal programming practice is to have the calling routine assign values to subroutine variables before the GOSUB is executed. To prevent a subroutine from inadvertently affecting any other routine, we give it a set of local variables by using names that do not appear in any other routine.

A Solution to Passing BASIC Variables

Now you can see the problem with recursive code. How can we give a subroutine a set of variables that are different from those in the calling routine when they are one and the same routine?

There is a solution. We can create an array of arguments and have each generation of the subroutine use its own "row" in the array.

The Towers Of Brahma

The "Towers of Brahma" is one problem that is best solved with a recursive subroutine. The solution, in turn, best illustrates the capability of recursive code. The two seem to have been made for each other.

This interesting mathematical problem is often found disguised as a child's toy: a board with three pegs and four or five disks of varying diameters that fit on the pegs. The disks are initially arranged on the first peg in order of their diameters, with the smallest one on top. They are to be moved one at a time, always keeping the smaller ones on top, until they are on the third peg.

Towers of Brahma

When the recursive solution to this problem is coded in the proper language, it is a thing of beauty. A PL/I version of the subroutine is shown below. This will be the model for a BASIC version. The main routine is not shown. The main routine simply inputs the number of disks and makes the initial call:

CALL MOVE (NDISKS,1,3);

Note: In this version of PL/I, arguments passed in as expressions become dummy arguments and do not change anything in the calling routine. Adding zero to a variable makes it an expression without altering its value. This feature provides for extremely compact code.

MOVE: PROCEDURE (N,F,T) RECURSIVE;
IF N = 0 THEN RETURN;
CALL MOVE (N-1,F + 0,6-F-T);
PUT SKIP DATA (N,F,T);CALL MOVE (N-l, 6-F-T, T + 0);
END MOVE;

Brief Definitions Some of the terms used in this article might be unfamiliar. Here's a short description of the main ideas: CODE – Refers to the statements, the lines, or the entirety of a program, as in the phrase "there's an error in your code at line 110." Also used as a verb, as another word for programming: "I'm coding a subroutine." COMPILED LANGUAGE – Unlike BASIC (an interpreted language) there are three steps to getting a program to run when you're working with a compiled language: 1. Write it. 2. Compile it. 3. Run it. After you write the program, a separate program called a compiler translates what you've written into a form of machine language. This results in a program which can then be executed (run). Some examples of compiled languages are FORTRAN, COBOL, and PL/I. The language the program is written in (step 1, above) is called the source language and when you finish typing it you've got not surprisingly, the source program. Step 2 is where you instruct the compiler to "examine" and transform the source program into an executable (it can be executed) program called the object or target program. You can write, easily read, and easily modify source programs, but you can't run them. Object programs, on the other hand, do run, but they are difficult to read (they're not written in words like PUT IF THEN DECLARE, but rather in machine or assembly language.) INTERPRETED LANGUAGE – Step 2 (above) does not take place in an interpreted language. There are only two steps to writing an interpreted language program (BASIC is an example): 1. Write it. 2. RUN it. However, while the program is RUNning, a separate program in the computer is "interpreting" the meaning of words like PRINT and INPUT. In other words, the computer slows down somewhat while the interpreter decides what PRINT means and just what kind of PRINT is involved (to the screen, the printer, a disk file?). Then the interpreter sets up pointers and flags and variables and momentarily sends control to the machine language subroutine (in a library of such subroutines) which can do a PRINT. All of this translating and interpreting is going on during the RUN of the program. It's obvious why interpreted programs tend to RUN more slowly than compiled programs. On the other hand, because you can write it/RUN it, it is easier to test parts of a program immediately and make the necessary changes to the program itself. Debugging is easier simply because the program you write is the same program that you will RUN. PARAMETER PASSING – This generally refers to the ways that variables are made available to several programs at once, (or, if the variables are local, to several parts of the same program at once). For example, if the variable CASH "holds" 15.98, we might want to "pass" that value (15.98, the parameter) to another program. Some computers will cancel all variables when a new program is LOADed into RAM memory. How can the 15.98 be "passed" to the hew program ? Likewise, if variables are local, the value of CASH will be different in subroutines from what is in the main body of the program unless 15.98 is "passed" to the subroutines. Passing parameters is handled in different ways depending on which computer or language is being used. Compiled languages often allow you to put the variables in parentheses on the same line as a CALL to or RETURN from a subroutine. The example CALL SUB3 (CASH, TOTAL) passes the values of CASH and TOTAL to the subroutine SUB3. It can later pass variables back to the main routine in the same way, using parameters (also called arguments). PL/I – A "high level" language (as opposed to lower level, closer to machine language) which combines attributes of FORTRAN and COBOL. DUMMY ARGUMENTS – Parameters which have no effect other than to take up some necessary space. An example is the FRE(1) statement in Microsoft BASICS where the value within the parentheses can be anything. It's just there because the computer will not recognize FRE(). NESTING — When something is contained by something else. FOR I = 1 TO 10 : FOR J = 1 TO 2 : NEXT J : NEXT I. This J loop is said to be nested within the I loop. STACK — The computer must be able to remember "return addresses." 100 GOSUB 500 will turn over control to whatever is on line 500, but eventually there will be a RETURN. So, before GOSUBbing, the "address" to RETURN to is put on the computer's stack and later pulled off the stack by RETURN. There is a limit to how many return addresses can be pushed on the stack. This is normally no problem since most subroutines go right back via RETURN, relieving the stack of the address number. Recursive, self-calling subroutines, however, aren't RETURNing. It's GOSUB-GOSUB-GOSUB, etc. Unless the recursion is carefully managed, the stack could quickly fill with return addresses and is then said to overflow.

The BASIC program has arrays for variables N, F, and T. Variable G serves as the index to the arrays. G represents the number of nested GOSUBs. The subroutine increments G on each entry and decrements it on each return, thereby keeping count of its own generation number. Arguments are passed to the next generation by putting values into the arrays at (G + 1) before each GOSUB. The variable G is always the current subscript for any generation of the subroutine.

This method of using arrays requires that you know beforehand what the maximum nesting depth will be in order to dimension the arrays. This number is a function of the problem, but may be limited by the BASIC interpreter.

Solving 21 Disks Would Take More Than Eight Days

The program runs in less than 2K. The internal stack size of my PET restricts the number of disks to 21. When I try to run more than 21 I get an "OUT OF MEMORY" message. Your system may allow more or less, but don't expect to run this many disks to completion. The time required to complete 21 disks (at a rate of approximately three moves per second) will be more than eight days, and one more disk would double that.

The BASIC program here shows the moves to be made, along with a plot of the nesting level made down the left side of the screen. Each increase in the length of the plotted line indicates a GOSUB. Each decrease in length indicates a RETURN. You can see a more detailed view of the process by replacing the plot with a printout of the current array variables.

Program 1. Microsoft Version

10 REM TOWERS OF BRAHMA (RECURSIVE)
11 DIM N(22), F(22), T(22)
12 P$ = "----+----+----+----+--"
13 INPUT"N DISKS (1 TO 21) ";N(1)
14 IFN(1)<1 OR N(l)>22 THEN 13
15 F(1) = l
16 T(1) = 3
17 GOSUB 31
18 END :::::::::::::::::::::::
31 G = G + 1
32 PRINT LEFT$(P$,G)
33 IF N(G) = 0 THEN 43
34 N(G + 1) = N(G)-1
35 F(F + 1) = F(F)
36 T(G + 1) = 6-F(G)-T(G)
37 GOSUB 31
38 PRINT TAB(19) "DISK#"N(G) "FROM"F(G)"TO"T(G)
39 N(G + 1) = N(G)-1
40 F(G + 1) = 6-F(G)-T(G)
41 T(F + 1) =T(F)
42 GOSUB 31
43 G = G-1
44 PRINT LEFT$(P$, G)
45 RETURN

Program 2. Atari Version

11 DIM N(22), F(22), T(22), P$(20)
12 P$="----+----+----+----+---"
13 ? "N DISKS (1 TO 21)" : INPUT T : N(1) = T
14 IF T<1 OR T>21 THEH 13
15 F(1) = 1
16 T(1) = 3
17 GOSUB 31
19 END
31 G = G + 1
32 IF G THEN ? P$(1,G)
33 IF N(G) = 0 THEN 43
34 N(G + 1) = N(G) - 1
35 F(G + 1) = F(G)
36 T(G + 1) = 6-F(G)-T(G)
37 GOSUB 31
38 ? "DISK #"; N(G);" FROM ";F(G);" TO ";T(G)
39 N(G + 1) = N(G)-1
40 F(G + 1) = 6-F(G)-T(G)
41 T(G + 1) = T(G)
42 GOSUB 31
43 G = G-1
44 IF G THEN ? P$(1, G)
45 RETURN