Exploring Recursion in BASIC

[almightytodd]

My apologies for hijacking the topic on LOGO programming on the TI 99/4A computer. I think it's best to continue the conversation in this new thread. I was browsing the Rosetta Code website when I stumbled upon this Recursive example of the Fibonacci sequence on the Sinclair Z81.

 10 INPUT N
 20 LET A=0
 30 LET B=1
 40 GOSUB 70
 50 PRINT B
 60 STOP
 70 IF N=1 THEN RETURN
 80 LET C=B
 90 LET B=A+B
100 LET A=C
110 LET N=N-1
120 GOSUB 70
130 RETURN

I was quite surprised to see how similar it was to my second attempt at demonstrating recursion in BASIC using a subroutine.

 

...a quick style note:  I prefer to start BASIC Programs with line 100 - allowing for a zeroth line number for a remark naming the program. This also allows for 99 lines of code without any changes in indentation of the line numbers - retaining ten lines between each for the insertion of other lines. I prefer to number all subroutines in the thousands; creating a visual "break" between the "Main" routine and the subroutines.

 

In the Fibonacci example above, the sequence is not created; rather the nth Fibonacci value is returned based on input "N". I find it much more interesting to present the sequence, so I have modified the Rosetta Code example to display the sequence from 1 to 40 (an arbitrary value). Here's what I came up with:

 

 

Another Sinclair ZX81 example from Rosetta Code is very interesting:

 10 INPUT N
 20 PRINT INT (0.5+(((SQR 5+1)/2)**N)/SQR 5)

This one also displays only the nth number, so here it is reworked to display the sequence up to the 40th iteration:

 

 

The output of this example is identical to the Recursive solution. I have to say, playing around with this stuff using the EightyOne emulator is such a joy. The BASIC language commands are all laid out for me on the keyboard with a single button-press for each keyword; which means no typos. The syntax is checked as each line is entered and a new line of code isn't added to the listing until it is syntactically correct. Each line of a listing can be selected for editing, including the line numbers, which is extra helpful for moving things around and repeating code lines that differ only by one or just a few characters.

 

 

[carlsson]

You can recurse up to 40 levels on an (expanded) ZX-81? That's cool, compared to only 23 levels on e.g. the VIC-20, due to the stack space is used up. I suppose it is true also for newer computers that eventually you'll run out of stack space or other form of nesting when you recurse like that, which is why algoritms preferrably are rewritten to avoid recursion.

[ClausB]

Sinclair did an impressive job with the ZX 8K BASIC. That went a long way toward compensating for the limited hardware. That keyword entry feature and the various cursor modes made the membrane keyboard tolerable.

[almightytodd]

I'm inspired to do some testing to see just how deep the recursion can potentially go...  Updates to follow.

[JamesD]

Even though BASIC doesn't have local variables, you can simulate them in arrays.  <hint, hint>

 

[phoenixdownita]

Any recursive program admits an iterative version in which you hold the state needed, which for true recursion can grow at each call, that is to say you can build your own stack and introduce whatever other limits you see fit if the machine/language stack is too limiting ... it may run slower but ...

 

If the problem lend itself to tail recursion then it's not even recursion anymore and the iterative solution uses constant space ... like the Fibonacci series you are using, it should be possible to replace the recursive gosub with goto (not sure about the BASIC you are using but try to replace the gosub in line 1080 with a simple goto, no recursion)  no recursion really needed as the problem only necessitates to keep state for the "last 2" to generate the next .... all of it being moot nowadays due to Fibonacci sequence admitting a closed form (as you reported already) but there are other fixed state problems that can be solved the same way (aka replace recursion with iteration and a fixed amount of state).

[almightytodd]

On 5/31/2020 at 1:04 AM, phoenixdownita said:

Any recursive program admits an iterative version in which you hold the state needed, which for true recursion can grow at each call, that is to say you can build your own stack and introduce whatever other limits you see fit if the machine/language stack is too limiting ... it may run slower but ...

 

If the problem lend itself to tail recursion then it's not even recursion anymore and the iterative solution uses constant space ... like the Fibonacci series you are using, it should be possible to replace the recursive gosub with goto (not sure about the BASIC you are using but try to replace the gosub in line 1080 with a simple goto, no recursion)  no recursion really needed as the problem only necessitates to keep state for the "last 2" to generate the next .... all of it being moot nowadays due to Fibonacci sequence admitting a closed form (as you reported already) but there are other fixed state problems that can be solved the same way (aka replace recursion with iteration and a fixed amount of state).

 

Thank you so much for that! I am constantly in awe of the brilliance that I find in the forums here. I re-configured my EightyOne emulator to a stock ZX81 with one Kb of RAM. The BASIC and operating system are stored in an 8Kb ROM. It seems to me that the Model 1 TRS-80 had a 4Kb ROM? Can anyone confirm?

 

Anyway, here's a simple program to PEEK at the RAM addresses of the system variables, which start at the end of ROM. I modified my code from the example on page 136 of the Timex Sinclair 1000 manual. Using a "GOTO" the program runs happily for at least 4,000 iterations.

 

Switching to a GOSUB in line 1040, the situation changes dramatically...

The program stops with error code 4 (out of memory).

I then execute a "PRINT N" command which returns 270, suggesting that the GOSUB stack has consumed all of the memory in 270 iterations (...unless the value of "N" has been corrupted). I looked up the ASM source code for the ZX81 ROM here:  https://www.tablix.org/~avian/spectrum/rom/zx81.htm#L0EB5

 

If I'm reading this right, the GOSUB routine uses the "error stack pointer - ERR_SP" to store the return address for each GOSUB call at Hex address 4002:

;; GOSUB
L0EB5:  LD      HL,($4007)      ; sv PPC_lo
        INC     HL              ;
        EX      (SP),HL         ;
        PUSH    HL              ;
        LD      ($4002),SP      ; set the error stack pointer - ERR_SP
        CALL    L0E81           ; routine GOTO
        LD      BC,$0006        ; 

I experimented with PEEKing memory location 16,386 during each iteration, which I believe corresponds with Hex value 4002. Please point out any glaring errors in my thinking. THIS IS WHY I'M POSTING HERE! During my various experiments, I found that the starting address of this stack pointer varied with the length of my program, and then decremented two-bytes with each iteration. I found one case where it wrapped around zero (...this was before I had reduced my RAM from 16k to 1k in the emulator) and it started over at 255.

 

Another interesting phenomenon I observed, is that once I had blown out memory space during a test run, the program wouldn't list fully anymore, and if I tried running it repeatedly, it would run out of memory in fewer iterations each time (...13, and then 3). The only remedy for this condition was a reboot, and then I'd have to type my program back in again. I could also save state in the emulator, and then reload it with an additional constraint that a snapshot will only load to an emulation model with the same memory model.

 

From my computer science days in college, I believe heap-space grows upwards while stack-space grows down? This stuff is all very interesting to me. I'm tempted to try some additional experimenting with the Altirra emulator or the BeebEm for the BBC Micro, since those computers used the 6502 CPU instead of the Z80 in the Sinclair.

[almightytodd]

On 5/29/2020 at 7:32 AM, carlsson said:

You can recurse up to 40 levels on an (expanded) ZX-81? That's cool, compared to only 23 levels on e.g. the VIC-20, due to the stack space is used up. I suppose it is true also for newer computers that eventually you'll run out of stack space or other form of nesting when you recurse like that, which is why algorithms preferably are rewritten to avoid recursion.

I am amused... ...just for fun I modified my Fibonacci sequence program above to also print the PEEK of the ERR_SP as discussed above with each iteration. I then ran it on the "stock" ZX81 with 1Kb of RAM... and it ran out of memory just before printing the stack-pointer value on the 40th ITERATION!! What are the odds?

 

 

(Error code 4 at line 1060)

[almightytodd]

On 5/30/2020 at 5:58 PM, JamesD said:

Even though BASIC doesn't have local variables, you can simulate them in arrays.  <hint, hint>

 

Fascinating! Do you have some sample code you could post to demonstrate this technique?

[Mr SQL]

1 hour ago, almightytodd said:

Another interesting phenomenon I observed, is that once I had blown out memory space during a test run, the program wouldn't list fully anymore

I think the NEW keyword should enable you to list the program again, the ZX81 displays less and less lines of code on the screen when it starts to run out of RAM.

 

On 5/30/2020 at 5:58 PM, JamesD said:

Even though BASIC doesn't have local variables, you can simulate them in arrays.  <hint, hint>

 

Array variables are still global though; do you define them locally and then just make sure never to call them out of scope?

 

[JamesD]

You increment the index before the subroutine calls itself, and decrement before return

 

[almightytodd]

Interesting...

 

[JamesD]

Do you want an example?

 

[almightytodd]

Yes, that would be great...

 

[ClausB]

Anotated ROM listing:

https://archive.org/details/complete-timex-ts1000-sinclair-zx81-rom-disassembly

All the clever tricks and RAM management explained.

[JamesD]

I'm trying to come up with something useful that requires local variables, but it will probably be just a useless example.