Results 1 to 4 of 4

Thread: Recursion Check

  1. #1

    Thread Starter
    Hyperactive Member
    Join Date
    Feb 2000
    Location
    Sedgefield
    Posts
    337

    Recursion Check

    I have an item with a name, which runs a recursive routine. Part of that execution involves the possible 'running' of other items of the same type.

    I need to check that the recusion is not infinite (i.e. an item will never run itself). The nesting is unlimited.

    Is there an efficient algorithm to check this? I can build up the list of the item names, and I'd want to exit if a name is already in the list, but the checking could make this prohibitive time-wise.

    Is it quicker to build the whole name list and then check for multiple entries? Or check after each addition?

    Or is there a better way?

    Any suggestions?

    Dan

    Outside of a dog, a book is a man's best friend.
    Inside of a dog, it's too dark to read.

  2. #2
    jim mcnamara
    Guest
    Create an enum of names, then create a simple global array with that many elements, set them all to zero.
    Code:
    Public enum names
         name1
         name2
         ... ad nauseum
    end enum
    Public arr(100) as Integer
    For x = 0 to  name64
        arr(x)=0
    next x
    ..............
    
    'as each name comes up
    '  check to see 
    if arr(name) >0 then 
        Exit Sub ' quit the alogorithm
    else
          arr(name )=1
    end if

  3. #3

    Thread Starter
    Hyperactive Member
    Join Date
    Feb 2000
    Location
    Sedgefield
    Posts
    337

    Thanks, but...

    I don't know how many names there will be before hand, or what they will be. I can only evaluate the list at run time (i.e. it is user configurable).

    Any item can refer to up to 10 other item names, which I can look up.

    Actually, each item has a unique index (from 1 to 3000). Can I somehow use a MOD to check if that index is already present...

    Code:
    (pseudocode)
    Type Item
       Name As String * 10
       Index As Long
       Ref(10) As Item
    End Type
    Its a puzzle. I can do it the hard way, but I'm looking for the quickest...

    Dan

    Outside of a dog, a book is a man's best friend.
    Inside of a dog, it's too dark to read.

  4. #4
    wossname
    Guest
    I used a boolean array recently to check if a node on a tree had been dealt with.
    VB Code:
    1. Public Trail() as Boolean
    2. ....
    3. ....
    4. ....
    5.  
    6. NumNodes = LoadTree(Filename") 'returns number of nodes unsurprisingly!
    7.  
    8. Redim Trail(1 to NumNodes) as Boolean
    9. ....
    10. ....
    11. ....
    12.  
    13. 'inside recursive function
    14. if Trail(Whatever) then
    15. CollapseRecursion = True 'a public flag to kill recursion upon finding a repetition.
    16. Else
    17. DealWith(Whatever)
    18. End If

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  



Click Here to Expand Forum to Full Width