Applied Example II of Recursion in F#

原创：顾远山
著作权归作者所有，转载请标明出处。

递归是一种直接或间接调用自身的计算过程，无关计算机，也无关具体的编程语言，只是递归的嵌套特性不适合人脑计算，通常会借助计算机等工具执行罢了，今时今日几乎所有现代的编程语言都支持递归，本文使用的是函数式编程语言F#。

递归小例（一）中笔者通过Excel列数转列名对递归的应用进行了简示。有偶无独，最近还是处理超大Excel文件过程中，笔者又发现了一个场景， 也可以通过应用递归实现解决方案。

问题描述

把汉字表述的数字转换成阿拉伯数字。

问题分析

对Excel熟悉的同学应该知道，有个函数叫numberstring，可以很方便地把阿拉伯数字转换成汉字表述的数字，比如：

Excel中的numberstring函数

我们的问题正好是Excel中numberstring函数反过来的场景，然而Excel并没有提供现成的函数供大家直接使用。虽然网上也有一堆插件可以完成快速转换，但独立思考加自己动手，是防止少年智障、青年孕傻和老年痴呆的必要操作，建议大家多实践。

动手写码前，最好先分析一下汉字表述的数字都有哪些特点。假设待转换的数字都是简体中文汉字表述的整数（无小数点及小数部分），则该数字可由两种元素组合而成：

• 普通数字，如“五”、“六”、“七”等；
• 量级单位，如“十”、“百”、“千”等。
  其中普通数字可以作为前缀修饰量级单位，比如“五十”、“六百”、“七千”等；量级单位也可以作为前缀修饰量级单位，比如“八千万”、“九万亿”等。根据实际应用，我们不妨约定对于汉字表述的数字，有效的量级单位仅限于：
• 亿
• 万
• 千
• 百
• 十

为了避免不规范的表述，我们可以进一步约定：量级单位能且仅能被小于其自身的量级单位所修饰。比如，“六十万”、“七百亿”和“八千万亿”等，这些都是有效的汉字数字；但“六万十”、“七亿百”和“八亿万千”等，这些并不是有效的汉字数字；甚至类似“三千千”、“四万万”和“五亿亿”这种充满年代感的汉字数字，也被排除在外。

约定好普通数字和量级单位的规则后，问题突然就变得非常简单，我们同样可以直接套用递归的思路求解：

• 欲求整体汉字数字对应的阿拉伯数字，只要先求得“亿”前的汉字数字对应的阿拉伯数字，乘以100000000再加上“亿”后的汉字数字对应的阿拉伯数字即可
• 欲求“亿”前(后)的汉字数字对应的阿拉伯数字，只要先求得“万”前的汉字数字对应的阿拉伯数字，乘以10000再加上“万”后的汉字数字对应的阿拉伯数字即可
• 欲求“万”前(后)的汉字数字对应的阿拉伯数字，只要先求得“千”、“百”、“十”前的汉字数字对应的阿拉伯数字，分别乘以1000、100、10再加上“十”后的汉字数字对应的阿拉伯数字即可
• ……

上面这段文字略显冗长不好理解，我们用符号把它简化一下，其实就是以下过程：

• 转换(整个数字) = 转换((亿前)+亿+(亿后))
• 转换(亿前) = 转换((万前)+万+(万后))
• 转换(万前) = 转换((千前)+千+(百前)+百+(十前)+十+各位数字)
• ……

之所以说它是递归的思路，是因为转换这个过程一直都在一层一层地调用它自己，只是被调用时传入的对象不同罢了。

我们举一个直观的例子，把汉字表述的数字“八千万亿”转换成阿拉伯数字，应用递归的思路计算过程如下：

• 八千万亿 = (八千万) 亿 = (八千万) x 100000000
• 八千万 = (八千) 万 = (八千) x 10000
• 八千 = (八) 千 = (八) x 1000
• 八 = 8

综上，八千万亿 = 8 x 1000 x 10000 x 100000000 = 8000000000000000

换一个例子，从下面的图示可以看得更清楚：

递归的转换思路

分析到此，计算过程无非是：通过递归的方式可以很方便地求出各个量级前对应的数字，乘以量级对应的倍数再求和，便能得到整个汉字数字对应的阿拉伯数字。

逻辑非常直接，但必须小心的是：并非每个汉字数字包含所有量级，中间缺失若干量级是很常见的，比如一千二百零三万就缺失了“亿”及以上所有量级、“十(万)”、“千”、“百”、“十”和个位，而且根据实际情况，汉字数字缺失量级的个数和位置都很灵活，所以准确定位到量级关键字并切分其前后部分相当关键，可以使用正则表达式处理（辅助函数R可参考笔者之前的文章活动模式小例(二)中
RegexMatch活动模式)。

解决方案

我们使用函数式编程语言F#实现。
首先，转换普通数字，如下：

let d v = 
    match "零一二三四五六七八九".ToCharArray() |> Array.tryFindIndex (fun e -> (e|>string)=v) with 
    | Some x -> x |> bigint 
    | None -> -1I

其次，汉字数字去零（“零”在汉字数字中用作缺失量级的补足，需要去掉，避免影响计算逻辑），如下：

let z (s:string) = s.Replace("零","")

最后，结合正则表达式活动模式易得递归的转换函数p，如下：

let rec p c a =
    match z c with
    | "" -> a
    | R "^(.{1,})(亿)(.*)$" [_;v;_;r]-> p r (a + (p v 0I)*100000000I)
    | R "^(.{1,})(万)(.*)$" [_;v;_;r]-> p r (a + (p v 0I)*10000I)
    | R "^(.{1,})(千)(.*)$" [_;v;_;r]-> p r (a + (d v)*1000I)
    | R "^(.{1,})(百)(.*)$" [_;v;_;r]-> p r (a + (d v)*100I)
    | R "^(.{1,})(十)(.*)$" [_;v;_;r]-> p r (a + (d v)*10I)
    | R "^(十)(.*)$"        [_;_;r  ]-> p r (a + 1I*10I)
    | v -> a + (d v)

上述代码中有个特殊处理的逻辑：在汉字数字中“十”前面部分没有数字时等价于“一十”，需要与其他量级单位的匹配模式有所区分。

还有一个有趣的点——例子用到了大数类型，其实用Int64类型也可以，毕竟人最大值为9223372036854775807，远远够用。若要换成Int64类型，那上面的F#的代码中数字的后缀“I”改成“L”即可。

结果验证

随意给定两个测试用例，调用上述转换函数p，如下：

["一千二百三十四万五千六百七十八亿零九万零一";"十六万亿"] |> List.iter (fun e -> printfn "%s:%A" e (p e 0I))

转换结果为：
一千二百三十四万五千六百七十八亿零九万零一: 1234567800090001
十六万亿: 16000000000000

符合预期，测试通过，解决方案可用。

小结

本文通过把汉字表述的数字转换成阿拉伯数字的小例，演示了递归在日常数据处理中的应用。F#作为函数式编程语言，编写递归函数解决问题，不但逻辑清晰，而且简单易读，事半功倍。