How to call a function inside itself?

Question

I have a function that generates a key of 4 characters that has to be unique for each time. In order to do that, the function first generates a key, and then checks a database table to see if it's in use by someone else.

If it's not in use, it returns the key, else, it calls itself again, but this causes the function to do an infinite loop, which is a no-no. Here's the whole function:

function key_generator($length = 4)
{
    // I've subsequently left out the generating code,
    // which is not necesarry in this case

    $key = 'xxxx';

    if ($this->user_model->valid_key($key) == true)
    {
        return $key;
    }
    else
    {
        $this->key_generator(4);
    }
}

What is the correct way to call the function again?

By the way, I'm using CodeIgniter, hence $this.

Answer 1

You could put your code into a loop and determine the key iteratively instead of recursively.

Example:

function key_generator($length = 4)
{
  do {
    $key = 'xxxx'; //TODO
    if (timeOutReached()) return InvalidKey;
  } while (!$this->user_model->valid_key($key))

  return $key;
}

The loop itself does not prevent an infinte loop, but unlike a function call, this doesn't eat up stack space, so you don't risk a stack overflow.

Also it simplifies things a little bit. Depending on the type of the key you can also adapt the key generation method, for example with numbered keys you can increase exponentially with each iteration.

Remarks: If it is possible, use a database's auto-increment feature instead of rolling your own key generation feature.

Also make sure you protect your code against concurrent access. What if two instances of this function try to generate a key and they both determine the same? Use critical sections or transactions to make sure nothing bad happens.

Answer 2

but this causes the function to do an infinite loop,

If you absolutely want to keep your recursive strategy you have to define an end case. For example you may define a counter, like this:

function key_generator($length = 4, $limit=5)
{
    if($limit === 0) {
         throw new YourException();
    }

    // I've subsequently left out the generating code,
    // which is not necesarry in this case

    $key = 'xxxx';

    if ($this->user_model->valid_key($key) == true)
    {
        return $key;
    }
    else
    {
        return $this->key_generator(4, ($limit-1));
    }
}

It is however also possible to do your code iteratively...

Answer 3

I would not use recursive functions for retry-scenarios (since you don't reuse the result of the function, it's pointless to use recursion)... It adds a lot of unnecessary overhead. Do something like this:

do {
    $key = ...; // Generate your key here...
} while (!$this->user_model->valid_key($key));

return $key;

If you're near the maximum number of keys, this will result in very long loop times, so you might want to put some kind of max limit.

Oh, and if this is occurring on multiple threads simultaneously and you're checking a database, you should implement table write locking so that the same key can't be inserted twice. Preferably the function that checks whether a key is available should lock, check, and if available write in the same transaction to avoid any collisions.

Answer 4

You need to return the result of the self-call, otherwise the valid key won't get returned once it recurses.

return $this->key_generator($length);

Answer 5

If you include enough uniqueness in your key generation routine, you might be able to avoid this situation in the first place. E.g. have the routine take into account the current timestamp and the local hostname and/or PID.

Looping in such a non-deterministic fashion is generally proof of some part being too naive. That's not good. :-)

---

Anyhow, it would at least be good practice to catch it and log some sort of error as opposed to hanging the request and finally timing out:

    function key_generator($length = 4)
    {
        /* The $attempts_left clearly depends on how much trust 
           you give your key generation code combined with the key space size. */
        $attempts_left = pow(16, $length) * 2;
        /* ... just guessing, in case your key base is 16, i.e. [0-9a-z] for example */

        do {
            // ... key generation goes here ...
            $key = 'xxxx';
        } while ( $this->user_model->valid_key($key) == false && $attempts_left-- > 0 );

        if( $attempts_left < 1 )
            return false;
        else
            return $key;
    }

Answer 6

Why don't you just scan the key value space for the first unused key? Needs the key to fulfill additional constraints on top of being four characters long and unique?

You could remember the last returned key to resume scanning from there on subsequent calls.

If you want subsequent calls not to return similar keys, you could shuffle your key database first. This would mean that you need to hold a 456976, 1679616, 7311616, or 14776336 element array somewhere (depending on whether the alphabet used are single- or double-cased characters, with or without digits).