Recursion in FreeBASIC
-
- 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?
my understanding about this is that you can call itself like the declare a sub procedure inside?
Re: Recursion in FreeBASIC
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
How to Replace Any Recursion with Simple Iteration or Unlimited Iteration with its Own Stack, in FB
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.
I would probably do it during my free time.
-
- Posts: 165
- Joined: Apr 19, 2019 19:03
Re: Recursion in FreeBASIC
Fxm answered in full detail, what i never could do in this completeness.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?
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.
Re: Recursion in FreeBASIC
A 'classic' example is flood fill:
Without recursion, more complex I think.
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
Re: Recursion in FreeBASIC
But program crashes (in Windows), by execution stack overflow I suppose.
Re: Recursion in FreeBASIC
I will make a smaller example...fxm wrote:But program crashes (in Windows), by execution stack overflow I suppose.
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
-
- Posts: 5
- Joined: Nov 05, 2018 8:55
Re: Recursion in FreeBASIC
thank you all. ill read what's in the link :)
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'):
Full code with the macro for 'Dynamic User Stack Type Creation':
@badidea,
Your previous version modified in the same way works well in Windows:
[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).
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
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
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
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.
Re: Recursion in FreeBASIC
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: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?
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()
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 ;)
Re: Recursion in FreeBASIC
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).paul doe wrote: As other members told you, most (but not all) tasks can be reformulated to work iteratively.
But practically, you are right because your code above is one of the very difficult case types to transform into iteration.