This work is licensed under a Creative Commons License.
The first thing to note about this document is that it isn't really intended for beginners: you'll need to understand some of the less-used features of Spectrum BASIC, including DEF FN, VAL, string slicing and the values returned by the logical operators AND and OR, as well as a little bit of maths. That said, even if you don't follow all the technical details, you may discover something interesting, so do keep reading.
A function which calls itself. Such a function will also need some form of termination in which it doesn't call itself or we'll never get an answer (more on this later...). This is probably best illustrated by an example: mathematicians define the factorial of a positive integer n (written as n! and pronounced as “n factorial” or occasionally “n bang”) as n × n - 1 × n - 2 × … × 3 × 2 × 1. For example, this means that 6! = 6 × 5 × 4 × 3 × 2 × 1 = 720. A little bit of thought will show that we can have a slightly different definition of the factorial function: for any integer n greater than 1, we have n! = n × (n-1)!. As mentioned before, we need some way of terminating this sequence, and we can do this by defining 1! = 1.
Let's start with a non-recursive definition of the factorial function:
10 INPUT "n? "; n 20 LET f = 1 20 FOR i = 1 TO n 30 LET f = f * i 40 NEXT i 50 PRINT n;"! = ";f
That's nice and simple, but not particularly useful if we want more to get the factorial of more than one number in a program. We can obviously put it into a subroutine if we want that:
1000 REM Factorial function 1010 REM Given a positive integer n, returns f = n! 1020 REM Side-effects: i is undefined after execution 1020 LET f = 1 1030 FOR i = 1 TO n 1040 LET f = f * i 1050 NEXT i 1060 RETURN
That's OK, but still not particularly nice. Let's say we want to calculate 2! + 3!; with our current implementation, we'd need something like:
100 LET n = 2 110 GOSUB 1000 120 LET x = f 130 LET n = 3 140 GOSUB 1000 150 LET x = x + f 160 PRINT "2! + 3! = ";x
Fortunately, Spectrum BASIC has a way of making this kind of thing a lot neater, and that's our good friend DEF FN. Given a suitable definition of FN f, we can just write x = FN f(2) + FN f(3) and we're there. So, what's the problem? Spectrum BASIC allows only expressions in a user-defined function, not statements like FOR.
We can rewrite our current implementation to avoid the FOR loop by using our alternative recursive definition of n!:
1100 REM Factoral function v2 1110 REM Given a positive integer n, returns f = n! 1120 REM Side-effects: n is defined after execution 1130 LET f = 1 1140 IF n = 1 THEN RETURN 1150 LET f = f * n 1160 LET n = n - 1 1170 GO TO 1140
That still has the IF which we can't use in a function, but we'll see how to get rid of that later.
Looking at our recursive definition of n! above, a little thought will show that the "core" of any function definition will be something like DEF FN f(n)=n * FN f(n-1). Unfortunately, this will never terminate, so attempting to calculate any factorials with this will just result in an infinite loop. How can we cause the function to end when n = 1?
At this point, the logical functions come to our aid. While these are usually used simply in an IF clause, they do return values in their own right: x AND y is x if y is non-zero, and zero if y is zero. Hence you might think that something like:
DEF FN f(n) = ( 1 AND n = 1 ) + ( n * FN f( n - 1 ) AND n <> 1 )
will do the trick. If you can't see what it does, look at what happens when n is equal to 1, and when it's not (refer to the definition of x AND y above). Unfortunately, it's not as simple as all that. When n = 1, we know that the expression ( n * FN f( n - 1 ) AND n <> 1 ) will always evaluate to zero as n <> 1 is untrue (and therefore zero), so AND n <> 1 will always be zero, no matter what is. However, Spectrum BASIC doesn't have this form of logic (called “short circuit evaluation”), and so evaluates even though it's going to throw its value away. This is more than just a little annoying for us, as it means we still haven't managed to close off the recursion and get an answer. Hence we need to find a different way to stop the Spectrum evaluating the “unwanted” term.
Note the following:
"AlphaBeta"( 1 TO 5 ) = "Alpha"
"AlphaBeta"( 6 TO 9 ) = "Beta"
Now, by applying the same sort of trick we used to select one expression or the other in the DEF FN above, we can select one string or the other:
"AlphaBeta"( 1 + ( 5 AND i <> 0 ) TO 5 + ( 4 AND i <> 0 ) )
By using this little maneuver, we can slice a string before it's evaluated, and then call VAL on the sliced string to get the result we want:
"2+34*5+6"( 1 + ( 3 AND i <> 0 ) TO 3 + ( 5 AND i <> 0 ) )
Or, coming back to our recursion function:
"1n*FN f(n-1)"( 1 + ( 1 AND n <> 1 ) TO 1 + ( 9 AND i <> 1 ) )
(If you're using a non-keyword machine like the 128K, you'll have to type that as "1n*" + CHR$( 168 ) + "f(n-1)"; thanks to Crisis for pointing this out). When calculating the slicing limits, remember that “FN ” and other keywords count as one character. Hence, our (almost) final function:
10 DEF FN f(n)=VAL "1n*FN f(n-1)"( 1 + ( 1 AND n <> 1 ) TO 1 + ( 9 AND i <> 1 ) ) 20 PRINT FN f(6) 30 PRINT FN f(2) + FN f(3)
There are a couple of small optimisations we can make to this: firstly, we already have a “1” in the string, so there's no need to use another character at the start:
10 DEF FN f(n)=VAL "n*FN f(n-1)"( 8 - ( 7 AND n <> 1 ) TO 8 + ( 1 AND i <> 1 )
Now, 7 AND n<>1 is equivalent to 7 * ( n <> 1 ), and 1 AND n <> 1 is equivalent to just n <> 1, so we can reduce slightly further to:
10 DEF FN f(n)=VAL "n*FN f(n-1)"( 8 - 7 * ( n <> 1 ) TO 8 + ( n <> 1 ) )
We note here that we're no longer using AND at all. However, it's a useful trick for more complicated recursive functions, so it's worth remembering about. The other thing worth noting is that this whole VAL thing is slow, so don't be relying on any of this for speed. On the other hand, if you're writing in BASIC, you're probably not too bothered about speed anyway!
There you go. Hope it was interesting. Any comments, corrections, etc to philip-spectrum@shadowmagic.org.uk.
This work is licensed under a Creative Commons License.