Why does my Loop end after 11 Loops?

[Dimster]

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

[Kernelpanic]

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 Function

[Dimster]

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.

[mnrvovrfc]

Recursion is almost a necessity in LISP and in its leading descendants Common LISP and Scheme.

[SMcNeill]

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 SUB

Now 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 FUNCTION

Now 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 SUB

Your 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?

[Dimster]

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.

[bplus]

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.

[Dimster]

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
Next

 
TN 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.

[TerryRitchie]

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 SUB

Recursive-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 SUB

The maze generation code could have been done with recursion as well but a stack did nicely in this case.

[Dimster]

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