 Notice. New forum software under development. It's going to miss a few functions and look a bit ugly for a while, but I'm working on it full time now as the old forum was too unstable. Couple days, all good. If you notice any issues, please contact me. |
Forum Index : Microcontroller and PC projects : Recursion in MMBasic
Page 1 of 2   |
|||||
| Author | Message | ||||
| ceptimus Senior Member  Joined: 05/07/2019 Location: United KingdomPosts: 130 |
I've been experimenting with recursion in MMBasic. For simple examples, like the classic factorial, it works fine. function factorial(n%) if n% = 0 then factorial = 1 else factorial = n% * factorial(n% - 1) end if end function print factorial(100) But I've found that it doesn't seem to co-exist happily with any loops (do loop, or for next) that use exit (exit do, exit for). The error reports are rather strange - you get errors such as "LOOP without a matching DO" when returning from two or three levels deep of recursion, even though that same code executes fine at the deeper recursion levels. I've tried it on various versions of MMBasic including the DOS one, and the same errors seem to occur on all the ones I've tried. My code had no places where I just jumped out of a loop - every loop that required early exiting had a proper exit route. Also I was careful that when I wanted to pass a 'value' to a recursive sub or function, that sub or function created a local copy of the variable so as not to inadvertently modify the value (MMBasic has call by reference parameters). I changed any loops that needed exits or called other subs/functions to work instead with labels and If ... Then GoTo label - and then it runs perfectly albeit rather slowly. I don't know what mechanism MMBasic uses to 'find' a label - does it build a table of addresses for them, or does it search through the entire program from the start each time it needs to target one? If it's the latter, that would explain the slowness. |
||||
| JohnS Guru  Joined: 18/11/2011 Location: United KingdomPosts: 4044 |
May be best to post a short example or two that ought to work but doesn't, so Geoff can reproduce it easily. John |
||||
| ceptimus Senior Member Joined: 05/07/2019 Location: United KingdomPosts: 130 |
Thanks John. Excellent idea. Here's a short one. It calculates OEIS A000522 using a short recursive function. I've written two equivalent functions named "foo" and "bar" that should both return the same result. You'll see that the labels plus gotos (foo) version works fine, but the equivalent For Next version (bar) crashes when attempting to calculate bar(2). The error reported is "Error: Cannot find a matching FOR" The code: Option explicit Function foo(a) 'version with labels and gotos Local i foo = 1 i = 1 If i > a Then GoTo label_B 'skip loop body when a is zero label_A: ' for i = 1 to a foo = foo + foo(a-1) i = i + 1 : If i <= a Then GoTo label_A ' next label_B: End Function Function bar(a) 'version with For Next loop Local i bar = 1 For i = 1 To a bar = bar + bar(a-1) Next End Function Dim n Print "Demo MMBasic recursion bug. Calculate OEIS A000522" Print "Using foo() method - labels and gotos" For n = 0 To 8 Print n, foo(n) Next Print : Print "Using bar() method - For Next" For n = 0 To 8 Print n, bar(n) Next The output: Demo MMBasic recursion bug. Calculate OEIS A000522 Using foo() method - labels and gotos 0 1 1 2 2 5 3 16 4 65 5 326 6 1957 7 13700 8 109601 Using bar() method - For Next 0 1 1 2 2 [19] Next Error: Cannot find a matching FOR > Obviously MMBasic doesn't support calling a recursive function that contains a loop from inside that loop. I'm quite happy with that - I realize that I'm trying to do something a bit extraordinary. It's interesting that the label and goto method does work though. By the way, I've verified that MMBasic must search through the code (from the beginning) whenever it targets a label (with goto for example). If you have a lot of comments near the start of the program (before the label) the program runs much slower than when you move those same comments to a position in the program after the label. . Edited 2019-10-25 04:49 by ceptimus |
||||
| Pluto Guru Joined: 09/06/2017 Location: FinlandPosts: 375 |
Should there be a "NEXT i" just before the "Label_B" statement? |
||||
| ceptimus Senior Member Joined: 05/07/2019 Location: United KingdomPosts: 130 |
No Pluto - the whole point is that in the foo() function there aren't any For or Next statements (except in the comments). Remember that anything after a ' is a comment. I probably shouldn't have put those (' for ... ) and (' next ) comments in foo() - they are confusing rather than helpful, but it's too late for me to edit the code now. When you eliminate the "For Next" statements and replace them with a bunch of equivalent "i=i+1 - If - Then - GoTo" statements then a program with recursion will work. Of course, the "For Next" version is much easier to understand but unfortunately it crashes. I should probably have put the bar() function first - study bar() first and once you understand it, verify that foo() does exactly the same, but in a less clear way. To make it clearer, this is all you really need to see the bug - the rest of the program was just to demonstrate a way to work around the bug. Option explicit Function bar(a) Local i, r r = 1 ' the return value of this function For i = 1 To a r = r + bar(a-1) Next bar = r End Function print bar(3) . Edited 2019-10-25 05:25 by ceptimus |
||||
| JohnS Guru Joined: 18/11/2011 Location: United KingdomPosts: 4044 |
For what it's worth (not much!), I don't think you're trying to do anything extraordinary. I think it should just work and I suspect MMBasic will be fixed :) I just tried a version (had to add line numbers) with the old Linux (statically-linked) MMBasic (v 4.4.07e) and oddly get weird values but doesn't throw an error. Oh... wait... The version using r does the above. (E.g. print bar(3) prints 11.) The version using bar = bar + bar(a-1) throws an error. Oh... John |
||||
TassyJim Guru Joined: 07/08/2011 Location: AustraliaPosts: 6283 |
TRy putting the 'target' in the NEXT statement Works OK in MMBasic DOS and armite F4 Jim VK7JH MMedit |
||||
| JohnS Guru Joined: 18/11/2011 Location: United KingdomPosts: 4044 |
Goodness! Works on Linux with that. John |
||||
| matherp Guru Joined: 11/12/2012 Location: United KingdomPosts: 10310 |
Timings on H7 using Jim's correction 11.2Sec vs 8.5sec Edited 2019-10-25 07:45 by matherp |
||||
| ceptimus Senior Member Joined: 05/07/2019 Location: United KingdomPosts: 130 |
Awesome! Thanks to all who've posted.  I will start adding the loop variable to all my Next statements - it's a good way of self-documenting the code anyway. Ironically, I was playing around with strangely nested For Next loops a while back to see what happened: For I = 1 to 10 For J = 1 to 10 Print I, J Next I Next J I concluded that there could never be any possible use for that sort of code, even if it worked, and that was why most BASICs are happy for the loop variable to be omitted from Next statements.  |
||||
thwill Guru Joined: 16/09/2019 Location: United KingdomPosts: 4311 |
I encountered exactly the same problem last week on my CMM and found the solution of using the loop variable explicitly in the Next statement. Unfortunately I couldn't work out a solution for Do While Loops which demonstrate the same issue if used in recursive functions. MMBasic for Linux, Game*Mite, CMM2 Welcome Tape, Creaky old text adventures |
||||
| ceptimus Senior Member Joined: 05/07/2019 Location: United KingdomPosts: 130 |
thwill, here is bar() rewritten to use an equivalent Do While Loop, and as you say it crashes MMBasic: Option explicit Function bar(a) Local i,r=1 i=1:Do While i<=a r=r+bar(a-1) i=i+1:Loop bar=r End Function Dim n:For n=0 To 8:Print n,bar(n):Next n Until the bug in MMBasic is fixed, it's possible to use the weird construct described below that makes "For Next" behave like "Do While Loop". We introduce a dummy loop variable - I've used z - and put whatever the While control logic was - in the example above it was "i<=a" - inside the parentheses after the Not So "Do While i<=a" is replaced by "For z=0 To 0 Step 0:If Not(i<=a)Then Exit For" ... and "Loop" is replaced by "Next z" here is the kludged version that runs without error: Option explicit Function bar(a) Local i,z,r=1 i=1:For z=0 To 0 Step 0:If Not(i<=a)Then Exit For r=r+bar(a-1) i=i+1:Next z bar=r End Function Dim n:For n=0 To 8:Print n,bar(n):Next n Edited 2019-10-25 22:18 by ceptimus |
||||
| ceptimus Senior Member Joined: 05/07/2019 Location: United KingdomPosts: 130 |
Unless you have a special interest in MMBasic recursion, you can probably ignore the following - it's getting dangerously close to becoming an entry for an obfuscated BASIC contest. I wanted to test Sub() which can "return" values using the fact that the arguments are passed by reference. Function() does the same and it's a source of subtle bugs if a Sub() or Function() in MMBasic accidentally modifies the argument variable(s). I also wanted to verify that Exit Sub doesn't cause a problem with recursion. Anyway, the following code does execute without error and generates the correct answers. Option explicit Sub bar(a) 'a is passed by reference. This Sub modifies a to "return" a result Local i,t,z,r=1 If a=0 Then a=1:Exit Sub i=1:For z=0 To 0 Step 0:If i>a Then Exit For t=a-1:bar(t):r=r+t i=i+1:Next z a=r End Sub Dim n,r:For n=0 To 8:r=n:bar(r):Print n,r:Next n |
||||
| thwill Guru Joined: 16/09/2019 Location: United KingdomPosts: 4311 |
Thanks Ceptimus. I originally used a "goto label" instead of a loop to workaround it. Is the Next kludge more efficient? Also your example isn't MMBasic 4.5 is it? "Option explicit" and using "Dim" to declare variables aren't in my copy of the manual. Edited 2019-10-26 06:22 by thwill MMBasic for Linux, Game*Mite, CMM2 Welcome Tape, Creaky old text adventures |
||||
| ceptimus Senior Member Joined: 05/07/2019 Location: United KingdomPosts: 130 |
On all the platforms I've tried, GoTo label is much slower than the other loop constructs. I think Geoff said that the (Colour) Maximite builds a table of addresses of labels, but the other implementations search through the program from the beginning to find a label whenever one is targeted - so a GoTo label executes very slowly for any labels that are towards the end of a large program. The other loop constructs, even when they are misused a little to get around the bug, are also neater and arguably better programming practice than using GoTo. I'm using MMBasic Ver 5.05.02 in DOS, and the latest versions on the Armmites and Pi-cromite for testing. I've not been using my Colour Maximite nor any of the PIC based Micromites for these tests. Option Explicit is a great safety net for catching bugs if your version of MMBasic supports it. I'm not sure if there is a better way of declaring scalar variables in DOS MMBasic than with DIM - and if you use Option Explicit you have to declare global variables somehow. Perhaps someone more knowledgeable than me will provide an answer to that. . Edited 2019-10-26 06:32 by ceptimus |
||||
Grogster Admin Group  Joined: 31/12/2012 Location: New ZealandPosts: 9610 |
TEGAN: "Of course, if we had an index file, we could look it up in the index file under index file! What am I saying. I'm talking nonsense." NYSSA: "Recursion isn't nonsense." TEGAN: "Eh?" NYSSA: "That's an example of recursion - when procedures fall back on themselves. IF you had an index file, you could look it up in the index file." TEGAN: "'IF'. My dad used to say that 'If' was the most powerful word in the English language..." NYSSA: "Recursion's a powerful mathematical concept. But I don't see how it can help us now." TEGAN: "If.... I.F.!!! Stands for Index File!" - Doctor Who, Castrovalva. Smoke makes things work. When the smoke gets out, it stops! |
||||
| thwill Guru Joined: 16/09/2019 Location: United KingdomPosts: 4311 |
Grogster: Wrong platform; the TARDIS clearly ran BBC BASIC 2 - see The Five Doctors. Ceptimus: thanks for the reply. As it happens my current project won't work on DOS MMBasic because it uses PEEK and POKE to access a byte array that acts as the Z-machine's memory; though thinking about it, DOS MMBasic presumably has a lot more memory to play with than a CMM and I could use an array of integers even if I never store > 255 in them. I'll be taking an in depth look at which are the fastest constructs and how file ordering matters when I optimise the code. Does anyone have any insight? Tom MMBasic for Linux, Game*Mite, CMM2 Welcome Tape, Creaky old text adventures |
||||
| TassyJim Guru Joined: 07/08/2011 Location: AustraliaPosts: 6283 |
thwill, Depending on the size of memory required, I would create an array of strings. Each element uses one byte for the length then 255 bytes for the string. A string array s$() would reserve 8 X 256 or 2K bytes which you could then peek and poke at will. You can get the starting address for any variable. An integer array uses 4 bytes per element but you could use code to divide each number into 4. That would save using peek and poke. CMM V4.5 doesn't have integers available to play with. The DOS version is restricted in memory Jim VK7JH MMedit |
||||
| ceptimus Senior Member Joined: 05/07/2019 Location: United KingdomPosts: 130 |
For testing programs on the DOS version, I wrote these Peek and Poke equivalents in MMBasic. You can only use an offset of 0,1,2, or 3 of course. Peek works on simple variables and arrays, but Poke only on simple variables, so if your program pokes to an array variable you have to alter it to copy that to a simple variable, poke to that and then copy back again. Only other change needed is to put a comma after all the VAR keywords - that can be done with a quick search and replace. The DOS version just treats VAR as an extra variable passed to peek / poke - a variable that it doesn't need, so it names that variable 'dummy'. You also need to DIM VAR if you're using Option Explicit, as DOS MMBasic will otherwise complain that VAR is not defined. If your program is intended for just the DOS version, then you're better off just using arrays or strings as Jim suggested, but for testing programs on the DOS version that you eventually intend to run on some other 'mite, these peek and poke hacks are useful. Dim VAR Function Peek(dummy,v%,o%) Local div(3)=(&h1,&h100,&h10000,&h1000000) peek=(v%\div(o%))And &hFF End Function Sub Poke dummy,v%,o%,p% Local mul(3)=(&h1,&h100,&h10000,&h1000000) Local mask(3)=(&hFFFFFF00,&hFFFF00FF,&hFF00FFFF,&hFFFFFF) v%=(v% And mask(o%))Or(p%*mul(o%)) End Sub . Edited 2019-10-28 19:07 by ceptimus |
||||
| ceptimus Senior Member Joined: 05/07/2019 Location: United KingdomPosts: 130 |
On the DOS version of MMBasic, you're allowed 50 nested for loops, but some other platforms only allow 10. So recursion using the for loop trick can result in a "too many nested for loops" error. It's always possible to simulate recursion by using arrays and a variable "depth" to index into those arrays keeping track of the current 'recursion depth' Here's a non-recursive bar() that does that. Of course, bar() lends itself to this approach so this version runs in a blink. It starts to run into numerical errors at bar(13) on 32-bit 'mites and even the 64-bit integer variables of DOS MMBasic top out at bar(20). The same depth-indexed array approach can be used to eliminate explicit recursion from any program - but it may make your head hurt a little while you're figuring out how to do it.  Option explicit: Option default integer Const MD=25 'max depth Const FALSE=0 Const TRUE=1 Function bar(a) Local depth=0,_a(MD),r(MD),i,j,unwind=FALSE _a(0)=a Do While Not(unwind) r(depth)=1 If _a(depth)=0 Then unwind=TRUE Else _a(depth+1)=_a(depth)-1 depth=depth+1 EndIf Loop For i=depth-1 To 0 Step -1 For j=i+1 To depth r(i)=r(i)+r(i+1) Next j Next i bar=r(0) End Function Dim i:For i=0 To 20:Print Str$(i,2);Str$(bar(i),21,0):Next . Edited 2019-10-28 21:10 by ceptimus |
||||
| Page 1 of 2 |
|||||
 Print this page |
 |
The Back Shed's forum code is written, and hosted, in Australia. | © JAQ Software 2025 |
