locked
Recursive routines - learning material.

    Question

  • Does anyone know if there are any learning materials for designing recursive routines?

    I am trying to develop a routine which will evaluate all the possible paths that a specific checker (draughts) piece can make. At the beginning of the game it was quite simple there are only a few moves possible. As the game progresses the possibility of multiple paths arises. I am trying to use a recursive technique much like a tree search but I need to save only the paths which are valid. Imagine a player (online) selects a piece and points to where they want it to go.

    This gives rise to questions such as:

    Is it possible to move to that position?

    Are there different ways to reach that position?

    Does the move include the crowning (kinging) of the piece so that it may make backward jumps?

    I think it becomes necessary to have global variables which are outside the recursive routine as well as local variables inside the routine.

    I am looking for educational/teaching/tutorial resources.


    Alan Cameron
    Sunday, May 23, 2010 3:30 PM

Answers

  • The game of Checkers, huh.  Not as troubling as Chess.

    Lesson 5: Branching and Recursion using Visual Basic

    Recursive Procedures

    How to recursively search directories by using Visual Basic 2005 or ...

    Those links show you what recursion is and some ways to implement it for specific scenarios.  There is a OOP Design Pattern known as the Composite Pattern that frequently makes use of Recursion.  The directory search sample is an example of this pattern in action.

    Another example of the Composite in action is the System.Windows.Forms.Control.Controls collection.  It can be used to recursively search for controls on a form. 
      
        Dim result As Control = Nothing
        Private Sub FindControlByName(ByVal ctrl As Control, ByVal name As String)

            For Each control As Control In ctrl.Controls

                If control.Name = name Then
                    result = control
                Else
                    FindControlByName(control, name)
                End If

            Next control
           
        End Function

     


    Mark the best replies as answers. "Fooling computers since 1971."
    Monday, May 24, 2010 3:44 PM

All replies

  • To answer your question..... Recursion is one of those things in computer programming that you have to get yourself or it was when I got in it.

    For a recurive routine your best friend is the NEW keyword because you need context and the only way to achieve it is with NEW copies of variables. Stopping usually come when there is no more data to process. Stopping is accomplished by a return or continuing called by calling yourself again with the correct arguments.

    That about it.

    Renee

    Sunday, May 23, 2010 8:26 PM
  • The classic recursive is Factorial.  I copied the pseudo code from the Wiki:

      'function factorial is:
      'input: integer n such that n >= 0
      'output: [n × (n-1) × (n-2) × … × 1]
    
      '1. create new variable called running_total with a value of 1
    
      '2. begin loop
      '     1. if n is 0, exit loop
      '     2. set running_total to (running_total × n)
      '     3.decrement(n)
      '     4. repeat loop
    
      '3:   .return(running_total)
    
      'end factorial
    
      Private Sub Button3_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button3.Click
    
        Dim x As Integer = Fact(3)
        Dim y As Integer = Fact(5)
        Dim z As Integer = Fact(7)
      End Sub
    
      Dim ans As Integer = 0, ft As Boolean = True
      Private Function Fact(ByVal Factor As Integer) As Integer
        If Factor = 0 Then Exit Function
        If ft Then
          ans = 1
          ft = False
        End If
        ans = ans * Factor
        Fact(Factor - 1)
        ft = True
        Return ans
      End Function
    


    Subnet Calculator / Planner      Serial Port
    Monday, May 24, 2010 3:32 PM
  • The game of Checkers, huh.  Not as troubling as Chess.

    Lesson 5: Branching and Recursion using Visual Basic

    Recursive Procedures

    How to recursively search directories by using Visual Basic 2005 or ...

    Those links show you what recursion is and some ways to implement it for specific scenarios.  There is a OOP Design Pattern known as the Composite Pattern that frequently makes use of Recursion.  The directory search sample is an example of this pattern in action.

    Another example of the Composite in action is the System.Windows.Forms.Control.Controls collection.  It can be used to recursively search for controls on a form. 
      
        Dim result As Control = Nothing
        Private Sub FindControlByName(ByVal ctrl As Control, ByVal name As String)

            For Each control As Control In ctrl.Controls

                If control.Name = name Then
                    result = control
                Else
                    FindControlByName(control, name)
                End If

            Next control
           
        End Function

     


    Mark the best replies as answers. "Fooling computers since 1971."
    Monday, May 24, 2010 3:44 PM
  • Another classic.

    Subnet Calculator / Planner      Serial Port
    Monday, May 24, 2010 3:51 PM