Learn To Code: Recursion Examples

[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:
   

Code Select Expand


   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