PHP function returns wrong result [was: I am really confused]

I am working on the navigation for a messaging system I creating. This is the code that I am having problems with:

function getPreviousMessageID($mid) {
      global $connection;
      $message_sets = getMessageID("first");
      $messages = mysql_fetch_assoc($message_sets);
      if($mid < $messages['id']) {
            $mid++;
            $sql = "SELECT *
              FROM messages
              WHERE id = {$mid}
              LIMIT 1";
            $message_set = mysql_query($sql, $connection);
            $message = mysql_fetch_assoc($message_set);
            if(!empty($message)) {
                  return $message['id'];
            } else {
                  if($mid < $messages['id']) {
                        getPreviousMessageID($mid);
                  } else {
                        return 0;
                  }
            }
      } else {
            return 0;
      }
}

function getNextMessageID($mid) {
      global $connection;
      $message_sets = getMessageID("last");
      $messages = mysql_fetch_assoc($message_sets);
      if($mid > $messages['id']) {
            $mid--;
            $sql = "SELECT *
              FROM messages
              WHERE id = {$mid}
              LIMIT 1";
            $message_set = mysql_query($sql, $connection);
            $message = mysql_fetch_assoc($message_set);
            if(!empty($message)) {

                  return $message['id'];
            } else {
                  if($mid > 1) {
                        getNextMessageID($mid);
                  } else {
                        return 0;
                  }
            }
      } else {
            return 0;
      }
}

I don't know why this would be, but it seems these functions only work properly if they return a value that is directly next to the one that is originally put into the function. Otherwise, they return empty. I have previously told the functions to echo $message['id']. That works fine and echoes the id that it should. However, if that id is not directly next to the one that was originally input, it will return empty. I don't know if the function isn't returning the value it's supposed to or if the variable that is supposed to catch the returned variable isn't catching it. I find it to be kind of odd that it only works part of the time. If you found the above to be a bit confusing, let me give an example:

I have 3 rows in the messages table. They have the ids of 4, 7, and 8. If 8 is put into the functions, getNextMessageID returns 7 and getPreviousMessageID returns 0. That is what you would expect. Now, if you put 7 into the functions, getPreviousMessageID returns 8. That's what should happen, but getNextMessageID returns completely empty. It doesn't even return 0. Yet, when I echo $message['id'] in the getNextMessageID, it says 4, which is what you would expect to happen. Now, if 4 is put into the functions, getNextMessageID returns 0. That's what should happen. The getPreviousMessageID functions, however, returns completely empty. When I echo $message['id'] in the getPreviousMessageID function, it says 7. That's what it should say.

I am really confused. These functions only work part of the time. The rest of the time, the value is getting lost somewhere. Does anybody have any idea as to why this is happening or a possible fix? Thank you in advance for looking at my code.