递归算法题型总结

{
	"a":"string a",
	"b":"string b",
	"c":get(a),
	"d":get(c)
}

函数 get_value() 用来获取最终值。 例如：get_value(a) 直接返回 string a；get_value(c) 会先查 a，最终返回 string a；get_value(d) 会先查 c 再查 a，最终也返回 string a。

这和递归思想非常接近。对于传入参数 params，get_value 的执行逻辑只有两种：

• 直接返回。例如传入 a，直接返回 string a。
• 依赖更深一层的函数调用。例如传入 b，依赖 get_value(a)。

启发

1. 可以把题目抽象成一个 json 对象：key 是递归函数输入参数，value 是执行逻辑。执行逻辑通常分成两类：直接返回 和 递归调用下一层。对于给定 key，其对应逻辑只取决于该 key（以及必要的全局状态），题目给定后这个映射关系通常就固定了。
2. 如果 value 依赖更深层递归，下一层如何调用要根据函数语义和题意决定。

function get_value(key){
	if(判断 key是否为直接返回类型) return return_value;
	// 下面就是 依赖于更深层次的递归调用

	value= get_value(下一层的key: 根据get_value语义确定)
	// 是否要对返回值做处理
	return value+1; //以加一为例, 可能不是简单的返回 下一层调用的返回值, 可能有操作.
}

对于没有返回值的递归函数，判断当前层属于哪种情况通常更依赖全局状态；下一层调用方式依然要由函数语义决定。

做题总结

• 递归从哪里开始思考？
  • 常从第一个或最后一个位置开始，因为这两个位置受到的约束最少。
  • 例如：打家劫舍可按 灵茶山艾府 的思路，从最后一个位置开始推导。
• 递归可以从本层输入角度和答案角度思考。例如：子集问题，可以判断本层选不选，也可以从答案角度理解为往path中添加元素。但是在求最长公共子序列时，针对输入的选不选显然要比答案角度的共容易转化为动态规划。