Recursive programming (in WimBasic)

[wimoos]

Hi all,

Just for the fun of it: programming recursive functions in CBM Basic cannot be done - it leads to an ?OUT OF MEMORY error.

BUT

In WimBasic it can be done. For example, calculating a factorial:

Code: Select all

10 A$(0)="1" 
20 A$(1)="I*FNF(I-1)"
30 DEF FNF(I)=EVAL A$(SGN(I))
40 PRINT FNF(3) 

Now, practically, this only works for FNF(0), FNF(1), FNF(2) and FNF(3). Apparently, the stack overhead is humungous. But it works!

Regards,

Wim.

[Mike]

The main two advantages of DEF FN's are: they accept one parameter which duly gets used as local variable and second, they can directly be used in (numeric) expressions without the necessity to assign the result to a temporary variable.

Other than that, formulations of recursive procedures and "functions" (the latter with pre-defined variables as input and output parameters) work perfectly well in original BASIC V2, with sub-routines called by GOSUB. With a crafted stack from a dedicated array plus stack pointer, variable values can be stored away, that variable can thus be re-instantiated as local, and this isn't even limited to just one local variable for each call.

[wimoos]

Rewriting line 20 as

Code: Select all

20 A$(1)="FNF(I-1)*I"

uses less stack and makes FNF(4) and FNF(5) work as well.

'Crafting' a stack and handling variables 'local' in vanilla CBM Basic can make you go 23 levels deep.

Regards,

Wim.

[chysn]

It would be an interesting property of BASIC to implement a non-6502 stack space. You could define some part of top-of-memory as the stack, which would be used by FOR/NEXT or GOSUB/RETURN.

Of course, you never need recursive subroutines, so maybe it's one of those interesting ideas with no good reason to do it.

[wimoos]

Of course, you never need recursive subroutines, so maybe it's one of those interesting ideas with no good reason to do it.

Well, as a famous Dutch philosopher once said: "never say never". Here's the (recursive) code for solving "Tower of Hanoi":

Code: Select all

10 n=5:dimlf$(n),la$(n),lt$(n):f$="a":t$="b":a$="c":gosub20:end
20 ifn=0thenreturn
30 lf$(n)=f$:la$(n)=a$:lt$(n)=t$:n=n-1:h$=a$:a$=t$:t$=h$:gosub20
40 print"move"n"from "f$" to "t$:h$=f$:f$=a$:a$=t$:t$=h$:gosub20
50 n=n+1:f$=lf$(n):a$=la$(n):t$=lt$(n):return

It bails out on n>22.

Regards,

Wim

[thegg]

Although chysn correctly says that 'you never need recursion', I find that recursion does have a certain elegance and often provides a smaller code footprint. It can also be implemented in 6502 Assembler.

Recursion on a 6502 CPU is constrained by a small system stack. As Mike outlines above, this constraint can be overcome by using other memory as a private stack for the recursive procedure working data. The system stack is then just used for holding the return address for calls to the recursive procedure.

The attached archive contains an assembly program (hanoi.prg) for the unexpanded VIC-20 that implements a solution to the Towers of Hanoi puzzle using recursion similar to the BASIC solution above.

The source code included is for the CBM prg Studio IDE. It uses macros to implement push and pull functions for the recursive procedure variable data. The private stack is placed in store at the end of the program. The recursive procedure itself is small, most of the program space is taken up by the output processing.

The program is preset to a tower of 3 discs. The number can be changed by POKE 4163,number_of_discs before the program is run.

Actually, for sensible numbers of discs, the system stack is perfectly adequate. A second program (hanoi2.prg) is provided that places the recursive procedure working data on the system stack.

The attachment ZIP contains the executable PRGs and source code.