Learn To Code: Recursion Examples

Started by kevin, March 15, 2022, 09:01:18 PM

Previous topic - Next topic

kevin

  Learn To Code: Recursion Examples


    Recursion is used for when we need our programming language to leave a trail a breed crumbs while searching though multiple paths ways of data for some answer.  


   
[ Flood Filling ]


    One classic problem would be something like writing an algorithm that performs a flood fill of an image.  So given a starting point within the  image bounds,  we then replace that colour and all the colours surrounding this (to the left/right / top & bottom) with a new colour of our choice.   Then for each of those colours we repeat the process.



PlayBASIC Code: [Select]
   //  Set up an image for something to fill
image=newimage(200,200)

// draw some circles on it to make it more interesting
rendertoimage image
r=50
circlec 0 ,0,r,true ,$00ff00
circlec 200 ,0,r,true ,$ff0000
circlec 0 ,200,r,true ,$0000ff
circlec 200 ,200,r,true ,$ff00ff
circlec 100 ,100,r,true ,$ffffff


// ---------------------------------------------------
Do
// ---------------------------------------------------

// Draw our image
rendertoscreen
drawimage Image,0,0,false

// Check if the mouse is down
if mousebutton()
mx=mousex()
my=mousey()

// is the mouse over the mouse
if pointinbox(mx,my,0,0,getimagewidth(Image),getimageheight(Image)-1)

// call the fill
rendertoimage Image
lockbuffer
FloodFill(mX,mY,point(mx,my), rndrgb())
unlockbuffer
rendertoscreen
endif
endif



sync
loop Spacekey()

end


function FloodFill(X,Y,ReplaceColour, NewColour)

; check if the colour we're over is our
; replacement colour ??
if point(x,Y) = replaceColour

; If it is, we replace it
Dotc X,Y,NewColour

; Now, We check dots around this starting location
; if the coordinate is legal (within the current image size)
; we recursively call ourselves. This will fill the dots
; to the left/Right/Above and bellow us, and in turn
; the dots around those dots and so on.

if (X-1)>=0 then FloodFill(X-1,Y,ReplaceColour, NewColour)
if (X+1)<GetSurfaceWidth() then FloodFill(X+1,Y,ReplaceColour, NewColour)
if (Y-1)>=0 then FloodFill(X,Y-1,ReplaceColour, NewColour)
if (Y+1)<GetSurfaceHeight() then FloodFill(X,Y+1,ReplaceColour, NewColour)

endif
EndFunction







   Note:  Beware though, each time we recurse (call the same function from with the function) we've leaving old local data (all the data for variables/arrays etc that your language uses) on whats called the stack.    The stack has a limited size; hence deeply nested functions can run out of memory.    Which if you try this demo you'll not don't notice :)  




   
[ Generate Fibonacci Series using Recursion ]



PlayBASIC Code: [Select]
  // Generate Fibonacci Series using Recursion

For lp =0 to 25

S$+=str$(Fibonacci(lp) )+","

next
print s$
#print s$

sync
waitkey


Function Fibonacci(Number)
if Number>1
Result1 =Fibonacci(Number-1)
Result2 =Fibonacci(Number-2)
Number =Result1+Result2
endif
EndFunction Number






    output:
   
   0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,
   

 
    Learn about fibonacci-sequence