Linked Lists & Recursion, Part 1

PASCAL, and descendant languages such as MODULA and ADA, are very structured compared to BASIC. All variables must be identified before use, Procedures and Functions (ie subroutines) must all appear before the main program and the punctuation required is “persnickity” to the extreme. These requirements are all well and good For large commercial use since the programs become easier to read and easy to change. However, for smaller applications and home use; I believe a person writing in BASIC can be done and walking away long before a person using PASCAL has his program debugged. Notwithstanding, PASCAL supports two neat features, Linked Lists and Recursion, which few books in BASIC will discuss. This article shows how you can add Linked Lists and Recursion to your BASIC programming tools.

LINKED LISTS

Linked Lists involve one or more variables and one or more pointers together in a Record. The Record can be called up for use much like a dimensioned variable. The pointer (s) in a Record point to the location of another Record. For a single variable (a) and a single pointer (p), a sketch of a Linked List would look like this:

In PASCAL, Linked Lists need not be dimensioned beforehand and can expand forever (within the limits of computer memory). A disadvantage is that one cannot immediately go to a variable. In the sketch above, one cannot go directly to a100 but must go thru a1, a2, a3,….,a98, a99 beforehand. The powerful feature of a Linked List is that a pointer may be easily changed to point to another variable. In the above sketch, pointer p0 could be changed to point to a100 and p100 changed to point to a1. As a result, one doesn’t have to move data around so as to arrange the data in some new order. Changing a two column pointer is much faster than moving an 80 column data item.

BASIC can closely approximate a Linked List with pointers by dimensioning a variable p, one greater than the Data dimension. Figure 2 shows a list of 15 random sets of letters. To place this list in alphabetical order without change in the original list, follow the pointers on the right.

The first pointer says goto index 10 (AWA…). The pointer at index 10 says go to index 8 (BER…), the pointer at 8 says go to 3 (CLY…) and so on. Following the pointers places the list in alphabetical order. In some data structures, pointers can save a great deal of memory since incoming data is simply stored in order of arrival and kept in order by their pointers. Another example of pointers is shown later.

RECURSION

The other neat feature supported by PASCAL is Recursion. Recursion is breathtaking in that a three or four line recursion program can do the equivalent of a 10 to 20 line non-recursive program. In addition, there are some problems that can be done only by recursion. Recursion take a leap in faith to understand, but it works. There are three rules to set up a recursive program. These rules are directions rather than laws and I will give several examples.

A multi-step recursive problem must have:

1. A Base Case (step 1 or the last step) that completes the problem. 2. There must be n-1 subproblems that approach the solution or make the problem smaller. 3. Assume that each subproblem is solved correctly and check that when combined, all subproblems including the base case will solve the original problem.

Without going into PASCAL or BASIC, let’s look at some examples of recursion:

N FACTORIAL (N!) is the product of 123….N. Thus 3! is 6, 4! is 24, 5! is 124, etc. A recursive function to find N. could look like this:

 Factorial(N)
   1. If N=1 then return 1      ; Base case
   2. Otherwise return N*Factorial(N-1)

Notice in step 2 that the function calls itself. For 4!, step 1 fails so step 2 says the problem is now 43!. 3! is called and 3! is called and step 2 says the problem is now step 32!. Eventually, the number in step 2 reduces down to 1 and step 1 pops with an answer. The most recent call of step 2 gets an answer giving the next call of step 2 an answer and thru the daisy chain step 2 returns: ((12)3)*4=24 as the final answer.

A similiar problem would be the sum of N numbers:

 Sum(N)
   If N=1 then return 1
   Otherwise return N+Sum(N-1)

A nice example of recursion is the game of Hanoi, where discs of decreasing size are on peg “start”. The problem is to move the discs, one at a time, to another peg without covering a smaller disc with a larger-ending with all discs on peg “end”. Let h be the number of discs on peg start and assume that we have a function MOVE(peg1, peg2) that will move the top disc of pegi to peg2.

Then by observation, our base case is: If h=1 then MOVE(start, end)

Now look at a situation where all the discs but the largest are on the middle peg. The statement MOVE(start, end) moves the largest disc over and we can then call Hanoi again as a new problem, one disc. smaller, moving discs from the one size smaller middle peg to the end.

 HANOI(start,middle,end,h)
  If h=1 then MOVE(start,end)
  Else HANOI(start,end,middle,h-1)
       MOVE(start,end)
       HANOI(middle,start,end,h-1)

HANOI has all the features of a good recursion program:

1. A base case with one disc.
2. • a (With a big leap of faith) Move all the smaller discs to the middle peg.
   • b Move the largest disc to its final position.
   • c Call the whole routine again as a new problem with h-1 discs to go from the middle peg to the end.
3. 3. With only four programming steps, any number of discs can be moved from the start peg to the end!

The question is: How can recursion be done in BASIC? The way that PASCAL supports recursion is that all the variable values are stored at the time of each call and held until the return. In BASIC, all variables are global In BASIC, (applicable to the whole program) and there is no automatic facility to store away special values.

For example, look at the Factorial function. We originally let N=4. The Factorial routine set N=3,2,1 at each call and knew which value of N belonged to each call. Without some special storage and release of proper N values, a BASIC recursion program becomes a disaster.

One way to supply this “automatic” identifiable storage is to use subroutines named PUSH and POP. PUSH stores away our special values and POP can bring them back. Let’s build the Factorial subroutine in BASIC.

   50 DIM v(100): REM to hold temp values of N during recursion
   60 LET indx=0: LET answ=1
   70 LET PUSH=500: LET POP=550: LET FACTORIAL=100
   80 INPUT "N";N: GOSUB FACTORIAL: STOP

  490 REM Subroutine PUSH
  500 LET indx=indx+1: LET v(indx)=N: RETURN
  
  540 REM Subroutine POP
  550 LET N=v(indx): LET indx=indx-1: RETURN

The recursive kernel becomes:

   90 REM Subroutine FACTORIAL
  100 IF N=1 THEN RETURN
  110 GOSUB PUSH: LET N=N-1: GOSUB FACTORIAL
  120 GOSUB POP: LET answ=answ*N
  125 PRINT N,answ
  130 RETURN

Step 125 is instructive since it shows all the values of N popping out as needed.

Recursive HANDI (below) is a fun program in BASIC. It includes a print routine showing the disc movement. If we let the start peg=1, temp (middle) peg=2, end peg=3 and h=number of discs, then these four values must be stored as the peg locations get swapped around and the h number reduces.

The recursive kernel is:

  IF h= THEN GOSUB MOVEse
  GOSUB SWAPet: GOSUB HANOI
  GOSUB POP: GOSUB MOVEse
  GOSUB SWAPst: GOSUB HANOI
  GOSUB POP: RETURN

The SWAP subroutines PUSH existing values of s,t,e,h and SWAP the indicated values of e,t or s,t. This changes direction of the reduced height of discs when HANDI is recursively called (eg “move the reduced height from the middle peg to the end.”).

Variables:

• S(),T(),E(),H() – PUSH, POP storage for peg values and h.
• p(3,h+1) – Identity of discs on each peg.
• q(3) – Number of discs on each peg.
• horig – Starting value of h

   10 REM .. RECURSIVE HANOI.. 
   20 REM by Dale Fritz 
   30 PRINT "Enter no of discs ";: INPUT h: PRINT h 
   40 DIM S(100): DIM T(100): DIM E(100): DIM H(100) 
   50 DIM p (3, h+1): DIM q(3): LET Indx=1: LET horig=h 
   55 LET S=1: LET t=2: LET e=3 
   60 LET HANOI=100: LET PUSH=300: LET POP=400: LET SWAPet=500: LET SWAPst=600: LET MOVEse=700: LET PRINT=800 
   70 FOR i=1 TO h: LET p(1,i)=h+1-i: NEXT i: LET q(1)=h 
   80 GOSUB PRINT: GOSUB HANOI: STOP

   90 REM .. SR HANOI.. 
  100 IF h=1 THEN GOSUB MOVEse: RETURN 
  110 GOSUB SWAPet: GOSUB HANOI 
  120 GOSUB POP: GOSUB MOVEse 
  130 GOSUB SWAPst: GOSUB HANOI 
  140 GOSUB POP: RETURN

  290 REM ..SR PUSH. 
  300 LET indx=indx+1: LET S(indy)=s: LET T(indx)=t: LET E(indx)=e: LET H(indx)=h 
  310 RETURN

  390 REM .SR POP. 
  400 IF INDX=0 THEN RETURN 
  410 LET S=S(indx): LET t=T(indx): LET e=E(indx): LET h=H(indx): LET indx=indx-1 
  420 RETURN 

  490 REM . SR PUSH, SWAP (e,t) 
  500 GOSUB PUSH: LET temp=e: LET e=t: LET t=temp: LET h=h-1 
  510 RETURN

  590 REM .. SR PUSH, SWAP(s,t) 
  600 GOSUB PUSH: LET temp=s: LET s=t: LET t=temp: LET h=h-1 
  610 RETURN

  690 REM ..SR MOVE (s,e).. 
  700 LET q(e)=q(e)+1: LET p(e,q(e))=p(s,q(s)) 
  710 LET p(5, q(s))=0: LET q(s)=q(s)-1 
  720 GOSUB PRINT 
  730 RETURN

  790 REM SR PRINT
  800 FOR I=horig TO 1 STEP-1: FOR j=1 TO 3 
  810 IF P(j,i)=0 THEN PRINT "     ";: GO TO 830 
  820 PRINT P(j,i);"     "; 
  830 RETURN