As soon as a program becomes longer than a few lines it is probably more convenient to think of it as a sequence of steps, each step being written as a separate 'routine', an independent piece of program which can be tested in isolation, and which can be incorporated into other programs when the same function is needed.
Sections of program can be isolated from the rest of the program using a BASIC construction called the 'subroutine'. In the main program a statement such as:
GOSUB 1000
causes control to be transferred to the statement at line 1000. The statements from line 1000 comprise the subroutine. The subroutine is terminated by a statement:
RETURN
which causes a jump back to the main 'calling' program to the statement immediately following the GOSUB 1000. It is just as if the statements from 1000 up to the RETURN statement had simply been inserted in place of the GOSUB 1000 statement in the main program.
As an example, consider the following program:
10 A=10 20 GOSUB 100 30 A=20 40 GOSUB 100 50 END
100 PRINT A ' 110 RETURN
Lines 100 and 110 form a subroutine, separate from the rest of the program, and they are terminated by RETURN. The subroutine is called twice from the main program, in lines 20 and 40. The program, when RUN, will print:
10 20 >
6.1.1 Chequebook-Balancing Program
As a more serious example, consider a program for balancing a chequebook. The program will have three distinct stages; reading in the credits, reading in the debits, and printing the final amount. We can immediately write the main program as:
10 REM Chequebook-Balancing Program 20 PRINT "ENTER CREDITS"' 30 GOSUB 1000 40 PRINT ”ENTER DEBITS"' 50 GOSUB 2000 60 PRINT "TOTAL IS" 70 GOSUB 3000 80 END
Now all we have to do is write the subroutines at lines 1000, 2000, and 3000!
The subroutines might be written as follows:
1000 REM Sum Credits in C 1010 REM Changes C,J 1020 C=0 1030 DO INPUT J; C=C+J 1040 UNTIL J=0 1050 RETURN
2000 REM Sum Debits in D 2010 REM Changes D,J 2020 D=0 2030 DO INPUT J; D=D+J 2040 UNTIL J=0 2050 RETURN
3000 REM Print Total in T 3010 REM Changes T; Uses C,D 3020 T=C-D; @=5 3030 PRINT T/100," POUNDS",T%100," PENCE" 3040 RETURN
Values are entered in pence, and entering zero will terminate the list of credits or debits.
The two subroutines at 1000 and 2000 are strikingly similar, and this suggests that it might be possible to dispense with one of them. Indeed, the main part of the chequebook-balancing program can be written as follows, eliminating subroutine 1000:
10 REM Chequebook-Balancing Program 20 PRINT "ENTER CREDITS" 30 GOSUB 2000 40 C=D 50 PRINT "ENTER DEBITS" 60 GOSUB 2000 70 PRINT "TOTAL IS" 80 GOSUB 3000 90 END
In conclusion, subroutines have two important uses:
1. To divide programs into modules that can be written and tested separately, thereby making it easier to understand the operation of the program.
2. To make it possible to use the same piece of program for a number of similar, related, functions.
As a rough guide, if a program is too long to fit onto the screen of the VDU it should be broken down into subroutines. Each subroutine should state clearly, in REM statements at the start of the subroutine, the purpose of the subroutine, which variables are used by the subroutine, and which variables are altered by the subroutine. A few moments spent documenting the operation of the subroutine in this way will save hours spent at a later date trying to debug a program which uses the subroutine.
The GOSUB statement is just like the GOTO statement that has already been described, in that it can be followed by a line number, an expession evaluating to a line number, or a label. Labels are of the form a to z, and the first line of the subroutine should contain the label immediately following the line number.
6.2.1 Linear Interpolation
The following program uses linear interpolation to find the roots of an equation using only integer arithmetic, although the program could be modified to use floating-point statements.
The equation is specified in a subroutine, y, giving Y in terms of X; the program finds solutions for Y=0.
As given, the program finds the root of the equation:
x2 - x - 1 = 0
The larger root of this equation is phi, the golden ratio. A scaling factor of S=1000 is included in the equation so that calculations can be performed to three decimal places.
The program prompts for two values of X which lie either side of the root required.
1 REM Linear Interpolation
5 S=1000; @=0; I=1
10 INPUT "X1",A,"X2",B
20 A=A*S; B=B*S
30 X=A; GOSUB y; C=Y
40 X=B; GOSUB y; D=Y
50 IF C*D<0 GOTO 80
60 PRINT "ROOT NOT BRACKETED"
70 END
80 DO I=I+1
90 X=B-(B-A)*D/(D-C); GOSUB y
100 IF C*Y<0 THEN A=X; C=Y; GOTO 120
110 B=X; D=Y
120 UNTIL ABS(A-B)<2 OR ABS(Y)<2
130 PRINT"ROOT IS X="
140 IF X<0 PRINT "-"
145 PRINT ABS(X)/S,"."
150 DO X=ABS(X)%S; S=S/10
155 PRINT X/S; UNTIL S=1
160 PRINT'"NEEDED ",I," ITERATIONS."'
170 END
200yY=X*X/S-X-1*S
210 RETURN
Description of Program:
5-70 Check that starting values bracket a root
80-120 Find root by successive approximation
130-145 Print integer part of root
150-155 Print decimal places
160 Print number of iterations needed
200-210 y: Subroutine giving Y in terms of X, with appropriate
scaling.
Variables: A - Lower starting value of X B - Upper starting value of X C - Value of Y for X=A D - Value of Y for X=B I - Iteration number S - Scaling factor; all numbers are multiplied by S and held as integers. X - Root being approximated Y - Value of equation for given,X Program size - 466 bytes
Sample run: >RUN X1?1 X2?3 ROOT IS X= 1.618 NEEDED 7 ITERATIONS.
Often the task carried out by a subroutine may itself usefully be broken down into a number of smaller steps, and so it might be convenient to include calls to subroutines within other subroutines. This is perfectly legal, and subroutines may be nested up to a maximum depth of 15 calls.
Sometimes a problem can be more simply expressed if it is allowed to include a reference to itself. When a subroutine includes a call to itself in this way it is known as a 'recursive' subroutine call, and it is possible to use recursive calls in ATOM BASIC provided that the depth of recursion is limited to 15 calls. The following half-hearted program uses a recursive call to print out ten stars without using a loop:
10 REM Recursive Stars 20 P=10; GOSUB p 30 END
100pREM Print P stars 110 IF P=0 RETURN 120 P=P-1 130 GOSUB p; REM Print P-1 stars 140 PRINT "*" 150 RETURN
This program could, of course, be written more effectively using a simple FOR...NEXT loop. The following programs, however, use recursion to great benefit to solve mathematical problems that would be much harder to solve using iteration alone.
In the Tower of Hanoi problem three pegs are fastened to a stand, and there are a number of wooden discs each with a hole at its centre. The discs are all of different diameters, and they all start on one peg, arranged in order of size with the largest disc at the bottom of the pile.
The problem is to shift the pile to another peg by transferring one disc at a time, with the restriction that no disc may be placed on top of a smaller disc. The number of moves required rises rapidly with the number of discs used; the problem was classically described with 64 discs, and moving one disc per second the solution of this problem would take more than 500,000 million years!
A recursive solution to the problem, stated in words, is:
To move F discs from peg A to peg B: 1. Move F-1 discs to peg C. 2. Move bottom disc to peg B. 3. Move F-1 discs to peg B.
Also, when F is zero there is no need to do anything. Steps 1 and 3 of the procedure contain a reference to the whole procedure, so the solution is recursive.
The following program will solve the problem for up to 13 discs, and displays the piles of discs at every stage in the solution:
1 REM Tower of Hanoi 10 PRINT$12 20 A=TOP;D=A+4 40 V=-3;W=-1 60 !D=#1020300;!A=0 70 INPUT"NUMBER OF DISCS "F 80 A?1=F;?D=F 85 N=64/3 90 CLEAR0 100 FORQ=1TOF;MOVE(F-Q),(2*(F-Q));PLOTl,(2*Q-1),0;NEXT 110 GOSUBh;END 1000hIF?D=0 RETURN 1010 D!4=!D-1;D?6=D?1;D?5=D?2;D=D+4;GOSUBh 1020 MOVE(F-D?-4+D?V*N-N),(D?V?A*2);PLOT1,(D?-4*2-1),0 1030 MOVE(D?W*N-N),(D?W?A*2-2);PLOT3,(F+D?-4),0 1040 A?(D?W)=A?(D?W)+W;A?(D?V)=A?(D?V)-W 1050 D?3=D?-2;D?2=D?W;D?1=D?V;GOSUBh 1060 D=D-4;RETURN
Description of Program: 100 Draw starting pile of discs 110 Subroutine h is called recursively to move the number of discs specified in ?D. 1000 h: Subroutine to move ?D discs 1010 Recursive call to move ?D-1 discs 1020 Draw new disc on screen 1030 Remove old disc from screen 1040 Set up array A 1050 Recursive call to put back ?D-1 discs
Variables: A?N - Number of discs on pile N D - Stack pointer ?D - How many discs to transfer D?1 - Destination Pile D?2 - Intermediate pile D?3 - Source pile F - Total number of discs N - One third of screen width V - Constant W - Constant
Program size: 461 bytes Stack usage: (4 * number of discs) bytes
A classical mathematical problem consists of placing eight queens on a chessboard so that no queen attacks any other. The following program find all possible solutions to the problem, and draws a diagram of the board to show each solution as it is found. The program uses many abbreviations to keep it small enough to fit on an unexpanded ATOM (for a complete explanation of these abbreviations, see section 10.1):
1 REM Eight Queens
30 C=0;D=TOP;E=D+3;A=D+27;!D=0
60 @=0;GOS.t;P.$13"THERE ARE "C" SOLUTIONS"';END
100tIF?D=#FF C=C+1;GOTOd
110 ?A=(?D\D?1\3?2):#FF
120lIF?A=OR.
130 A?1=?A&-?A
140 ?E=?D\A?1;E?l=(D?1\A?1)*2;E?2=(D?2\A?1)/2
150 D=D+3;E=E+3;A=A+2;GOS.t;D=D-3;E=E-3;A=A-2
160 ?A=?A&(A?1:#FF);GOT01
200dCLEAR0;FORZ=0T032S.4;MOVE0,Z;DRAW31,Z;MOVEZ,0;DRAWZ,32;N.
210 Q=0;FORZ=3TO34STEP3;P=TOP?Z-Q;S=-2;DOS=S+4;P=P/2;UNTILP=0
220 Q=TOP?Z;PLOT13,(Z/3*4-2),S;N.;{P.$30 C;R.
Description of Program:
30 Initialise array space. D is vector of attacks, ?D is row attacks,
D?1 is left diagonal attacks, D?2 is right diagonal attacks.
60 Call recursive analyser and print answer.
100 t: Recursive analyser: if all rows attacked have found a solution.
110 Calculate possible places to put new queen.
120 If no possible place, end this recursive attempt.
130 Find least significant bit in possible places to use as new
queen position.
140 Calculate new attacked values.
150 Recursive call of analyser.
160 Remove this position from possible position and see if done.
200 d: Have solution, display board matrix.
210 Plot pixels at positions of queens.
220 Print the solution number at screen top and end recursion.
Variables: ?A - Possible position; value of A changes C - Solutions counter ?D - Row attacks; value of D changes E - Holds D+3 to make program shorter
Program size: 440 bytes Vectors: 30 bytes Total storage: 470 bytes.