Recursion in BASIC

[basicchip]

ARMbasic was written for embedded processors with potentially very limited memory. So to keep the stack small and not have to add stack overflow checks, we decided to pre-allocate variables for subroutines and functions.

Now recursion is useful in certain situations, and one of those is writing compilers. However ARMbasic is written to do efficient and easy control in an embedded environment, and while it does have string functions, the intention was never to write a compiler in BASIC.

But the question of doing simple recursion comes up from time to time. Recursion is allowed in BASIC now, but you have to manage your own private stack. Could this be done automatically in a future BASIC (quite possibly, remember sub/functions were additions and floating point was recently added). But recursion is really the exception in embedded programming, not the rule, so it may take the form of a keyword that allows for recursive functions.

A classic example of a recursive routine is calculating a factorial (yes there are non-recursive solutions too)

Code: Select all

DIM privateStack(32)

privateStackPointer=0
factorialValue=0

Factorial:		'  called with privateStack(privateStackPointer)
	if privateStack(privateStackPointer)=1 then
		FactorialValue = 1
		return
	endif
	
	privateStackPointer += 1
	privateStack(privateStackPointer) = privateStack(privateStackPointer-1)-1
	gosub Factorial
	privateStackPointer -= 1
	FactorialValue *= privateStack(privateStackPointer)
	return

main:

for i = 1 to 10		
	privateStackPointer=0
	
	privateStack(privateStackPointer)=i
	gosub Factorial
	
	print i, FactorialValue
next i

And the result is

Code: Select all

ARMbasic[9.27h] on the PC  Copyright 2013, Coridium Corp.
*+
... ( 0.22K code + 0.00K const)/96K   0.15/9K data programmed

Executing...

1	1
2	2
3	6
4	24
5	120
6	720
7	5040
8	40320
9	362880
10	3628800
 

... Finished in 0 ms

[cfbsoftware]

I agree - while recursion is only appropriate on rare occasions, when it is useful it is very useful. My favourite practical example is the famous Quicksort algorithm. An example of this used to sort an array of integers In the Oberon language is:

Code: Select all

PROCEDURE SortIntegers(VAR a: ARRAY OF INTEGER; left, right: INTEGER); 
  VAR i, j, temp, x: INTEGER; 
BEGIN 
  i := left; 
  j := right; 
  x := a[(left+right) DIV 2]; 
  REPEAT 
    WHILE a[i] < x DO INC(i) END;
    WHILE x < a[j] DO DEC(j) END;
    IF i <= j THEN 
      temp := a[i]; a[i] := a[j]; a[j] := temp; INC(i); DEC(j)
    END 
  UNTIL i > j; 
  IF left < j THEN SortIntegers(a, left, j) END; 
  IF i < right THEN SortIntegers(a, i, right) END 
END SortIntegers; 

Anybody who is interested in the analysis of this algorithm, a comparison of its performance with other sorting algorithms and more examples of recursion should read Chapters 2 and 3 of the book Algorithms and Data Structures by Niklaus Wirth.

There is also an interesting visualisation of its behavior on Wikipedia.

[AMDlloydsp]

Ooo!
Is the private stack pointer facility new, or just the permissibility of recursion?

Both have SO many possibilities!

Lloyd

[basicchip]

Actually nothing new, that Factorial example has always worked. Private in this case is just a name. I also wrote one for the towers of hanoi in the past, I'll see if I can find it.

GOSUB and GOTO have always been able to call forward, so there was no limit there on recursion, but GOSUB never has allocated local variables, so you had to do it by hand

FUNCTION and SUB now do not allow forward calls or calls to themselves, so recursion is not allowed as a result of that limit.

Now I guess you could do a GOSUB inside a FUNCTION, but the local variables would not be saved so your code would break trying that.

What I envision is a modifier (called an attribute in c). Right now there is a modifier for INTERRUPT SUB, and there might be one for RECURSION. This is actually going to be a byproduct of the BASIC for an IO processor in one of the ARMs we have seen, that will use its local registers for local variables.

One of the advantages of our method of pre-allocated memory, beyond nearly guaranteeing no stack overflows, is that during debug, you can see all the local variables in all the FUNCTIONs and SUBs at any point where your program hits a break via STOP, or at the END.

[basicchip]

Speaking of QuickSort, this was precisely the routine one of our consulting clients was interested in doing.

And since they provided me with some working code and a test case to compare against, I built a version of the BASIC firmware with QUICKSORT(*data, num_elements). And it turns out that it runs about 20x the shellsort version in BASIC for 512 elements.

So that will be built into the custom firmware we are doing on the LPC4078 for that project. And we will roll it into some future product.

[olzeke51]

I have a menu loop, and can't decide whether to use SELECT CASE or a bunch of IF/THEN/ENDIFs.
would doing a GOTO from inside the SELECT CASE (or IF/THEN/ENDIFs) to a program area outside of the CASE/IF loop
cause any issues?
'
It seems strange to use a GOSUB for just a one-use routine -like setting the time.
I thought GOSUBs were an early version of "code reuse" and memory savings.
GOTO -you also can modify variables without having to pass them to a SUB
'
if the program runs for a long time, going into and out of the menu loop alot -- would this cause stack issues??
{in my mind the ENDSELECT & ENDIF would not get processed and might cause some hanging [?participles ] on the stack}
Thanks - Gary/Olzeke51

[basicchip]

GOSUBs are matched by RETURNs so it is not an issue

SELECT/CASE emits basically the same code as IF/ELSEIF... so there is no advantage to either though most people think SELECT/CASE is more readable.

While GOTO in a SELECT/CASE would be a bit of bad form, I believe the compiler does the right thing and there is no memory leak.

[basicchip]

Just to update this too, QUICKSORT has been added and is part of the Teensy and mbed firmware. Not enough room to add it to the BASICchip.

And we have not updated the SuperPRO firmware in more than 2 years, and don't intend to as one of more of the changes might affect the code base of the users out there. If it ain't broke don't fix it...