递归
递归是一种解决问题的有效方法，在递归过程中，函数将自身作为子例程调用.
为了确保递归函数不会导致无限循环，它应具有以下属性：
1. 有终止条件。
2. 一组规则，也称作递推关系（recurrence relation），可将所有其他情况拆分到基本案例。
通常情况下，递归是一种直观而有效的实现算法的方法。但是中间可能会出现重复的计算结果，可以用哈希map存储中间结果，减少重复计算。
经典的斐波那契数，递归通过hashMap减少中间重复计算，提高了时间效率。很好的用空间换时间。
class Solution { Mapint result = fib(n-1) + fib(n-2); valueMap.put(n, result); return result; } }
类似的还有爬楼梯问题：
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
class Solution { HashMapif(map.containsKey(n)) { return map.get(n); }
int result = climbStairs(n - 2) + climbStairs(n - 1); map.put(n, result); return result; } }
1. 括号生成：
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例：
输入：n = 3
输出：[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
通过次数
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/generate-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
if(left > 0) { generate(item + "(", left - 1, right, result); }
if(right > left) { generate(item + ")", left, right - 1, result); } } }
2. 有效的括号字符串
给定一个只包含三种字符的字符串：（ ，） 和 *，写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则：
任何左括号 ( 必须有相应的右括号 )。
任何右括号 ) 必须有相应的左括号 ( 。
左括号 ( 必须在对应的右括号之前 )。
* 可以被视为单个右括号 ) ，或单个左括号 ( ，或一个空字符串。
一个空字符串也被视为有效字符串。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-parenthesis-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路：用两个栈进行存储，一个存储左括号，一个存储星号。碰到右括号，优先弹出左括号，左括号栈没有则去星号栈弹出，都没有则返回false。最后判断左括号栈和星号栈是否匹配。
class Solution { public boolean checkValidString(String s) { ArrayDequefor(int i = 0; i < s.length(); i++) { char ch = s.charAt(i); switch(ch) { case '(' : stack.push(i); break; case ')' : if(!stack.isEmpty()) { stack.pop(); } else if(!starStack.isEmpty()) { starStack.pop(); } else { return false; }
break; case '*' : starStack.push(i); } }
if(stack.size() > starStack.size()) { return false; } while(!stack.isEmpty() && !starStack.isEmpty()) { //左括号的索引比*号大则无法组成有效括号。 if(stack.pop() > starStack.pop()) { return false; } }
return true; } }