Recursion in FreeBASIC

[jfiofficial]

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]

See perhaps the beginning of this article (up to paragraph 2):
How to Replace Any Recursion with Simple Iteration or Unlimited Iteration with its Own Stack, in FB

[fxm]

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]

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]

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]

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

[badidea]

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]

thank you all. ill read what's in the link :)

[fxm]

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

[paul doe]

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()

That should give you quite a few cool ideas to try on the Maslow ;)

[fxm]

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.