Recursive functions in BASIC
Recursive functions in BASIC
This is a trick me and my cousin discovered back in those days, I had to fiddle with the ZX Spectrum emulator.
There are several ways to get to the same result, this one looks reasonably readable.
The trick relies on two very powerful features we have on the ZX Spectrum, DEF FN() and VAL.
DEF FN is, on the interpreter perspective, very similar to a GOSUB, yet it is a function and the return point will be inside an expression being evaluated. VAL issues a separate interpreter task to translate whatever we have in a string into a numeric value.
When FN is launched, it needs to recursively call itself many times, which is easy but we need to find a way to break the loop.
What we can do is to alter the string content when x reaches the expected limit to force a constant.
EDIT: I just noticed this trick is also described in RosettaCode
There are several ways to get to the same result, this one looks reasonably readable.
The trick relies on two very powerful features we have on the ZX Spectrum, DEF FN() and VAL.
DEF FN is, on the interpreter perspective, very similar to a GOSUB, yet it is a function and the return point will be inside an expression being evaluated. VAL issues a separate interpreter task to translate whatever we have in a string into a numeric value.
When FN is launched, it needs to recursively call itself many times, which is easy but we need to find a way to break the loop.
What we can do is to alter the string content when x reaches the expected limit to force a constant.
EDIT: I just noticed this trick is also described in RosettaCode
Re: Recursive functions in BASIC
Code: Select all
10 Def Fn D$(n,s$)=val$ (("s$+fn D$(n-1,s$)" And N>0)+("""""" And N=0))
20 Print Fn D$(10,"abc")
Re: Recursive functions in BASIC
I even had a recursive HANOI solution printed in a string.
Re: Recursive functions in BASIC
Decimal to binary
Code: Select all
1 DEF FN b$(d)=VAL$ ((CHR$ 19
3+"d" AND d<=1)+(("FN b$(INT (d/
2))+"+CHR$ 193+STR$ ((d/2)<>INT
(d/2))) AND d>1))
-
- Posts: 2236
- Joined: Sat Nov 26, 2016 2:42 am
Re: Recursive functions in BASIC
I consider myself to be a reasonably competent programmer (I spend a fair amount of my professional life doing it) but reading stuff like this still blows my mind.
ZX80
ZX81 iss 1 (bugged ROM, kludge fix, normal, rebuilt)
TS 1000 iss 3, ZXPand AY and +, ZX8-CCB, ZX-KDLX & ChromaSCART
Tatung 81 + Wespi
TS 1500 & 2000
Spectrum 16k (iss 1 s/n 862)
Spectrum 48ks plus a DIVMMC future and SPECTRA
ZX81 iss 1 (bugged ROM, kludge fix, normal, rebuilt)
TS 1000 iss 3, ZXPand AY and +, ZX8-CCB, ZX-KDLX & ChromaSCART
Tatung 81 + Wespi
TS 1500 & 2000
Spectrum 16k (iss 1 s/n 862)
Spectrum 48ks plus a DIVMMC future and SPECTRA
Re: Recursive functions in BASIC
Recursion in general or this BASIC-method with DEF FN?Lardo Boffin wrote: ↑Thu Jul 18, 2024 8:05 pm I consider myself to be a reasonably competent programmer (I spend a fair amount of my professional life doing it) but reading stuff like this still blows my mind.
During my study (1987) I coded a recursive mazegenerator in Pascal and got a message from IT to quit the program since it generated over 100K on a stack. I now have a mazegenerator in less than 1K on the ZX81 although not recursive anymore.....
-
- Posts: 2236
- Joined: Sat Nov 26, 2016 2:42 am
Re: Recursive functions in BASIC
I don’t have much call for recursion in my job (aside from occasional data validation of complex hierarchical structured data in TSQL) so mostly the DEF FN as shown.dr beep wrote: ↑Thu Jul 18, 2024 8:50 pmRecursion in general or this BASIC-method with DEF FN?Lardo Boffin wrote: ↑Thu Jul 18, 2024 8:05 pm I consider myself to be a reasonably competent programmer (I spend a fair amount of my professional life doing it) but reading stuff like this still blows my mind.
During my study (1987) I coded a recursive mazegenerator in Pascal and got a message from IT to quit the program since it generated over 100K on a stack. I now have a mazegenerator in less than 1K on the ZX81 although not recursive anymore.....
ZX80
ZX81 iss 1 (bugged ROM, kludge fix, normal, rebuilt)
TS 1000 iss 3, ZXPand AY and +, ZX8-CCB, ZX-KDLX & ChromaSCART
Tatung 81 + Wespi
TS 1500 & 2000
Spectrum 16k (iss 1 s/n 862)
Spectrum 48ks plus a DIVMMC future and SPECTRA
ZX81 iss 1 (bugged ROM, kludge fix, normal, rebuilt)
TS 1000 iss 3, ZXPand AY and +, ZX8-CCB, ZX-KDLX & ChromaSCART
Tatung 81 + Wespi
TS 1500 & 2000
Spectrum 16k (iss 1 s/n 862)
Spectrum 48ks plus a DIVMMC future and SPECTRA
Re: Recursive functions in BASIC
I once had a query in a tool and it needed a recursive search to do the job,Lardo Boffin wrote: ↑Thu Jul 18, 2024 9:20 pm I don’t have much call for recursion in my job (aside from occasional data validation of complex hierarchical structured data in TSQL) so mostly the DEF FN as shown.
An expert said it was not possible but I solved it. Problem was an IF was not possible but I solved it with boolean algebra and an empty string to return,
a bit like the DEF FN on the ZX Spectrum
- 1024MAK
- Posts: 5342
- Joined: Mon Sep 26, 2011 10:56 am
- Location: Looking forward to summer in Somerset, UK...
Re: Recursive functions in BASIC
It helps if you understand the mechanism used by DEF FN and FN.
Mark
Mark
ZX81 Variations
ZX81 Chip Pin-outs
ZX81 Video Transistor Amp
Standby alert
There are four lights!
Step up to red alert. Sir, are you absolutely sure? It does mean changing the bulb
Autumn is here. Bye bye summer 2024...
ZX81 Chip Pin-outs
ZX81 Video Transistor Amp
Standby alert
There are four lights!
Step up to red alert. Sir, are you absolutely sure? It does mean changing the bulb
Autumn is here. Bye bye summer 2024...