+- QB64 Phoenix Edition (https://qb64phoenix.com/forum)
+-- Forum: QB64 Rising (https://qb64phoenix.com/forum/forumdisplay.php?fid=1)
+--- Forum: Code and Stuff (https://qb64phoenix.com/forum/forumdisplay.php?fid=3)
+---- Forum: Help Me! (https://qb64phoenix.com/forum/forumdisplay.php?fid=10)
+---- Thread: Why does my Loop end after 11 Loops? (/showthread.php?tid=1448)
RE: Why does my Loop end after 11 Loops? - Dimster - 02-11-2023
So the IF ... ELSE is mandatory in the C computer language?
"or is something just called after a counter"... The CALLing of the Recursion is naked call within the Recursive Loop
ie pseudocode
Recur
Sub Recur
Count = Count +1
if Count = 4000 then Exit Sub
Recur <-- Naked Call, ie no conditions just do it again
End Sub
RE: Why does my Loop end after 11 Loops? - Kernelpanic - 02-11-2023
I only took the example from C because it was explained well there. It can also be found in the QuickBasic 4 manual under 2.44.
I don't know whether your code example really runs recursively, I will have to try it out. To me it looks like it is rather iterative. Looks like a procedure to me too.
This is now the factorial iterative. It doesn't need a stack. In the past, in the days of Win 95, you could still see a time difference between iterative and recursive, especially when calculating the Fibonacci number. With normal calculations one can today no longer see the difference.
Code: (Select All)
'Fakultaet iterativ mit FOR-Schleife - 11. Feb. 2023
$Console:Only
Option _Explicit
Declare Function Fakultaet(n As Integer) As _Integer64
Dim As Integer n
Locate 2, 3
Print "Iterative Berechnung der Fakultaet - (n!)"
Locate 4, 3
Input "Fakultaet von (n): ", n
Locate 5, 3
Print Using "Die Fakultaet von ### ist: ###,###,###"; n, Fakultaet(n)
End 'Hauptprogramm
Function Fakultaet (n As Integer) Static
Dim As _Integer64 fakul
Dim As Integer i
fakul = 1
For i = 1 To n
fakul = fakul * i
Next
Fakultaet = fakul
End FunctionRE: Why does my Loop end after 11 Loops? - Dimster - 02-11-2023
Well you inspired me to put my Basic books and Binders of notes aside and check it out on the internet. You are correct. While I could not find Recursion using Basic there is a lot with all the other computer languages. Recursion is much more complex than I thought. I'm using it as a substitute for a Do...Loop or For...Next which I think would be classified as Direct Recursion. Shame there is not a lot on the internet about the Basic language and teaching examples of Recursion in Basic and all various ways to use it.
RE: Why does my Loop end after 11 Loops? - mnrvovrfc - 02-11-2023
Recursion is almost a necessity in LISP and in its leading descendants Common LISP and Scheme.
RE: Why does my Loop end after 11 Loops? - SMcNeill - 02-12-2023
(02-11-2023, 08:44 PM)Dimster Wrote: Well you inspired me to put my Basic books and Binders of notes aside and check it out on the internet. You are correct. While I could not find Recursion using Basic there is a lot with all the other computer languages. Recursion is much more complex than I thought. I'm using it as a substitute for a Do...Loop or For...Next which I think would be classified as Direct Recursion. Shame there is not a lot on the internet about the Basic language and teaching examples of Recursion in Basic and all various ways to use it.
The BASIC concept for recursion is very, very simple: Have a routine that simply calls itself. That's it. That's all recursion is, in a nutshell. If you have a routine which calls itself, then you have recursion.
Now, what does a routine need to successfully perform recursion? 3 basic things;
1) A starting point.
2) An end point.
3) To be limited in scope. Recursion which occurs a million times would be best served by some sort of loop structure. Each call to recursion uses a "chunk" of memory the size of your recursive sub/function (after all, it can't exit until it gets back from the recursive call), so if you repeat some process too many times, your program is going to crash when it runs out of memory available.
^But that's basically your only requirements to write a recursive routine. Let me show a few examples for you:
Code: (Select All)
RecurseSubPrint 1, 20
SUB RecurseSubPrint (start, finish)
PRINT start
start = start + 1
IF start <= finish THEN RecurseSubPrint start, finish
END SUBNow here, I'm passing my variables via parameter. There's a start point, and a finish point, and in this case it only runs 20 levels deep with recursion. All checks pass, so this is a valid recursive routine.
Code: (Select All)
FUNCTION RecurseFunPrint (finish)
STATIC count, total
count = count + 1
PRINT count
IF count < finish THEN total = total + count + RecurseFunPrint(finish)
RecurseFunPrint = total
END FUNCTIONNow here, I'm keeping the starting point STATIC (count) and passing my end point back to my recursive routine (finish), and this too is only going to be for 20 levels of recursion in my program. Now note, this WORKS, but **it's only going to work ONCE**. By making my start point STATIC here, there's absolutely no way to reset it. Count will increment by one every time it's called, and it's got no way to reset it. Why someone would want a recursive routine to behave in this manner, I have no clue, but that's what it's going to do here.
Start Point. End Point. Limited number of calls back to itself.
That's it. That's all recursion is. There's no fancy secret to it. It's not complicated. It's just a routine that calls itself a limited number of times.
Now, with that said, many recursive routines work without having to pass a start or finish point. HOW?? By whatever they're doing being constrained by the program itself in some other manner. A tile program might always start at point (0,0) and increment by 1 until it goes all the way right and down until it runs out of screen space, like this little tile demo below:
Code: (Select All)
$COLOR:0
CLS , 0
RecurseTile Red, Blue
SLEEP
CLS , 0
RecurseTile Magenta, Cyan
SLEEP
SUB RecurseTile (Kolor1 AS _UNSIGNED LONG, Kolor2 AS _UNSIGNED LONG)
x = POS(0)
y = CSRLIN
IF SCREEN(y, x, 1) \ 16 <> 0 THEN EXIT SUB
IF (x + y) MOD 2 THEN COLOR Kolor1, Kolor1 ELSE COLOR Kolor2, Kolor2
PRINT " ";
IF x < _WIDTH THEN x = x + 1: LOCATE y, x: RecurseTile Kolor1, Kolor2
IF y < _HEIGHT THEN y = y + 1: LOCATE y, 1: RecurseTile Kolor1, Kolor2
END SUBYour recursive file access works just like this -- start point is the beginning of the file. increment is by file record. finish is EOF. <-- Start. Stop. Limited recursion.
See how simple this stuff is, once you break it down to the BASICs?
RE: Why does my Loop end after 11 Loops? - Dimster - 02-12-2023
Thanks for these examples Steve, they are great. I've printed them off and placed them in my Basic Binder. The Looping I have down pat but the jury is still out on if Recursion is a worthy replacement for a Do..Loop/For..Next etc. In some of my formulas I have some pretty deep nesting of the various loops and the results, while accurate take a long time to complete. In one case I had a For...Next nested 6 deep
ie For U = 1 to 50
For V = 2 to 51
For W = 3 to 52
etc
It damn near took the whole day to complete the calculations. So I'm trying to explore Recursion as a substitute for those standard Do and For loopings. I haven't yet figured the algorythm correctly but on first blush it doesn't appear Recursion can be nested. I can stack Recursion calls but to nest Recursion calls seems I need to set the Recursion call in says a Select Case type algorythm. Not a true nesting but close.
I hope Recursion will be as accurate as the nested For loop above but faster. Plus I'm hoping I don't crash. I'm thinking that crashing a recursive routine is dependent on your computer's configuration. I may need to crash to find the limit my computer has with Recursion.
RE: Why does my Loop end after 11 Loops? - bplus - 02-12-2023
Quote:but the jury is still out on if Recursion is a worthy replacement for a Do..Loop/For..Next etc.
The jury has been back a long time ago, loops are better because recursion can burn through huge amounts of memory not easy to predict, neither is recursion faster. So for serious project like Opening file and processing it you want straightforward method.
Recursion is cool and is great learning experience for hobby coder. Recursion does have advantage of doing things like solving Sudoku Puzzles or Mine Sweeping empty cells or just drawing trees, allot easier to code than straight forward methods. The stacking tracks all the different paths your code has to go to cover a situation.
Opening and storing a file into data for processing is a single path from start to finish and the most effective way is not recursion.
RE: Why does my Loop end after 11 Loops? - Dimster - 02-12-2023
Oh that's devastating news B. I was looking at your Recursion examples and a Quick Sort routine. They are very fast. So here is my For...NEXT test code
Code: (Select All)
For TNa = 1 To 44
For TNb = 2 To 45
For TNc = 3 To 46
For TNd = 4 To 47
For TNe = 5 To 48
For TNf = 6 To 49
Print TNa; TNb; TNc; TNd; TNe; TNf
Next
Next
Next
Next
Next
NextTN stands for Target Number. This is similar to the actual algorythm I am presently using but really stripped down. If you run this code it will take the better part of the day to complete and that's not counting the time the actual algorythm branches off to do some calculations. I have been trying to duplicate this depth of nesting (at least 6 deep) with a recursive algorythm. I am having no luck nesting recursive calls (I don't think Quick Sort is nesting it's recursive calls but rather I think you would call that Stacking recursive calls). So I'm trying to stack them but still fumbling on the code. Impressed with the speed of Quick Sort, I thought it's recursive approach would be a lot faster than For..Next code I'm using. I good idea gone bad, as has been pointed out.
RE: Why does my Loop end after 11 Loops? - TerryRitchie - 02-12-2023
I've found recursion to be very useful for path-finding types of algorithms. I used a recursive flood fill in my Minesweeper clone:
Code: (Select All)
SUB REVEALCELL (x%, y%)
'**
'** Reveals the results of clicking on a game grid button (performs a recursive flood-fill)
'**
'** This is an example of a recursive subroutine, that is, a subroutine that calls itself over and over to achieve a
'** task that requires the same actions continuously. In the case of this subroutine, we need to look a grid square,
'** decide what to do with it, then move to each adjoining grid square and do the same thing, then moving onto the
'** next adjoining grid squares, deciding, move to adjoining, and so on a repeating pattern. Recursion is perfect for this!
'**
SHARED Game AS GAME ' need access to game options
SHARED Cell() AS CELL ' need access to cell grid
SHARED CellPic&() ' need access to cell pictures
SHARED CellsRemaining% ' need access to cells remaining in game
DIM Mines% ' the number of mines surrounding a given grid square
IF x% < 1 OR x% > Game.width OR y% < 1 OR y% > Game.height THEN EXIT SUB ' exit if past grid boundaries
IF Cell(x%, y%).pic <> CELLOUT AND Cell(x%, y%).pic <> CELLQOUT THEN EXIT SUB ' exit if not a button that can be revealed
IF x% < Game.width THEN ' are we at right edge of grid?
IF Cell(x% + 1, y%).mine THEN Mines% = Mines% + 1 ' no, if mine to the right add to mines
IF y% > 1 THEN IF Cell(x% + 1, y% - 1).mine THEN Mines% = Mines% + 1 ' if mine above/right add to mines if not at top of grid
IF y% < Game.height THEN IF Cell(x% + 1, y% + 1).mine THEN Mines% = Mines% + 1 ' if mine below/right add to mines if not at bottom of grid
END IF
IF x% > 1 THEN ' are we at left edge of grid?
IF Cell(x% - 1, y%).mine THEN Mines% = Mines% + 1 ' no, if mine to the left add to mines
IF y% > 1 THEN IF Cell(x% - 1, y% - 1).mine THEN Mines% = Mines% + 1 ' if mine above/left add to mines if not at top of grid
IF y% < Game.height THEN IF Cell(x% - 1, y% + 1).mine THEN Mines% = Mines% + 1 ' if mine below/left add to mines if not at bottom of grid
END IF
IF y% < Game.height THEN IF Cell(x%, y% + 1).mine THEN Mines% = Mines% + 1 ' if mine above add to mines if not at top of grid
IF y% > 1 THEN IF Cell(x%, y% - 1).mine THEN Mines% = Mines% + 1 ' if mine below add to mines if not at top of grid
IF Mines% <> 0 THEN ' were any mines found?
Cell(x%, y%).pic = Mines% ' yes, set this cell's picture to number found
_PUTIMAGE (Cell(x%, y%).x, Cell(x%, y%).y), CellPic&(Cell(x%, y%).pic) ' display the cell image
CellsRemaining% = CellsRemaining% - 1 ' decrement cell remaining count
EXIT SUB ' do not check any adjacent cells
END IF
CellsRemaining% = CellsRemaining% - 1 ' decrement cell remaining count
Cell(x%, y%).pic = 10 ' no mines found, set to blank picture
_PUTIMAGE (Cell(x%, y%).x, Cell(x%, y%).y), CellPic&(10) ' display the black image at cell location
REVEALCELL x% - 1, y% ' move left to next grid cell
REVEALCELL x% + 1, y% ' move right to next grid cell
REVEALCELL x%, y% - 1 ' move up to next grid cell
REVEALCELL x%, y% + 1 ' move down to next grid cell
REVEALCELL x% - 1, y% - 1 ' move left/up to next grid cell
REVEALCELL x% - 1, y% + 1 ' move left/down to next grid cell
REVEALCELL x% + 1, y% - 1 ' move right/up to next grid cell
REVEALCELL x% + 1, y% + 1 ' move right/down to next grid cell
END SUBRecursive-like routines can also be achieved using a stack as I did in my Super MegaBug program:
Code: (Select All)
SUB CreateRandomMaze
'****************************************************************************
'* *
'* Creates a random sized braided (looping) maze by first creating a *
'* perfect maze (a maze with no loops) then visiting each dead end and *
'* randomly opening them to create loops. *
'* *
'* vcells stores valid next maze cell moves in binary (bit) format *
'* if all adjacent cell walls are turned on then that cell is saved in *
'* vcells as follows: *
'* bit 1 (2^0) = north cell has all walls on *
'* bit 2 (2^1) = east cell has all walls on *
'* bit 3 (2^2) = south cell has all walls on *
'* bit 4 (2^3) = west cell has all walls on *
'* *
'* This subroutine was generated from psuedo-code found at mazeworks.com *
'* *
'* http://www.mazeworks.com/mazegen/mazetut/index.htm *
'* *
'* I would like to thank mazeworks.com for taking the time to write their *
'* very informative tutorial on braided mazes. *
'* *
'****************************************************************************
DIM stack(1280) AS stack ' maze generation LIFO stack
DIM cellx, celly, counter AS INTEGER ' general counters
DIM ccell AS stack ' current cell being created
DIM pointer AS INTEGER ' pointer for use in LIFO stack
DIM vcells AS INTEGER ' which cells are valid moves
DIM randomwall AS INTEGER ' random valid direction mover
DIM forward AS INTEGER ' movement indicator
RANDOMIZE TIMER ' seed generator
FOR cellx = 0 TO 39 ' initialize grid
FOR celly = 0 TO 31
cell(cellx, celly).walls = 15 ' turn all walls on
cell(cellx, celly).x = 80 + cellx * 4 ' upper left x
cell(cellx, celly).y = 36 + celly * 4 ' upper left y
cell(cellx, celly).npell = False ' north pellet off
cell(cellx, celly).wpell = False ' west pellet off
cell(cellx, celly).cpell = 2 ' center pellet food
NEXT celly
NEXT cellx
ccell.x = INT(RND(1) * 39) ' random x start
ccell.y = INT(RND(1) * 31) ' random y start
visitedcells = 1 ' initialize counter
pointer = 0 ' LIFO stack pointer
forward = False ' movement indicator
WHILE visitedcells < 1280 ' until all cells
vcells = 0 ' valid move check
'**
'** The following 12 lines of code look at all four adjoining maze cells
'** (north, east, south and west) and determine if all the walls in each
'** cell are turned on. If so each corresponding bit in vcells is turned on
'** (2^0 = north, 2^1 = east, 2^2 = south, 2^3 = west). If a bit is on (1)
'** then that direction is a valid move. If a bit is off (0) then that
'** direction has already been visited (invalid move).
'**
IF ccell.y <> 0 THEN
IF cell(ccell.x, ccell.y - 1).walls = 15 THEN vcells = vcells + 1
END IF
IF ccell.x <> 39 THEN
IF cell(ccell.x + 1, ccell.y).walls = 15 THEN vcells = vcells + 2
END IF
IF ccell.y <> 31 THEN
IF cell(ccell.x, ccell.y + 1).walls = 15 THEN vcells = vcells + 4
END IF
IF ccell.x <> 0 THEN
IF cell(ccell.x - 1, ccell.y).walls = 15 THEN vcells = vcells + 8
END IF
'**
IF vcells <> 0 THEN ' a cell has walls
DO ' find random dir
randomwall = INT(RND(1) * 4) ' select random wall
LOOP UNTIL vcells AND 2 ^ randomwall ' is it valid?
stack(pointer) = ccell ' save cell in stack
pointer = pointer + 1 ' increment pointer
visitedcells = visitedcells + 1 ' increment counter
forward = True ' forward movement
RemoveWall ccell.x, ccell.y, randomwall ' remove random wall
SELECT CASE randomwall ' which direction?
CASE North ' north wall
ccell.y = ccell.y - 1 ' move north
CASE East ' east wall
ccell.x = ccell.x + 1 ' move east
CASE South ' south wall
ccell.y = ccell.y + 1 ' move south
CASE West ' west wall
ccell.x = ccell.x - 1 ' move west
END SELECT
ELSE ' no walls!
IF forward THEN ' we hit a dead end!
forward = False ' stop movement here
IF Fifty50 THEN ' make looping maze?
SELECT CASE randomwall ' which random wall?
CASE North ' remove north wall
IF ccell.y <> 0 THEN ' unless a border
RemoveWall ccell.x, ccell.y, randomwall ' remove now
END IF
CASE East ' remove east wall
IF ccell.x <> 39 THEN ' unless a border
RemoveWall ccell.x, ccell.y, randomwall ' remove now
END IF
CASE South ' remove south wall
IF ccell.y <> 31 THEN ' unless a border
RemoveWall ccell.x, ccell.y, randomwall ' remove now
END IF
CASE West ' remove west wall
IF ccell.x <> 0 THEN ' unless a border
RemoveWall ccell.x, ccell.y, randomwall ' remove now
END IF
END SELECT
END IF
END IF
pointer = pointer - 1 ' decrement pointer
ccell = stack(pointer) ' go previous cell
END IF
WEND ' all cells visited
END SUBThe maze generation code could have been done with recursion as well but a stack did nicely in this case.
RE: Why does my Loop end after 11 Loops? - Dimster - 02-12-2023
And the Basic Binder grows recursively. Thanks Terry. I'm into the Super Bowl case of beer now .... planning my next hair brained assault on QB64pe