Applied Example I of Recursion in F#
原創(chuàng)：顧遠(yuǎn)山
著作權(quán)歸作者所有，轉(zhuǎn)載請(qǐng)標(biāo)明出處鹏控。
遞歸是一種直接或間接調(diào)用自身的計(jì)算過程致扯，無關(guān)計(jì)算機(jī)，也無關(guān)具體的編程語言当辐，只是遞歸的嵌套特性不適合人腦計(jì)算抖僵，通常會(huì)借助計(jì)算機(jī)等工具執(zhí)行罷了，今時(shí)今日幾乎所有現(xiàn)代的編程語言都支持遞歸缘揪，本文使用的是函數(shù)式編程語言F#耍群。
提到遞歸，教科書里繞不過的頭牌絕對(duì)是求解斐波那契數(shù)列問題找筝，可謂是最爛大街的例子蹈垢，更多的例子包括但不限于：
從前有座山，山上有座廟袖裕，廟里有個(gè)和尚曹抬，在講故事：“從前有座山，山上有座廟陆赋，廟里有個(gè)和尚沐祷，在講故事：“……””
對(duì)著鏡子里照鏡子嚷闭，鏡子里有鏡子，鏡子里的鏡子還有鏡子……
漢諾塔問題赖临，三根柱子移盤子……
這些例子雖然直觀形象胞锰，但總感覺少了點(diǎn)接地氣的實(shí)用性。筆者近日在處理一個(gè)超大Excel文件時(shí)遇到的某個(gè)小場景兢榨，亦可用遞歸思路求解嗅榕，遂分享之。
問題描述
把Excel的任意列數(shù)轉(zhuǎn)換成列名吵聪，若第0列對(duì)應(yīng)列'A'凌那，求第n列對(duì)應(yīng)的列名。
問題分析
眾所周知吟逝，Excel中的列名并不是阿拉伯?dāng)?shù)字帽蝶，而是從'A'開始逐個(gè)（位）遞增的字符串，所以我們需要考慮的無非就是“無需進(jìn)位”和“需要進(jìn)位”兩種情況块攒，而進(jìn)位無非也就是前一位字符也相應(yīng)遞增罷了励稳。
進(jìn)位的情況非常適合應(yīng)用遞歸處理，如下圖所示：
欲對(duì)'ZZZZ'進(jìn)行遞增囱井，除了最后一位的'Z'需要遞增成'A'之外驹尼，還需要應(yīng)用同樣的計(jì)算過程對(duì)前三位'ZZZ'進(jìn)行遞增，以此類推庞呕，遞歸到最前面一位新翎，問題就解決了。
另外字符的遞增（從'A'到'B'到……'Z'）相對(duì)別扭住练，我們可以用等價(jià)數(shù)字進(jìn)行計(jì)算地啰，算完后再換成字符。
解決方案
我們不妨約定用0到25作為等價(jià)數(shù)字代表字符'A'到'Z'澎羞，易得純數(shù)字轉(zhuǎn)換函數(shù)如下：
let rec c i a =
match i / 26, i % 26 with
| 0, r -> r :: a //無需進(jìn)位
| q, r -> c (q - 1) (r :: a) //需要進(jìn)位
特別值得留意的是髓绽，進(jìn)位時(shí)上步計(jì)算得到的商被傳入轉(zhuǎn)換函數(shù)前需轉(zhuǎn)換成0基的新列數(shù)（減一敛苇，而不是加一）妆绞。比如說，列數(shù)27枫攀，上步計(jì)算得到商1括饶，此步是新計(jì)算從0開始，上步的1需要等價(jià)為此步的0来涨，故減一图焰。
然后我們把0到25轉(zhuǎn)換成'A'到'Z'，最后歸約字符串就完成了蹦掐，如下：
let n i= [] |> c i |> List.map (fun e -> e + 65 |> char |> string) |> List.reduce (+)
結(jié)果驗(yàn)證
結(jié)果符合預(yù)期技羔，解決方案驗(yàn)證通過僵闯。
小結(jié)
本文通過Excel列數(shù)轉(zhuǎn)列名的小例，演示了遞歸在日常數(shù)據(jù)處理中的應(yīng)用藤滥。F#作為函數(shù)式編程語言鳖粟，其列表類型內(nèi)建支持遞歸，使用模式匹配解決此類問題不但思路清晰拙绊，而且程序簡潔向图，事半功倍。
