## Recursion in FreeBASIC

New to FreeBASIC? Post your questions here.
jfiofficial
Posts: 5
Joined: Nov 05, 2018 8:55

### Recursion in FreeBASIC

best and easy explanation and an example using the Recursive/Recursion in FreeBASIC.? strive to study it but still don't get it.
my understanding about this is that you can call itself like the declare a sub procedure inside?
fxm
Posts: 9408
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

### Re: Recursion in FreeBASIC

fxm
Posts: 9408
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

### Re: Recursion in FreeBASIC

I just realized that this article contains enough material to create and fill in the "Recursion" page of the "Programmer's Guide" (in "Procedures" section).
I would probably do it during my free time.
Knatterton
Posts: 165
Joined: Apr 19, 2019 19:03

### Re: Recursion in FreeBASIC

jfiofficial wrote:best and easy explanation and an example using the Recursive/Recursion in FreeBASIC.? strive to study it but still don't get it.
my understanding about this is that you can call itself like the declare a sub procedure inside?

Fxm answered in full detail, what i never could do in this completeness.

Im my understanding i would answer. recursion makes some code a little shorter, but not better understandable. It is often not so easy to understand this tricky technique. In order to make code more fast, readable and maintable it is often the best to keep everything as easy as possible. And the more complicated code becomes the more likely errors happen.
Posts: 1704
Joined: May 24, 2007 22:10
Location: The Netherlands

### Re: Recursion in FreeBASIC

A 'classic' example is flood fill:

Code: Select all

`const SCRN_W = 640, SCRN_H = 480const as ulong BLACK = rgb(0, 0, 0)const as ulong RED = rgb(255, 0, 0)const as ulong GREEN = rgb(0, 255, 0)sub floodFill(x as integer, y as integer, fillColor as ulong)   static as integer slowAnimation = 1   if point(x, y) = BLACK then      pset(x, y), fillColor      if inkey = chr(27) then slowAnimation = 0      if slowAnimation = 1 then sleep 1      floodFill(x - 1, y, fillColor)      floodFill(x, y - 1, fillColor)      floodFill(x + 1, y, fillColor)      floodFill(x, y + 1, fillColor)   end ifend subscreenres SCRN_W, SCRN_H, 32width SCRN_W \ 8, SCRN_H \ 16dim as integer x1, y1, x2, y2randomize 12345'draw borderline(0, 0)-(SCRN_W - 1, SCRN_H - 1), GREEN, b'randon dashed linesfor i as integer = 1 to 500   x1 = int(rnd * SCRN_W * 2) - SCRN_W \ 2   y1 = int(rnd * SCRN_H * 2) - SCRN_H \ 2   x2 = int(rnd * SCRN_W * 2) - SCRN_W \ 2   y2 = int(rnd * SCRN_H * 2) - SCRN_H \ 2   line(x1, y1)-(x2, y2), GREEN, , &h0f0fnextfloodFill(SCRN_W \ 2, SCRN_H \ 2, RED)print "End"sleep `

Without recursion, more complex I think.
fxm
Posts: 9408
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

### Re: Recursion in FreeBASIC

But program crashes (in Windows), by execution stack overflow I suppose.
Posts: 1704
Joined: May 24, 2007 22:10
Location: The Netherlands

### Re: Recursion in FreeBASIC

fxm wrote:But program crashes (in Windows), by execution stack overflow I suppose.

I will make a smaller example...
Anyway, demonstration of another disadvantage of recursive functions :-)

OK for Windows now?

Code: Select all

`const SCRN_W = 640, SCRN_H = 480const as ulong BLACK = rgb(0, 0, 0)const as ulong RED = rgb(255, 0, 0)const as ulong GREEN = rgb(0, 255, 0)const BLOCK_SIZE = 10const NUM_BLOCK_X = SCRN_W \ BLOCK_SIZEconst NUM_BLOCK_Y = SCRN_H \ BLOCK_SIZE'sorry shared variable, I was lazydim shared as ulong grid(NUM_BLOCK_X - 1, NUM_BLOCK_Y - 1)sub setGridAndShow(x as integer, y as integer, c as ulong)   grid(x, y) = c   line(x * BLOCK_SIZE + 1, y * BLOCK_SIZE + 1)-_      step(BLOCK_SIZE - 3, BLOCK_SIZE - 3), c, bf end subsub floodFill(x as integer, y as integer, fillColor as ulong)   static as integer slowAnimation = 1   if grid(x, y) = BLACK then      setGridAndShow(x, y, fillColor)      if inkey = chr(27) then slowAnimation = 0      if slowAnimation = 1 then sleep 15      floodFill(x - 1, y, fillColor)      floodFill(x, y - 1, fillColor)      floodFill(x + 1, y, fillColor)      floodFill(x, y + 1, fillColor)   end ifend subscreenres SCRN_W, SCRN_H, 32width SCRN_W \ 8, SCRN_H \ 16dim as ulong crandomize 123'fill grid black with green borderfor x as integer = 0 to NUM_BLOCK_X - 1   for y as integer = 0 to NUM_BLOCK_Y - 1      if x = 0 or y = 0 or x = NUM_BLOCK_X - 1 or y = NUM_BLOCK_Y - 1 then         c = GREEN 'green border      else         if rnd > 0.4 then c = BLACK else c = GREEN      end if         setGridAndShow(x, y, c)   nextnext'start filling in centerfloodFill(NUM_BLOCK_X \ 2, NUM_BLOCK_Y \ 2, RED)print "End"sleep `
jfiofficial
Posts: 5
Joined: Nov 05, 2018 8:55

### Re: Recursion in FreeBASIC

fxm
Posts: 9408
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

### Re: Recursion in FreeBASIC

Replacing the recursive procedure ('floodFillRecursive(()') with an iterative procedure ('floodFillIterative()'), by using a user dynamic stack instance ('S') of Integers, as described in my article ('How to Replace Any Recursion with Simple Iteration or Unlimited Iteration with its Own Stack, in FB'):

Code: Select all

`sub floodFillRecursive(x as integer, y as integer, fillColor as ulong)   static as integer slowAnimation = 1   if grid(x, y) = BLACK then      setGridAndShow(x, y, fillColor)      if inkey = chr(27) then slowAnimation = 0      if slowAnimation = 1 then sleep 15      floodFill(x - 1, y, fillColor)      floodFill(x, y - 1, fillColor)      floodFill(x + 1, y, fillColor)      floodFill(x, y + 1, fillColor)   end ifend sub`

Code: Select all

`sub floodFillIterative(x as integer, y as integer, fillColor as ulong)   static as integer slowAnimation = 1   Dim As DynamicUserStackTypeForInteger S   S.push = x : S.push = y   While S.used > 0     y = S.pop : x = S.pop     if grid(x, y) = BLACK then        setGridAndShow(x, y, fillColor)        if inkey = chr(27) then slowAnimation = 0        if slowAnimation = 1 then sleep 15        S.push = x : S.push = y + 1        S.push = x + 1 : S.push = y        S.push = x : S.push = y - 1        S.push = x - 1 : S.push = y     end if   Wendend sub`

Full code with the macro for 'Dynamic User Stack Type Creation':

Code: Select all

`#macro DynamicUserStackTypeCreate(typename, datatype)  Type typename    Public:      Declare Constructor ()                       '' pre-allocating user stack memory      Declare Property push (Byref i As datatype)  '' pushing on the user stack      Declare Property pop () Byref As datatype    '' popping from the user stack      Declare Property used () As Integer          '' outputting number of used elements in the user stack      Declare Property allocated () As Integer     '' outputting number of allocated elements in the user stack      Declare Destructor ()                        '' deallocating user stack memory    Private:      Dim As datatype ae (Any)  '' array of elements      Dim As Integer nue        '' number of used elements      Dim As Integer nae        '' number of allocated elements      Dim As Integer nae0       '' minimum number of allocated elements  End Type  Constructor typename ()    This.nae0 = 2^Int(Log(1024 * 1024 / Sizeof(datatype)) / Log(2) + 1) '' only a power of 2 (1 MB < stack memory < 2 MB here)    This.nue = 0    This.nae = This.nae0    Redim This.ae(This.nae - 1)                                         '' pre-allocating user stack memory  End constructor  Property typename.push (Byref i As datatype)  '' pushing on the user stack    This.nue += 1    If This.nue > This.nae0 And This.nae < This.nue * 2 Then      This.nae *= 2      Redim Preserve This.ae(This.nae - 1)  '' allocating user stack memory for double used elements at least    End If    This.ae(This.nue - 1) = i  End Property  Property typename.pop () Byref As datatype  '' popping from the user stack    If This.nue > 0 Then      Property = This.ae(This.nue - 1)      This.nue -= 1      If This.nue > This.nae0 And This.nae > This.nue * 2 Then        This.nae \= 2        Redim Preserve This.ae(This.nae - 1)  '' allocating user stack memory for double used elements at more      End If    Else      Static As datatype d      dim As datatype d0      d = d0      Property = d      Assertwarn(This.nue > 0)  '' warning if popping while empty user stack and debug mode (-g compiler option)    End If  End Property  Property typename.used () As Integer  '' outputting number of used elements in the user stack    Property = This.nue  End property  Property typename.allocated () As Integer  '' outputting number of allocated elements in the user stack    Property = This.nae  End property  Destructor typename  '' deallocating user stack memory    This.nue = 0    This.nae = 0    Erase This.ae  '' deallocating user stack memory  End destructor#endmacroDynamicUserStackTypeCreate(DynamicUserStackTypeForInteger, Integer)const SCRN_W = 640, SCRN_H = 480const as ulong BLACK = rgb(0, 0, 0)const as ulong RED = rgb(255, 0, 0)const as ulong GREEN = rgb(0, 255, 0)const BLOCK_SIZE = 10const NUM_BLOCK_X = SCRN_W \ BLOCK_SIZEconst NUM_BLOCK_Y = SCRN_H \ BLOCK_SIZE'sorry shared variable, I was lazydim shared as ulong grid(NUM_BLOCK_X - 1, NUM_BLOCK_Y - 1)sub setGridAndShow(x as integer, y as integer, c as ulong)   grid(x, y) = c   line(x * BLOCK_SIZE + 1, y * BLOCK_SIZE + 1)-_      step(BLOCK_SIZE - 3, BLOCK_SIZE - 3), c, bfend subsub floodFillIterative(x as integer, y as integer, fillColor as ulong)   static as integer slowAnimation = 1   Dim As DynamicUserStackTypeForInteger S   S.push = x : S.push = y   While S.used > 0     y = S.pop : x = S.pop     if grid(x, y) = BLACK then        setGridAndShow(x, y, fillColor)        if inkey = chr(27) then slowAnimation = 0        if slowAnimation = 1 then sleep 15        S.push = x : S.push = y + 1        S.push = x + 1 : S.push = y        S.push = x : S.push = y - 1        S.push = x - 1 : S.push = y     end if   Wendend subscreenres SCRN_W, SCRN_H, 32width SCRN_W \ 8, SCRN_H \ 16dim as ulong crandomize 123'fill grid black with green borderfor x as integer = 0 to NUM_BLOCK_X - 1   for y as integer = 0 to NUM_BLOCK_Y - 1      if x = 0 or y = 0 or x = NUM_BLOCK_X - 1 or y = NUM_BLOCK_Y - 1 then         c = GREEN 'green border      else         if rnd > 0.4 then c = BLACK else c = GREEN      end if         setGridAndShow(x, y, c)   nextnext'start filling in centerfloodFillIterative(NUM_BLOCK_X \ 2, NUM_BLOCK_Y \ 2, RED)print "End"sleep`

Your previous version modified in the same way works well in Windows:

Code: Select all

`#macro DynamicUserStackTypeCreate(typename, datatype)  Type typename    Public:      Declare Constructor ()                       '' pre-allocating user stack memory      Declare Property push (Byref i As datatype)  '' pushing on the user stack      Declare Property pop () Byref As datatype    '' popping from the user stack      Declare Property used () As Integer          '' outputting number of used elements in the user stack      Declare Property allocated () As Integer     '' outputting number of allocated elements in the user stack      Declare Destructor ()                        '' deallocating user stack memory    Private:      Dim As datatype ae (Any)  '' array of elements      Dim As Integer nue        '' number of used elements      Dim As Integer nae        '' number of allocated elements      Dim As Integer nae0       '' minimum number of allocated elements  End Type  Constructor typename ()    This.nae0 = 2^Int(Log(1024 * 1024 / Sizeof(datatype)) / Log(2) + 1) '' only a power of 2 (1 MB < stack memory < 2 MB here)    This.nue = 0    This.nae = This.nae0    Redim This.ae(This.nae - 1)                                         '' pre-allocating user stack memory  End constructor  Property typename.push (Byref i As datatype)  '' pushing on the user stack    This.nue += 1    If This.nue > This.nae0 And This.nae < This.nue * 2 Then      This.nae *= 2      Redim Preserve This.ae(This.nae - 1)  '' allocating user stack memory for double used elements at least    End If    This.ae(This.nue - 1) = i  End Property  Property typename.pop () Byref As datatype  '' popping from the user stack    If This.nue > 0 Then      Property = This.ae(This.nue - 1)      This.nue -= 1      If This.nue > This.nae0 And This.nae > This.nue * 2 Then        This.nae \= 2        Redim Preserve This.ae(This.nae - 1)  '' allocating user stack memory for double used elements at more      End If    Else      Static As datatype d      dim As datatype d0      d = d0      Property = d      Assertwarn(This.nue > 0)  '' warning if popping while empty user stack and debug mode (-g compiler option)    End If  End Property  Property typename.used () As Integer  '' outputting number of used elements in the user stack    Property = This.nue  End property  Property typename.allocated () As Integer  '' outputting number of allocated elements in the user stack    Property = This.nae  End property  Destructor typename  '' deallocating user stack memory    This.nue = 0    This.nae = 0    Erase This.ae  '' deallocating user stack memory  End destructor#endmacroDynamicUserStackTypeCreate(DynamicUserStackTypeForInteger, Integer)const SCRN_W = 640, SCRN_H = 480const as ulong BLACK = rgb(0, 0, 0)const as ulong RED = rgb(255, 0, 0)const as ulong GREEN = rgb(0, 255, 0)sub floodFillRecursive(x as integer, y as integer, fillColor as ulong)   static as integer slowAnimation = 1   Dim As DynamicUserStackTypeForInteger S   S.push = x : S.push = y   While S.used > 0     y = S.pop : x = S.pop     if point(x, y) = BLACK then        pset(x, y), fillColor        if inkey = chr(27) then slowAnimation = 0        if slowAnimation = 1 then sleep 15        S.push = x : S.push = y + 1        S.push = x + 1 : S.push = y        S.push = x : S.push = y - 1        S.push = x - 1 : S.push = y     end if   Wendend subscreenres SCRN_W, SCRN_H, 32width SCRN_W \ 8, SCRN_H \ 16dim as integer x1, y1, x2, y2randomize 12345'draw borderline(0, 0)-(SCRN_W - 1, SCRN_H - 1), GREEN, b'randon dashed linesfor i as integer = 1 to 500   x1 = int(rnd * SCRN_W * 2) - SCRN_W \ 2   y1 = int(rnd * SCRN_H * 2) - SCRN_H \ 2   x2 = int(rnd * SCRN_W * 2) - SCRN_W \ 2   y2 = int(rnd * SCRN_H * 2) - SCRN_H \ 2   line(x1, y1)-(x2, y2), GREEN, , &h0f0fnextfloodFillRecursive(SCRN_W \ 2, SCRN_H \ 2, RED)print "End"sleep`

In order to keep the same drawing order, the four operand order must to be reversed when pushing context on user stack instead of before when popping context from execution stack (as mentioned in the article).
Last edited by fxm on Jun 29, 2019 13:36, edited 3 times in total.
paul doe
Posts: 1018
Joined: Jul 25, 2017 17:22
Location: Argentina

### Re: Recursion in FreeBASIC

jfiofficial wrote:best and easy explanation and an example using the Recursive/Recursion in FreeBASIC.? strive to study it but still don't get it.
my understanding about this is that you can call itself like the declare a sub procedure inside?

Recursiveness is a fundamental technique, quite easy to use (but not so easy to grasp) and quite powerful. Here is a simple examples that show simple recursive functions that do simple tasks:

Code: Select all

`/'  Simple tail recursion example'/function _  recurse( _    byval times as integer ) _  as integer    ? "I'm learning about recursion " & _    times & iif( times = 1, " time.", " times." )    return( iif( times > 1, _    recurse( times - 1 ), _    0 ) )end function/'  A little more meaningful example of tail recursion: reversal  of a string.'/function _  reverse( _    byval s as string ) _  as string    if( s = "" ) then    return( "" )  end if    return( _    mid( s, len( s ), 1 ) + _    reverse( left( s, len( s ) - 1 ) ) )end function/'  Main code'/recurse( 10 )? reverse( "This is a reversed string" )sleep()`

As other members told you, most (but not all) tasks can be reformulated to work iteratively. However, recursive procedures are often simpler, more elegant, and quite efficient (as long as they are tail recursive; Google for that one). Finally, here is a classic example, that uses a Logo-style turtle to perform the typical 'recursive tree fractal':

Code: Select all

`/'  Some needed constants and definitions'/const as single _  Pi => 4.0 * atn( 1.0 ), _  degreesToRadians => ( Pi / 180.0 )#define toRadians( ang ) _  ( ( ang ) * degreesToRadians )/'  Represents a point in the Cartesian plane'/type _  PointF    declare constructor()  declare constructor( _    byval as single, _    byval as single )  declare destructor()    as single _    x, yend typeconstructor _  PointF()    this.constructor( 0.0, 0.0 )end constructorconstructor _  PointF( _    byval nX as single, _    byval nY as single )    x => nX  y => nYend constructordestructor _  PointF()end destructor/'  This class represents a simple Logo-like 'turtle' that can perform drawing  commands. 'Turtle drawing' differs from conventional drawing (using absolute  Cartesian coordinates) in that the turtle performs movement relative to  itself; that is, it has a position and a heading, and we draw by telling it   to 'go forward x steps', 'go backward y steps', and 'rotate z degrees to the  left'.    In this implementation, the turtle's heading is represented as a normalized  2D vector that initially points upwards, and positive rotation to the right  of the turtle rotates it counter-clockwise.    Very few commands are implemented (barely the ones needed for the example),  but adding methods to emulate a complete Logo turtle isn't hard at all. Note  however that all methods return a self reference, so you can chain them to  give many commands to the turtle with a single statement, like this:    aTurtle.forward( 50 ).right( 90 ).forward( 30 ).right( 90 ).forward( 50 ) ...'/type _  Turtle    public:    declare constructor()    declare constructor( _      byref as PointF )    declare destructor()        declare function _      setPosition( _        byref as PointF ) _      byref as Turtle    declare function _      forward( _        byval as single ) _      byref as Turtle    declare function _      backward( _        byval as single ) _      byref as Turtle    declare function _      left( _        byval as single ) _      byref as Turtle    declare function _      right( _        byval as single ) _      byref as Turtle    declare function _      penColor( _        byval as ulong ) _      byref as Turtle      private:    as PointF _      _position, _      _prevPosition, _      _heading    as ulong _      _penColorend typeconstructor _  Turtle()    this.constructor( _    PointF( 0.0, 0.0 ) )end constructorconstructor _  Turtle( _    byref aPosition as PointF )    _position => aPosition  _prevPosition => _position  _heading => PointF( 0.0, -1.0 )  _penColor => rgb( 0, 0, 0 )end constructordestructor _  Turtle()end destructorfunction _  Turtle.setPosition( _    byref aPosition as PointF ) _  byref as Turtle    _position => aPosition  _prevPosition => _position    return( this )end functionfunction _  Turtle.forward( _    byval amount as single ) _  byref as Turtle    _position.x +=> _heading.x * amount  _position.y +=> _heading.y * amount    line _    ( _prevPosition.x, _prevPosition.y ) - _    ( _position.x, _position.y ), _    _penColor    _prevPosition => _position    return( this )end functionfunction _  Turtle.backward( _    byval amount as single ) _  byref as Turtle    forward( -amount )    return( this )end functionfunction _  Turtle.right( _    byval angle as single ) _  byref as Turtle    dim as single _    si => sin( toRadians( angle ) ), _    co => cos( toRadians( angle ) )    _heading => PointF( _    _heading.x * co - _heading.y * si, _    _heading.x * si + _heading.y * co )    return( this )end functionfunction _  Turtle.left( _    byval angle as single ) _  byref as Turtle    right( -angle )    return( this )end functionfunction _  Turtle.penColor( _    byval aColor as ulong ) _  byref as Turtle    _penColor => aColor    return( this )end function/'  This procedure draws a tree recursively, starting at the current position of  the given Turtle and with the main trunk as tall as the given length.    This is a classic example of recursion, that allows you to conceptualize it  in a more 'visual' way. If you follow what the procedure does, and at the same  time draw the tree yourself on a piece of paper, you can get a pretty good  grasp of how recursion works.'/sub _  tree( _    byref t as Turtle, _    byval length as single )    if( length < 2.0 ) then    exit sub  end if    t.forward( length ).left( 45.0 )  tree( t, length / 2.0 )  t.right( 90.0 )  tree( t, length / 2.0 )  t.left( 45.0 ).backward( length )end sub/'  Main code'/'' Represent the width and height of the 'canvas' (the screen)dim as integer _  canvasWidth => 800, _  canvasHeight => 600'' Set up the screen, and foreground and background colorsscreenRes( _  canvasWidth, canvasHeight, 32 )color( _  rgb( 0, 0, 0 ), _  rgb( 255, 255, 255 ) )cls()'' Create a turtle to play with and place it horizontally at the middle of the'' screen, and vertically at the very bottom (remember its heading is initially to'' the top of the screen).var _  t => Turtle() _    .setPosition( PointF( _      canvasWidth / 2.0, _      canvasHeight - 1 ) )    '' And then call the recursive procedure to draw the treetree( t, canvasHeight / 2.0 )sleep()` That should give you quite a few cool ideas to try on the Maslow ;)
fxm
Posts: 9408
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

### Re: Recursion in FreeBASIC

paul doe wrote:As other members told you, most (but not all) tasks can be reformulated to work iteratively.

A recursive algorithm can always (more or less easily until with very difficulty) be replaced by an iterative algorithm (see my article in full for more information about some more or less easy cases).
But practically, you are right because your code above is one of the very difficult case types to transform into iteration.