为何Memoization未能加速整数转英文单词的递归程序？

根本原因：递归逻辑无重复计算 #

你当前的递归是按数位层级拆分数字，比如处理123456789时，会拆成123*1000000 + 456789，再分别处理123和456789，每个子问题的num参数都是唯一的，几乎不会出现同一个数字被多次计算的情况。Memoization的核心是缓存重复计算的结果，这里没有重复计算，加了字典缓存反而多了读写开销，自然性能没提升甚至更慢。

你的Memoization实现有冗余操作 #

带缓存的代码里，先调用ContainsKey再调用TryGetValue是重复查询，TryGetValue本身就能判断键是否存在，可以简化：

// 原冗余代码
if (memoizationDictionary.ContainsKey(num))
{
    if( memoizationDictionary.TryGetValue(num, out var memoizedResult))
    {
        return memoizedResult;
    }
}

// 优化后
if (memoizationDictionary.TryGetValue(num, out var memoizedResult))
{
    return memoizedResult;
}

额外小问题 #

tens数组里的"Fourty"是拼写错误，正确应为"Forty"。

带Memoization的代码 #

Dictionary<long, string> memoizationDictionary = new Dictionary<long, string>();

string[] lessThanTwentyWords = new string[] { "","One","Two", "Three", "Four", "Five", "Six",
                                              "Seven","Eight","Nine", "Ten","Eleven","Twelve",
                                              "Thirteen","Fourteen","Fifteen","Sixteen",
                                              "Seventeen","Eighteen","Nineteen"
                                        };

string[] tens = new string[] { "", "Ten", "Twenty", "Thirty", "Fourty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety" };

string ConvertNumsToWords(long num, string[] lessThanTwentyWords, string[] tens)
{
    long result = 1;
    long rem = 0;

    // Check if the result is already memoized
    if (memoizationDictionary.ContainsKey(num))
    {
        if( memoizationDictionary.TryGetValue(num, out var memoizedResult))
        {
            return memoizedResult;
        }
    }

    if (num == 0)
        return "";

    if (num >= 1 && num < 20)
    {
        memoizationDictionary[num] = lessThanTwentyWords[num];
        return memoizationDictionary[num];
    }

    if ((num / 1000000000) > 0)
    {
        rem = num % 1000000000;
        result = num / 1000000000;

        memoizationDictionary[num] = ConvertNumsToWords(result, lessThanTwentyWords, tens) + " " + "Billion" + 
                                     (rem !=0 ? (" " + ConvertNumsToWords(rem, lessThanTwentyWords, tens)) : "");
        return memoizationDictionary[num];
    }

    if ((num / 1000000) > 0)
    {
        rem = num % 1000000;
        result = num/1000000;

        memoizationDictionary[num] = ConvertNumsToWords(result, lessThanTwentyWords, tens) + " " + "Million" + 
                                     (rem != 0 ? (" " + ConvertNumsToWords(rem, lessThanTwentyWords, tens)) : "");
        return memoizationDictionary[num];
    }

    if ((num / 1000) > 0)
    {
        rem = num % 1000;
        result = num/ 1000;

        memoizationDictionary[num] = ConvertNumsToWords(result, lessThanTwentyWords, tens) + " " +"Thousand" + 
                                     (rem !=0 ? (" " + ConvertNumsToWords(rem, lessThanTwentyWords, tens)) : "");
        return memoizationDictionary[num];
    }

    if ((num / 100) > 0)
    {
        rem = num % 100;
        result = num/100;

        memoizationDictionary[num] = ConvertNumsToWords(result, lessThanTwentyWords, tens) + " " + "Hundred" + 
                                     (rem !=0 ? (" " + ConvertNumsToWords(rem, lessThanTwentyWords, tens)) : "");
        return memoizationDictionary[num];
    }
    else
    {
        if (num >= 20)
        {
            memoizationDictionary[num] = tens[num / 10] + (num % 10 != 0 ? (" " + lessThanTwentyWords[num % 10]) : "");
            return memoizationDictionary[num];
        }
        return "";
    }    
}

普通递归代码 #

string ConvertNumsToWords(long num, string[] lessThanTwentyWords, string[] tens)
{
    long result = 1;
    long rem = 0;

    if (num == 0)
        return "";

    if (num >= 1 && num < 20)
        return lessThanTwentyWords[num];

    if ((num / 1000000000) > 0)
    {
        rem = num % 1000000000;
        result = num / 1000000000;

        return ConvertNumsToWords(result, lessThanTwentyWords, tens) + " " + "Billion" + (rem !=0 ? (" " + ConvertNumsToWords(rem, lessThanTwentyWords, tens)) : "");
    }

    if ((num / 1000000) > 0)
    {
        rem = num % 1000000;
        result = num/1000000;

        return ConvertNumsToWords(result, lessThanTwentyWords, tens) + " " + "Million" + (rem != 0 ? (" " + ConvertNumsToWords(rem, lessThanTwentyWords, tens)) : "");        
    }

    if ((num / 1000) > 0)
    {
        rem = num % 1000;
        result = num/ 1000;

        return ConvertNumsToWords(result, lessThanTwentyWords, tens) + " " +"Thousand" + (rem !=0 ? (" " + ConvertNumsToWords(rem, lessThanTwentyWords, tens)) : "");
    }

    if ((num / 100) > 0)
    {
        rem = num % 100;
        result = num/100;

        return ConvertNumsToWords(result, lessThanTwentyWords, tens) + " " + "Hundred" + (rem !=0 ? (" " + ConvertNumsToWords(rem, lessThanTwentyWords, tens)) : "");
    }
    else
    {
        if (num >= 20)
        {            
            return tens[num / 10] + (num % 10 != 0 ? (" " + lessThanTwentyWords[num % 10]) : "");
        }
        return "";
    }    
}

内容的提问来源于stack exchange，提问作者Usman