Generating unique account numbers - recursive call

Question

Hi i need to generate 9 digit unique account numbers. Here is my pseudocode:

function generateAccNo()

    generate an account number between 100,000,000 and 999,999,999

    if the account number already exists in the DB 
        call generateAccNo()    /* recursive call */
    else
        return new accout number
    end if

end function

The function seems to be working well, however I am a bit worried about the recursive call.

Will this cause any memory leaks (PHP 5 under apache)?

Is this an acceptable way to tackle this problem?

Thanks for your input.

Vaccination

Answer 1

You realize this could very well cause a stack overflow, right? As the number of customesr increases, the probability of not finding a an acceptable account number increases.

Also, why can't you just do sequential account numbers and just increase by one every time? With this approach, you'd just have to read the max id currently in the database and just increment it.

Sorry to be so blunt, but your solution is a terrible way to tackle the problem. It'll use tons of memory (as the stack possibly grows infinitely) and it will makes tons of expensive calls to the database.

You should really consider some other approach:
I strongly recommend just incrementing the customer number every time you create a customer. In fact, if you set up your db properly (with auto increment on the id column), you won't even have to set the id. The id will be set for you whenever you insert a new customer.

Seashore

That would be unlikely. It depends on the randomness of the generated account number and the number of active accounts. With managed code you have to recurse 10s of thousands of times in order to break the stack. When the probability of non-uniqueness approaches 10,000:1, then it's time to worry. – Elide

Thanks Esetban you have talked some sense into me hehe :) I will let the DB create the value for me and stick to sequential numbers instead. Thanks – Ylem

@Eli: Sorry I had to be so blunt, but I just couldn't let you do what several here suggested you do. Glad I could help. – Seashore

Answer 2

I really don't think it comes down to recursion vs. looping, both are prone to problems as the dataset grows and if the random number generation is not correctly implemented. Two ideas come to mind:

. GUID

If a truly unique id is required with as little effort as possible, consider a GUID, your DB will most likely be able to assign on for you on insert, if not create one in code. It is guaranteed to be unique although it is not very user friendly. However, in combination with a sequential AccountRecordId generated by the DB on insert you would have a solid combination

. Composite Key: Random + Sequential

One way to address all the needs, although at the surface it feels a bit kludgy, is to create a composite account number from a sequential db key of 5 digits (or more) and then another 5 digits of randomness. If the random number was duplicated it would not matter as the sequential id would guarantee the uniqueness of the entire account number

Drida

Answer 3

There's no need to use a recursive call here. Run a simple while loop in the function testing against non-existence as the conditional, e.g.

function generateAccNo()

    generate an account number between 100,000,000 and 999,999,999

    while ( the account number already exists in the DB ) {
         generate new account number;
    }
    return new account number

end function

Randomly generating-and-testing is a sub-optimal approach to generating unique account numbers, though, if this code is for anything other than a toy.

Hutchins

WHAT!?! You want to make maybe 899,999,999 db hits just to create an account number? Seems like a bad approach to me. – Seashore

When we do this, we usually use some feature of the database to produce the value, so it is one query instead of O(n). – Leffert

@Eli: Yes, look at my answer just below this one. – Seashore

In my opinion this solution is no better, the stack overflow issue is not a serious concern. Also, hash tables and dictionaries have this exact same problem, perhaps you should investigate those solutions as well (hint, the solutions may seem familiar). – Elide

I frankly agree that random generation with collision testing is a bad idea -- see my post-script -- but it's a bad idea independent of the bad idea that is needless recursion. – Hutchins

@Josh: Sorry Josh, I didn't see your postscript. I'm glad you're not insane! ;) – Seashore

You and me both! Now if you'll excuse me, I've got to take a phone call from a very important moose. – Hutchins

Answer 4

It seems fine, but I think you need some sort of die condition, how many times are you going to let this run before you give up?

I know this seems unlikely with the huge number range, but something could go wrong that just drops you back to the previous call, which will call itself again, ad-nauseum.

Malines

Answer 5

Generating account numbers sequentially is a security risk - you should find some other algorithm to do it.

Touraco

Only if you don't hash them whenever you use them. – Seashore

Answer 6

Alternately, you can maintain a separate table containing a buffer of generated, known to be unique account numbers. This table should have an auto-incrementing integer id. When you want an account number, simply pull the record with the lowest index in the buffer and remove it from that table. Have some process that runs regularly which replenishes the buffer and makes sure it has capacity >> normal usage. The advantage is that the amount of time experienced by the end user spent creating an account number will be essentially constant.

Also, I should note that the processing overhead or risks of recursion or iteration, the real issue is determinism and the overhead of repeating database queries. I like TheZenker's solution of random + sequential. Guaranteed to generate a unique id without adding unnecessary overhead.

Elide

Surprised this doesn't have more upvotes. Generating account numbers on demand, at runtime, is not a good plan, recursion or no. Write a loop to generate a million numbers sequentially based on your account number pattern, shuffle them, store them, and call it a day. – Hannon

Answer 7

You do not need to use recursion here. A simple loop would be just as fast and consume less stack space.

Split

Answer 8

You could put it in a while loop:

function generateAccNo()

    while (true) {    

      generate an account number between 100,000,000 and 999,999,999

      if the account number already exists in the DB 
          /* do nothing */
      else
          return new accout number
      end if
    }

end function

Weylin

Answer 9

Why not:

lock_db
do
    account_num <= generate number
while account_num in db

put row with account_num in db

unlock_db

Convene

Answer 10

Why not have the database handle this? IN SQL Server, you can just have an identity column that starts at 100000000. Or you could use sql in whatever db that you have. Just get the max id plus 1.

Epencephalon

I would like to have random looking account numbers instead of sequential. – Ylem