I'm stumped on telephone numbers to characters interview question

See more:

C#

During an interview I was asked how I would list every character conversion of a ten digit telephone number. I figured that at most there were 3^10 combinations, then he mentioned 9 has 4 characters, OK, so at most 4 to the 10'th. I said it could be done with a loop in loop process, but I'd probably use a recursive loop to do it. It's a phone interview, little hard to describe exactly how I'd do it and I'd just been presented the problem. Instead of 10 digits use a variable set of numbers (Kills loop in loop unless a lot more logic is added.) and you can't do recursive logic. So, a trick question, and I don't know the trick answer. OK, does anyone know the process for doing that? Can you come up with a better process than the one I came up with? (Including recursive) I haven't counted breaking up the numbers into words (breaking up into words with 0 or 1.) He did ask about recognizing words in the list of solutions. (A little beyond my skill level. He was OK with that.)

In the mean time, I wrote the recursive logic to handle digits from 1 to 19 numbers. A few numbers for the number of possible results:
3^10=59049, 4^10=1048576, (Oh yea, that'd be 2^20, no wonder that number was familiar.) 3^19=1162261467, 4^19=274877906944

I may or may not be able to handle 3^19 in memory, I'd rather not find out.

/// <summary>
/// Provide a decimal value, Convert the decimal values to characters from a phone keypad.
/// Supply a list of all character combinations of those values.
/// </summary>
/// <param name="telnum">The decimal value to convert</param>
/// <returns>list of strings the value supplied can be converted</returns>
public static List<string> TeleWords(UInt64 telnum)
{
    List<string> strlst = new List<string>();
    if (telnum==0) return strlst;
    string[] phon = {" "};
    Dictionary<int, string> phones = new Dictionary<int, string>();
    Dictionary<int, string[]> phone = new Dictionary<int, string[]>();
    phone.Add(0, phon);   phone.Add(1, phon);
    phones.Add(2, "abc"); phones.Add(3, "def"); phones.Add(4, "ghi"); phones.Add(5, "jkl");
    phones.Add(6, "mno"); phones.Add(7, "pqrs"); phones.Add(8, "tuv"); phones.Add(9, "wxyz");
    foreach (int num in phones.Keys)
    {
        phon = new string[phones[num].Length];
        for (int i = 0; i < phones[num].Length; i++)
            phon[i] = phones[num].Substring(i, 1);
        phone.Add(num, phon);
    }
    List<int> nums = new List<int>();
    UInt64 tmx = telnum;
    tmx /= 10;
    tmx *= 10;
    //nums adds digits from right to left
    while (telnum > 0)
    {
        int ii = (int)(telnum - tmx);// removed remainer % 10
        nums.Add(ii);
        telnum /= 10;
        tmx /= 100;
        tmx *= 10;
    }
    int x = nums.Count-1;
    int[] lst = new int[nums.Count];
    //Convert right to left to left to right on the numbers used while creating int[] list
    for (int i = 0; i <= x; i++)
        lst[i] = nums[x - i];
    //start the recursive routine at the beginning with the first number on the left
    TeleWords(strlst, 0, lst, new StringBuilder(), phone);
    return strlst;
}

/// <summary>
/// private supplier for TeleWords(UInt64 telnum) list of words
/// A recursive routine to create a list of words from digit to string conversion
/// </summary>
/// <param name="strlst">TeleWords(UInt64 telnum) supplied pointer, filled by this routine</param>
/// <param name="pos">Which of the nmbrs to recursively process</param>
/// <param name="nmbrs">TeleWords(UInt64 telnum) converted telnum values</param>
/// <param name="lst">The characters converted from the supplied nmbrs list</param>
/// <param name="phoneLtrs">Definition of the single letters used for digits 0-9</param>
private static void TeleWords(List<string> strlst, int pos, int[] nmbrs, StringBuilder lst, Dictionary<int, string[]> phoneLtrs)
{
    if (pos >= nmbrs.Length)
    {
        strlst.Add(lst.ToString());
        return;
    }
    StringBuilder nlst = new StringBuilder();
    int l = nmbrs.Length;
    if (pos > 0) nlst.Append(lst.ToString());
    foreach (string x in phoneLtrs[nmbrs[pos]])
    {
        nlst.Append(x);
        TeleWords(strlst, pos + 1, nmbrs, nlst, phoneLtrs);
        nlst.Remove(lst.Length, x.Length);
    }
}