Recursive functions in BASIC

User avatar
stefano
Posts: 592
Joined: Tue Dec 11, 2012 9:24 am
Contact:

Recursive functions in BASIC

Post by stefano »

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.
recursive_factorial.png
recursive_factorial.png (8.12 KiB) Viewed 5938 times

EDIT: I just noticed this trick is also described in RosettaCode
dr beep
Posts: 2341
Joined: Thu Jun 16, 2011 8:35 am
Location: Boxmeer

Re: Recursive functions in BASIC

Post by dr beep »

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")
dr beep
Posts: 2341
Joined: Thu Jun 16, 2011 8:35 am
Location: Boxmeer

Re: Recursive functions in BASIC

Post by dr beep »

I even had a recursive HANOI solution printed in a string.
dr beep
Posts: 2341
Joined: Thu Jun 16, 2011 8:35 am
Location: Boxmeer

Re: Recursive functions in BASIC

Post by dr beep »

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))
dr beep
Posts: 2341
Joined: Thu Jun 16, 2011 8:35 am
Location: Boxmeer

Re: Recursive functions in BASIC

Post by dr beep »

Lardo Boffin
Posts: 2236
Joined: Sat Nov 26, 2016 2:42 am

Re: Recursive functions in BASIC

Post by Lardo Boffin »

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
dr beep
Posts: 2341
Joined: Thu Jun 16, 2011 8:35 am
Location: Boxmeer

Re: Recursive functions in BASIC

Post by dr beep »

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.
Recursion in general or this BASIC-method with DEF FN?

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.....
Lardo Boffin
Posts: 2236
Joined: Sat Nov 26, 2016 2:42 am

Re: Recursive functions in BASIC

Post by Lardo Boffin »

dr beep wrote: Thu Jul 18, 2024 8:50 pm
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.
Recursion in general or this BASIC-method with DEF FN?

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.....
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.
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
dr beep
Posts: 2341
Joined: Thu Jun 16, 2011 8:35 am
Location: Boxmeer

Re: Recursive functions in BASIC

Post by dr beep »

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.
I once had a query in a tool and it needed a recursive search to do the job,
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
User avatar
1024MAK
Posts: 5343
Joined: Mon Sep 26, 2011 10:56 am
Location: Looking forward to summer in Somerset, UK...

Re: Recursive functions in BASIC

Post by 1024MAK »

It helps if you understand the mechanism used by DEF FN and FN.

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...
Post Reply