Recursion in FreeBASIC

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

Recursion in FreeBASIC

Postby jfiofficial » Jun 27, 2019 4:02

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: 9076
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Recursion in FreeBASIC

Postby fxm » Jun 27, 2019 4:48

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

Re: Recursion in FreeBASIC

Postby fxm » Jun 27, 2019 9:54

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: 113
Joined: Apr 19, 2019 19:03

Re: Recursion in FreeBASIC

Postby Knatterton » Jun 27, 2019 10:32

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.
badidea
Posts: 1417
Joined: May 24, 2007 22:10
Location: The Netherlands

Re: Recursion in FreeBASIC

Postby badidea » Jun 27, 2019 20:27

A 'classic' example is flood fill:

Code: Select all

const SCRN_W = 640, SCRN_H = 480
const 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 if
end sub

screenres SCRN_W, SCRN_H, 32
width SCRN_W \ 8, SCRN_H \ 16

dim as integer x1, y1, x2, y2

randomize 12345
'draw border
line(0, 0)-(SCRN_W - 1, SCRN_H - 1), GREEN, b
'randon dashed lines
for 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, , &h0f0f
next

floodFill(SCRN_W \ 2, SCRN_H \ 2, RED)

print "End"
sleep

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

Re: Recursion in FreeBASIC

Postby fxm » Jun 27, 2019 20:53

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

Re: Recursion in FreeBASIC

Postby badidea » Jun 27, 2019 21:23

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 = 480
const 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 = 10
const NUM_BLOCK_X = SCRN_W \ BLOCK_SIZE
const NUM_BLOCK_Y = SCRN_H \ BLOCK_SIZE

'sorry shared variable, I was lazy
dim 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 sub

sub 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 if
end sub

screenres SCRN_W, SCRN_H, 32
width SCRN_W \ 8, SCRN_H \ 16
dim as ulong c

randomize 123
'fill grid black with green border
for 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)
   next
next

'start filling in center
floodFill(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

Postby jfiofficial » Jun 28, 2019 18:28

thank you all. ill read what's in the link :)
fxm
Posts: 9076
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Recursion in FreeBASIC

Postby fxm » Jun 29, 2019 9:14

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 if
end 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
   Wend
end 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

#endmacro

DynamicUserStackTypeCreate(DynamicUserStackTypeForInteger, Integer)


const SCRN_W = 640, SCRN_H = 480
const 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 = 10
const NUM_BLOCK_X = SCRN_W \ BLOCK_SIZE
const NUM_BLOCK_Y = SCRN_H \ BLOCK_SIZE

'sorry shared variable, I was lazy
dim 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 sub

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
   Wend
end sub

screenres SCRN_W, SCRN_H, 32
width SCRN_W \ 8, SCRN_H \ 16
dim as ulong c

randomize 123
'fill grid black with green border
for 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)
   next
next

'start filling in center
floodFillIterative(NUM_BLOCK_X \ 2, NUM_BLOCK_Y \ 2, RED)

print "End"
sleep


@badidea,
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

#endmacro

DynamicUserStackTypeCreate(DynamicUserStackTypeForInteger, Integer)


const SCRN_W = 640, SCRN_H = 480
const 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
   Wend
end sub

screenres SCRN_W, SCRN_H, 32
width SCRN_W \ 8, SCRN_H \ 16

dim as integer x1, y1, x2, y2

randomize 12345
'draw border
line(0, 0)-(SCRN_W - 1, SCRN_H - 1), GREEN, b
'randon dashed lines
for 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, , &h0f0f
next

floodFillRecursive(SCRN_W \ 2, SCRN_H \ 2, RED)

print "End"
sleep


[edit]
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: 916
Joined: Jul 25, 2017 17:22
Location: Argentina

Re: Recursion in FreeBASIC

Postby paul doe » Jun 29, 2019 13:18

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, y
end type

constructor _
  PointF()
 
  this.constructor( 0.0, 0.0 )
end constructor

constructor _
  PointF( _
    byval nX as single, _
    byval nY as single )
 
  x => nX
  y => nY
end constructor

destructor _
  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 _
      _penColor
end type

constructor _
  Turtle()
 
  this.constructor( _
    PointF( 0.0, 0.0 ) )
end constructor

constructor _
  Turtle( _
    byref aPosition as PointF )
 
  _position => aPosition
  _prevPosition => _position
  _heading => PointF( 0.0, -1.0 )
  _penColor => rgb( 0, 0, 0 )
end constructor

destructor _
  Turtle()
end destructor

function _
  Turtle.setPosition( _
    byref aPosition as PointF ) _
  byref as Turtle
 
  _position => aPosition
  _prevPosition => _position
 
  return( this )
end function

function _
  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 function

function _
  Turtle.backward( _
    byval amount as single ) _
  byref as Turtle
 
  forward( -amount )
 
  return( this )
end function

function _
  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 function

function _
  Turtle.left( _
    byval angle as single ) _
  byref as Turtle
 
  right( -angle )
 
  return( this )
end function

function _
  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 colors
screenRes( _
  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 tree
tree( t, canvasHeight / 2.0 )

sleep()


Image

That should give you quite a few cool ideas to try on the Maslow ;)
fxm
Posts: 9076
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

Re: Recursion in FreeBASIC

Postby fxm » Jun 29, 2019 14:19

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.

Return to “Beginners”

Who is online

Users browsing this forum: No registered users and 1 guest