继上一篇博客老鼠走迷宫问题的栈实现算法讨论后，在此运用递归对最近在leetcode上遇到的一个problem进行分析，而后结合目前所学对栈实现代码结构及递归结构进行一个小小的对比总结。
Leetcode原题目先附上：17.leetcode：Letter Combinations of a Phone Number
Given a string containing digits from 2-9 inclusive, return all
possible letter combinations that the number could represent.A mapping of digit to letters (just like on the telephone buttons) is
given below. Note that 1 does not map to any letters.
Example:>
Input: “23”
Output: [“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].Note:
Although the above answer is in lexicographical order, your answer
could be in any order you want.
分析：
在此第一阶段有一个digit到字符集String的规则映射，从算法设计角度考虑运用散列思想；因为映射数据边界确定，在此采用ArrayList下标与值的一一对应以自定义模拟HashMap实现高效查找。如在本代码实现中rules.get（9）得到wxyz即为下标9（digit）对应字符集映射为”wxyz”。
本题关键在于从给定不定长digits中得到其中每个digit对应的不定长字符集，在此基础上得到每个digit对应的不定长字符集的单选组合结果。数学上即为一个选取组合枚举问题。由于映射字符集边界的不确定性，故而无法完全按循环结构去完成穷举，结合走迷宫案例，代码主体结构采用递归去完成。突破点为组合结果的每个枚举元素字符长度是可以预先确定的，如在本题中给出digits:”23”，其长度为2，即在结果中的每个元素字符长度皆为2，以此可以得到递归终止条件（当index等于digits.length时即表明一个result收集完成，该递归分支即可结束）。此外在递归执行体中完成digit对应字符集的枚举结果保存及遍历自调以完成横向穷举。
代码实现：
public static List<String> letterCombinations(String digits) {List<String> res=new ArrayList<>();if(digits.length()==0){return res;}List<String> rules=new ArrayList<>(10);//index of rules means number in digits,in this way to formulate pattern of Hash Maprules.add(0,"");//0，1 without charSet maprules.add(1,"");//rules.add(2,new String("abc"));rules.add(3,new String("def"));rules.add(4,new String("ghi"));rules.add(5,new String("jkl"));rules.add(6,new String("mno"));rules.add(7,new String("pqrs"));rules.add(8,new String("tuv"));rules.add(9,new String("wxyz"));char[]re=new char[digits.length()];//save re each otherletterCombinations(digits,rules,0,re,res);return res;}public static void letterCombinations(String digits,List<String> rules, int index,char[]result,List<String> results){//@param: index is which of @param: result, if(index==digits.length()){//save a result to resultsresults.add(new String(result));return ;}int rulesIndex=Integer.parseInt(""+digits.charAt(index));for(int i=0;i<rules.get(rulesIndex).length();i++){//trace every alphabet of digit result[index]=rules.get(rulesIndex).charAt(i);letterCombinations(digits,rules,index+1,result,results);}}
测试结果：
总结：（递归与栈实现的讨论）
此类题目有两种结构去完成穷举：一是自写栈结构实现，另一种是利用递归。
从编程开发效率来考虑当然是利用递归去实现比较好；而从程序运行效率、资源损耗、使用范围来讲还是首选自写栈实现。在此假设一种极端情况：在digit.length=10000的情况下还能用递归实现吗？在程序数据结构复杂的情况下计算机栈深度很难达到10000（记得64位java虚拟机的栈深度可以自定义设置达到大几千到几万。关于计算机栈空间，这篇博客或许有启发作用：Linux虚拟地址空间布局以及进程栈和线程栈总结 ），在假设不受到cpu运算力限制的情况下将看到StackOverflowError，还没得到结果程序便因为栈溢出了而终止了。而在自定义栈的情况下可以在理论范围内实现任意“递归深度”。