 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 : MMBasic 4.6b Recursion
| Author | Message | ||||
| kwass Newbie  Joined: 20/04/2015 Location: United StatesPosts: 3 |
I'm a noob here so please excuse me if I'm missing something obvious. I just started with playing around on a Micromite and came across what looks to be a bug in recursion. According to the manual, recursive functions should allow for a stack depth of 50, but I'm getting a stack overflow after 5 calls in this code: Print fac(1) Print fac(5) Print fac(6) Print fac(7) Function fac(n) If n <= 1 Then fac = 1 Else fac = n*fac(n-1) EndIf End Function Am I doing something wrong? Thanks, Katie |
||||
TassyJim Guru  Joined: 07/08/2011 Location: AustraliaPosts: 6283 |
Welcome to the forum. The program runs OK under DOS MMBasic but fails under micromite V4.6B I don't think you are doing anything wrong. Jim VK7JH MMedit |
||||
| kwass Newbie Joined: 20/04/2015 Location: United StatesPosts: 3 |
Thank you for the welcome and the confirmation of the problem report. Is there a better place to officially report bugs to Geoff? -Katie |
||||
| paceman Guru Joined: 07/10/2011 Location: AustraliaPosts: 1329 |
Hi Katie, Welcome to the forum from me too. Geoff usually manages to keep a pretty good eye on all the TBS forum posts but just to make sure you can PM him from the forum. See "Private Messenger" link at the top of the posts - his member name is 'Geoffg' and he'll receive an e-mail via the forum if you message him. Greg |
||||
G8JCF Guru Joined: 15/05/2014 Location: United KingdomPosts: 676 |
@kwass I rewrote your test a little so that I could test it on different platforms FOR P=1 TO 100 STEP 2 Q=0 PRINT P;" ",fac(P)," ";Q NEXT P FUNCTION fac(n) Q=Q+1 IF n < 2 THEN fac = 1 EXIT FUNCTION ENDIF FAC = n * fac(n-1) END FUNCTION and on a 4.6B micromite, it breaks at P%=7 > RUN 1 1 1 3 6 3 5 120 5 7 [13] If n% < 2 Then Error: Stack overflow. Expression is too complex > Now, I also happen to have the STM32 beta of MMBasic aka ARMMite, and it breaks at P%=51 which is to be expected > RUN 1 1 1 3 6 3 5 120 5 7 5040 7 9 362880 9 11 3.99168e+07 11 13 6.22702e+09 13 15 1.30767e+12 15 17 3.55687e+14 17 19 1.21645e+17 19 21 5.10909e+19 21 23 2.58520e+22 23 25 1.55112e+25 25 27 1.08889e+28 27 29 8.84176e+30 29 31 8.22284e+33 31 33 8.68332e+36 33 35 0.00000e+2147483647 35 37 0.00000e+2147483647 37 39 0.00000e+2147483647 39 41 0.00000e+2147483647 41 43 0.00000e+2147483647 43 45 0.00000e+2147483647 45 47 0.00000e+2147483647 47 49 0.00000e+2147483647 49 51 [7] Function fac(n) Error: Too many SUB and FUN > And when run under MMBasic for DOS 1 1 1 3 6 3 5 120 5 7 5040 7 9 362880 9 11 3.99168e+07 11 13 6.22702e+09 13 15 1.30767e+12 15 17 3.55687e+14 17 19 1.21645e+17 19 21 5.10909e+19 21 23 2.5852e+22 23 25 1.55112e+25 25 27 1.08889e+28 27 29 8.84176e+30 29 31 8.22284e+33 31 33 8.68332e+36 33 35 inf 35 37 inf 37 39 inf 39 41 inf 41 43 inf 43 45 inf 45 47 inf 47 49 inf 49 51 inf 51 53 inf 53 55 inf 55 57 inf 57 59 inf 59 61 inf 61 63 inf 63 65 inf 65 67 inf 67 69 inf 69 71 inf 71 73 inf 73 75 inf 75 77 inf 77 79 inf 79 81 inf 81 83 inf 83 85 inf 85 87 inf 87 89 inf 89 91 inf 91 93 inf 93 95 inf 95 97 inf 97 99 inf 99 > So it would seem that the MMBasic Interpreter's stack in the MX170 is probably quite small compared to the other platforms - to be expected given the small RAM on the '170. So, to echo Jim, your code is quite correct. Peter The only Konstant is Change |
||||
twofingers Guru Joined: 02/06/2014 Location: GermanyPosts: 1593 |
I can confirm, the issue consist also with mmBasic 4.5 for MaxiMites. I just do not understand why we have not found it sooner.  causality ≠ correlation ≠ coincidence |
||||
| matherp Guru Joined: 11/12/2012 Location: United KingdomPosts: 10315 |
The problem also arises on the MX470. The stack size is set to 6K on both the MX170 and MX470. Changing it to 8K on the 470 I only get 2 extra levels. So it looks like there is too much stack being used. I'll PM Geoff and ask him to look at this thread. |
||||
| kwass Newbie Joined: 20/04/2015 Location: United StatesPosts: 3 |
Thank you all for the welcomes and further investigations of this. -Katie |
||||
| matherp Guru Joined: 11/12/2012 Location: United KingdomPosts: 10315 |
For info: Each level of recursion takes an extra 696 bytes off the stack |
||||
Grogster Admin Group  Joined: 31/12/2012 Location: New ZealandPosts: 9610 |
Wow, yeah, exactly! 
You beta test into the ground, and there are still bugs breeding deep in the code there somewhere! 
VERY nice find, Katie.  
Although, to be fair to EVERYONE, this example is a very complicated mathematical test, and unless specifically written such that you are calling said function from within that same function, you would never see this error. That's what makes it a particularly interesting find.  Smoke makes things work. When the smoke gets out, it stops! |
||||
| rave Newbie Joined: 24/02/2018 Location: United StatesPosts: 28 |
Sorry folks, I'm resurrecting this old thread, since folks like me that use the CMM and MM will definitely run into this problem again, because we're still using MMBasic 4.5b or 4.4. With a bit of experimentation I found out that there is an easy way to work around this problem using subs, which aren't causing stack overflows that quickly. Just rewrite your function as a sub and add a parameter for the return value. The idea is to pass the result back out of the sub using parameter passing by reference. For example: Sub fac(n, res) If n < 2 Then res = 1 Else fac n-1, res ' recursive call res = n*res EndIf End Sub > fac 20, res: Print res 2.4329e+18 If you really want to use a function in the rest of your code, then add a function of the same name ( yes you can!) that calls the sub, like this:Function fac(n) Local res fac n, res ' call sub fac = res ' assign the return value End Function I also tried calling the sub with the fac parameter directly, like this: Function fac(n) fac n, fac End Function Which would have been really nice and compact, yet somewhat mysterious with the absence of logic  . MMBasic does not complain. However, MMBasic does not apparently update the function return variable fac when passed as a reference parameter to the fac sub, although function return variables in most other cases can be set and then used just fine as I found out (e.g. assuming fac is a function, then in this function you can do things like fac = res: if fac > 1000 then fac = 1000).I ran into this issue when converting Rob Pike's regular expression matching algorithm to MMBasic, which uses two mutually-recusive functions and I could't get even a simple regex match to work . But all is good now. Life is good .- Rob |
||||
 Print this page |
 |
The Back Shed's forum code is written, and hosted, in Australia. | © JAQ Software 2025 |
