In part nine of his series on Basic programming, Mark Moxon finishes off functions and procedures, and takes a look at the thorny problem of recursion
Last month we had a look at declaring local variables and found out why it is important to declare all the variables you invent for a certain procedure as local. Look on it as a precautionary measure; that way if you add your procedure to someone else's program - or even a program you wrote earlier - you don't have problematic variable clashes.
However, as we also saw, variables passed to routines are always local, so if we have a procedure defined as follows:
DEF PROCdouble(num) num=num*2 ENDPROC
you would have thought it would double the value in the variable passed to the procedure.
Go on, try it: it doesn't work. This is because every procedure automatically performs a LOCAL command on all the variables in the DEF line, so when the program comes to ENDPROC, the old value of num will be restored.
However, there is a way round this. All you have to do is include the word RETURN before any variables in the definition you want to be able to alter. So, to make our procedure alter the value of num and actually double it, we should change the definition to this:
DEF PROCdouble(RETURN num) num=num*2 ENDPROC
This version doubles the value of num, and prevents the old value of num being restored. There is one important point to be made here: when you call the procedure, the argument passed must be a variable, otherwise it doesn't make sense.
If you passed a number, for example three, then when the procedure ends it makes no sense to say 'and make sure the value of the argument remains changed', as It is a constant anyway.
Remember arrays, which we briefly talked about in the January issue? Well, just as you can pass numeric and string variables to procedures and functions, so you can pass arrays.
Let's take an example. In Listing 1 two arrays are set up in the procedure PROCinitialise, one containing first names - firstname$() - and the other surnames - surname$.
REM >Listing1 : ON ERROR REPORT:PRINT " at line ";ERL/10:END MODE 0 PROCinitialise PRINT "Press Esc to exit." REPEAT INPUT "Input a number between 1 and 5 ";num PRINT FNfullname(firstname$(),surname$(),num) UNTIL FALSE END : DEF PROCinitialise DIM firstname$(5),surname$(5) firstname$(1)="John":surname$(1)="SMith" firstname$(2)="Arthur":surname$(2)="Guinness" firstname$(3)="Joshua":surname$(3)="Tetley" firstname$(4)="Peter":surname$(4)="Dominic" firstname$(5)="Augustus":surname$(5)="Barnet" ENDPROC : DEF FNfullname(f$(),s$(),n) IF n<1 OR n>DIM(f$(),1) THEN ="Bad number" =f$(n)+" "+s$(n)
The function FNfullname then takes these two arrays as argument, and a number entered by you, and prints out the corresponding full name, complete with space between the names. Not that momentous, but it's easy to see how this would fit into an address book or simple database.
Have a look at the call to FNfullname, and the function definition. In both cases the first two variables passed have a couple of brackets after them, like so: firstname$() in the call, and f$() in the definition.
The brackets simply denote that an array is being passed, and we can assume when we are inside the function that an array has been created with the same dimensions as the argument passed.
The first line of the function simply checks that the number passed to the program is not less than one, or greater than the number of elements in the array. The expression DIM(f$(),1) simply returns the number of elements in the array f$().
If n is out of range, then the function returns the string 'Bad number', otherwise it takes the firstname and the surname from the array and returns the combination of the two as the result.
And, because we are using the DIM(f$(),1) function, we can rest assured that if we decide to extend the size of firstname$ to, say, 10 names, then FNfullname will still work correctly.
One final important point about passing arrays to procedures is that they are never local: arrays always act as if there was a RETURN in front if them in the procedure or function definition. So beware: if you pass an array to a routine, it can be changed, even without a RETURN.
Recursion is a really wild concept to try to get your head round. It basically involves a routine calling upon itself at some stage: scary if you think about it. How can the definition of a procedure contain somewhere in it a call to itself: a real chicken and egg situation, if ever I saw one.
The secret to understanding recursion is simple, but let's take an example first. Listing 2 contains a recursive function which generates anagrams, though not necessarily real ones, from a word you enter.
REM >Listing2 : ON ERROR REPORT:PRINT " at line ";ERL/10:END MODE 0 INPUT "Please enter a word ";word$ num=0 PROCanagram("",word$) PRINT "Number found ";num END : DEF PROCanagram(c1$,s$) LOCAL c2$,loop, rest$ CASE TRUE OF WHEN LEN(s$)>1 FOR loop=1 TO LEN(s$) c2$=MID$(s$,loop,1) rest$=LEFT$(s$,loop-1)+MID$(s$,loop+1) PROCanagram(c1$+c2$,rest$) NEXT loop WHEN LEN(s%)=1 PRINT c1$+s$ num=num+1 ENDCASE ENDPROC
It simply displays every anagram possible from any word you enter, and also the total number of anagrams possible. If we had a spelling checker to hand, we could check any anagrams found against that to create a real anagram generator.
Have a look at PROCanagram: it looks rather daunting at first, but bear with the explanation and it unravels itself rather neatly.
PRoCanagram takes two arguments, c1$ and s$, and prints out anagrams of s$, with the string c1$ appended to the front. So if we call the procedure like this:
then the program will print out anagrams of word$.
So why go through all this strange string appending? Well, the answer is so we can use recursion. Imagine we want to print all anagrams of a word. One way to do it is to take each letter of the word in turn, remove it from the word, and start the anagram with that letter. Then we simply need to work out all the anagrams of the word minus that letter, and write them down, putting the missing letter at the start of the anagram.
For example, for the word 'TWO', we would take out 'T' and write that down, followed by all the anagrams of 'WO', giving us `TWO' and `TOW'. Next we remove 'W' and find all the anagrams of 'TO', giving 'WTO' and 'WOT'. Finally, remove '0' to give 'OTW' and `OWT': now we've worked out all the anagrams of 'TWO'.
Now take a look at PROCanagram. The string passed in c1$ is the equivalent of the letters we have pulled out, and s$ is the rest of the word.
So, if s$ has more than one character, we step through it using the FOR-NEXT loop, plucking out each character in turn into c2$, and putting the rest of the word into rest$. Then we say to the program 'find all the anagrams of rest$ and print them with the removed letters tagged on the front', which equates to the call:
Assuming we have written PROCanagram correctly, this code will do what we want. The only case which needs to be dealt with is when s$ contains only one character, which means that we have our anagram, as there is only one permutation of one character. To print the anagram, we just use:
and that's all there is to it.
So the secret to understanding recursion is to assume that your procedure works, and make sure that the last case works - in this example, when there is only one character in the string. If that works, and you've written the procedure correctly, recursion becomes one of the most powerful tools in your arsenal.
That's all for this month: next month we'll be moving on to handling data from within your programs.
|Source:||Acorn User 141 - April 1994|