Recursively convert all keys in a multi-dimensional array to snake_case

I am trying to convert the keys of a multi-dimensional array from camelCase or StudlyCase/PascalCase to snake_case, with the added complication that some keys have a leading exclamation mark that I'd like to be removed.

For example:

$array = array(
  '!AccountNumber' => '00000000',
  'Address' => array(
    '!Line1' => '10 High Street',
    '!line2' => 'London'));

I would like to convert to:

$array = array(
  'account_number' => '00000000',
  'address' => array(
    'line1' => '10 High Street',
    'line2' => 'London'));

My real-life array is huge and goes many levels deep.

This is the modified function I have used, taken from soulmerge's response:

function transformKeys(&$array)
{
  foreach (array_keys($array) as $key):
    # Working with references here to avoid copying the value,
    # since you said your data is quite large.
    $value = &$array[$key];
    unset($array[$key]);
    # This is what you actually want to do with your keys:
    #  - remove exclamation marks at the front
    #  - camelCase to snake_case
    $transformedKey = strtolower(preg_replace('/([a-z])([A-Z])/', '$1_$2', ltrim($key, '!')));
    # Work recursively
    if (is_array($value)) transformKeys($value);
    # Store with new key
    $array[$transformedKey] = $value;      
    # Do not forget to unset references!
    unset($value);
  endforeach;
}