Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people, just like you, are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
Solved

Recursion & Random Numbers

Posted on 2002-06-08
10
163 Views
Last Modified: 2010-05-02
Okay, here's a fun question for the technically minded.  It's been a while since I've done anything even close to recursion, and I can't find my uni notes.

I've got a Random Number generator which I want to check if numbers have been called already - I guess kind of like a lottery in some ways.

Now I've got my function:

Public Function RandomNum(iLow As Integer, iHigh As Integer) As Integer
Dim a As Integer

    Randomize
    a = Int(Rnd * (iHigh - iLow)) + iLow

    If Not Already_Called(a) Then
        RandomNum = a
    Else
        RandomNum = RandomNum(iLow, iHigh)
    End If

End Function

Now, the calling line is storing the return number to an array which the Already_Called function checks to see if the number has been called previously and returns true if the number is already found in the number array and false if it isn't.  However, upon Already_Called returning True, my RandomNum function generates an "Out of Stack Space" error message when getting nearer the end of the array when only a finite amount of numbers are left.

Can anyone see anything that I have obviously wrong?  I know that a recursive function needs a close or collapse, which I have, if it's not already generated the number, it returns a, otherwise it keeps calling itself until it generates a number it hasn't already called before.

I guess the problem may be caused by the fact that it is feasible that the random number generator could be generating with an iLow of 1 and an iHigh of 10 and upon reaching the last number never calls the only missing number.  Is there an obvious solution for this other than telling it to go and figure out what the last number that hasn't been called is and just calling that (which in my meagre opinion is a bit of a lame workaround).

Thanks for any help anyone can give me.
0
Comment
Question by:balabaster
  • 3
  • 3
  • 2
  • +2
10 Comments
 
LVL 7

Expert Comment

by:Nitin Sontakke
ID: 7065096
Public Function RandomNum(iLow As Integer, iHigh As Integer) As Integer
Dim a As Integer

   Randomize
   a = Int(Rnd * (iHigh - iLow)) + iLow

   If Not Already_Called(a) Then
       RandomNum = a
       Exit Function  'Try adding this line.
   Else
       RandomNum = RandomNum(iLow, iHigh)
   End If

End Function

I am also not very expert in recursion functions, but if you don't mind, try adding that line. I think it should solve your problem. If not, you have to remove just one line to come back to your original code.

0
 
LVL 7

Expert Comment

by:Nitin Sontakke
ID: 7065097
On second thoughts, it wouldn't matter actually. Your function looks good to me. Have you thoroughly tested your Already_Called functionality on which this function rests?
0
 
LVL 5

Expert Comment

by:Julian_K
ID: 7065103
Hi.
The error you get means in fact, that the func "Already_Called(a)" returns 'TRUE' too many times, forcing the procedure go get deeper and deeper into a recursion until the stack overflows.

So, you can use a simple cycle instead of recursion. Or, If you insist to use recursion, you have to implement some more code. Might be something like this:

Public Function RandomNum(iLow As Integer, iHigh As Integer) As Integer
   
    Dim blnSeekLow As Boolean
    Dim a As Integer
   
    'closes the recursion,
    'if there are no free numbers in this interval.
    If iLow >= iHigh Then
        RandomNum = -1
        Exit Function
    End If
   
    'try to get a random number
    a = Int(Rnd * (iHigh - iLow)) + iLow

    'check if it is acceptable
    If Not Already_Called(a) Then
        RandomNum = a
        Exit Function
    End If
       
    'if not acceptable,
    'decide where to search for other number - higher or lower than this
    blnSeekLow = (Int(Rnd * 2) = 0)
   
    'get random number, excluding a, in one of the directions
    If blnSeekLow Then
        a = RandomNum(iLow, a)
    Else
        a = RandomNum(a + 1, iHigh)
    End If
   
    'if a>=0 means we have a result
    If a >= 0 Then
        RandomNum = a
        Exit Function
    End If
   
    'If a<0 then there is no result. In that case, we search in the other direction
    blnSeekLow = Not blnSeekLow
    If blnSeekLow Then
        a = RandomNum(iLow, a)
    Else
        a = RandomNum(a + 1, iHigh)
    End If
   
    'if both directions return (a<0) then there is no unused number left.
    If a < 0 Then
        Err.Raise vbObjectError + 1, "Random Number Generator", "There are no free numbers left!"
    Else
        RandomNum = a
    End If

End Function

I think there might be easier way to do it, but that was all I could think out right now.

Hope it is usefull.

Julian
0
Free Tool: Postgres Monitoring System

A PHP and Perl based system to collect and display usage statistics from PostgreSQL databases.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

 
LVL 5

Accepted Solution

by:
Julian_K earned 50 total points
ID: 7065105
The idea is that we have to avoid getting a number, which was previously marked as not acceptable by the "Already_Called" function, to minimize the recursion level.
So, when we do recursion, we seek a number, that is higher or lower, but NOT equal to the previous, that was not acceptable. That's it. By the way, when you generate a random number, you use:
a = Int(Rnd * (iHigh - iLow)) + iLow

this returns iLow <= a < (!!!!) iHigh
I mean, you can NEVER get a=iHigh. I'm not sure if this is on purpose, or a bug, but I have coded the previous example to work the same way.
0
 
LVL 100

Expert Comment

by:mlmcc
ID: 7065254
learning
0
 

Author Comment

by:balabaster
ID: 7065771
okay, I've got it...I figured it out around the same time as the last post...iHigh was not ever returning the highest number.

I tried calling my function by using:

Const LOW_COUNT = 1
Const HIGH_COUNT = 10

a = RandomNum(LOW_COUNT, HIGH_COUNT + 1)

This is a workaround, but it does fix the problem.  I'll modify the RandomNum function at some point to account for this, but it was running for the last 24 hours without error, so I am going to run with this for now.

Thanks for your help.
0
 
LVL 7

Expert Comment

by:Nitin Sontakke
ID: 7066395
Please deal with this thread, if your problem now stands solved.
0
 
LVL 5

Expert Comment

by:Julian_K
ID: 7066638

Well, balabaster, It's up to You, but there is a chance to get this error again, If you use your algorythm: It is possible that the (RND) function to return already-called numbers too many times. Especialy if You use a bigger range (not 1 to 10, but say 1 to 1000 or more).

Anyway, if you write this program just for fun, it is not so important.

Best wishes

Julian
0
 

Author Comment

by:balabaster
ID: 7067662
Sorry, guys, I thought I'd already hit "Accept Answer" my apologies.

Consider it Answered
0
 
LVL 18

Expert Comment

by:mdougan
ID: 7070556
You still need to finalize the question by actually accepting a comment as the answer so that it moves the question to the PAQs and awards the points to the Expert.
0

Featured Post

Free Tool: Port Scanner

Check which ports are open to the outside world. Helps make sure that your firewall rules are working as intended.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
String manipulation in Visual Basic 7 73
using Access 8 75
VBS file using code from 2nd file (txt or vbs) 4 42
How to compare ms sql hashbytes results within vb6 5 84
There are many ways to remove duplicate entries in an SQL or Access database. Most make you temporarily insert an ID field, make a temp table and copy data back and forth, and/or are slow. Here is an easy way in VB6 using ADO to remove duplicate row…
Enums (shorthand for ‘enumerations’) are not often used by programmers but they can be quite valuable when they are.  What are they? An Enum is just a type of variable like a string or an Integer, but in this case one that you create that contains…
Get people started with the utilization of class modules. Class modules can be a powerful tool in Microsoft Access. They allow you to create self-contained objects that encapsulate functionality. They can easily hide the complexity of a process from…
This lesson covers basic error handling code in Microsoft Excel using VBA. This is the first lesson in a 3-part series that uses code to loop through an Excel spreadsheet in VBA and then fix errors, taking advantage of error handling code. This l…

861 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question