递归
目录
简介
一个函数反复地调用自己就是递归。一般定义一个递归函数有两个步骤，一个是确定递归基，第二就是找到递归关系。一般介绍递归的文章都会从“斐波那契数列”和”A!的计算“开始讲起，稍微深入一点会讲到“汉诺塔问题”和“八皇后问题”。然后会讲讲递归的时间复杂度和空间复杂度问题。通过递归追踪会发现大量的递归调用栈重复调用，接着提出改进的方法，比如记忆化数组等等。为了进一步减小时间复杂度，部分递归问题还可以转化为动态规划问题。最后会总结一下递归的一般特点：程序简单，容易理解和编写。缺点：时间复杂度和空间复杂度高。
一般而言的确如此。一般而言递归都可以和迭代方法相互转换，而且一般迭代的方法效率会更好。不过如果精心设计的话，递归的效率也会很高，比如归并排序，快速排序，还有就是在二叉树中有许多问题，用递归写不仅表意清楚，而且算法的效率也比迭代高，比如最基本的遍历，还有二叉搜索树的一些方法等等（或者换一种说法，就是对于可以指向自身的数据结构，如链表，二叉树的节点，N叉树的结点等等）
递归算法的一般形式
func(){
if some case:
return ;
else{
do something:
func();
}
}
递归与迭代
递归就是反复的自身调用，得到的中间结果可以放在调用过程中不会销毁的变量中或者通过返回值来反馈。而迭代就是循环，中间结果就放在已经定义好的变量中。举个栗子，输出斐波那契数列的第n项:
//基于Java 实现
// 递归
public void int fib(int n){
if( n == 0 || n == 1){
return n;
}
else{
return fib(n - 1) + fib(n - 2);
}
}
//迭代
public void int fib(int n ){
int[] res = new int[n + 1];
res[0] = 0;
res[1] = 1;
for(int i = 2; i <= n; i++){
res[i] = res[i - 2] + res[i - 1];
}
return res[n];
}
// 空间复杂度其实还可以进一步优化为O(1);
递归与二叉树
二叉树的遍历用递归来写将会十分的流畅。
// 前序遍历
class Solution {
private List<Integer> myList = new LinkedList<Integer>();
public List<Integer> preorderTraversal(TreeNode root) {
if(root == null){
return myList;
}
myList.add(root.val);
if(root.left != null) preorderTraversal(root.left);
if(root.right != null) preorderTraversal(root.right);
return myList;
}
}
//中序遍历
class Solution {
private List<Integer> myList = new LinkedList<Integer>();
public List<Integer> inorderTraversal(TreeNode root) {
if(root == null) return myList;
if(root.left != null) inorderTraversal(root.left);
myList.add(root.val);
if(root.right != null) inorderTraversal(root.right);
return myList;
}
}
//后序遍历
class Solution {
List<Integer> myList = new LinkedList<Integer>();
public List<Integer> postorderTraversal(TreeNode root) {
if(root == null) return myList;
if(root.left != null) postorderTraversal(root.left);
if(root.right != null) postorderTraversal(root.right);
myList.add(root.val);
return myList;
}
}
当然也可以通过栈这种数据结构来代替递归，只不过实现起来就麻烦一点。
// 前序遍历
public List<Integer> preorderTraversal(TreeNode root) {
Stack<TreeNode> st = new Stack<TreeNode>();
List<Integer> myList = new LinkedList<Integer>();
if(root == null) return myList;
st.push(root);
while(!st.empty()){
TreeNode tmpNode = st.pop();
myList.add(tmpNode.val);
if(tmpNode.right!= null){
st.push(tmpNode.right);
}
if(tmpNode.left != null){
st.push(tmpNode.left);
}
}
return myList;
}
//中序遍历
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> ans = new LinkedList<>();
Stack<TreeNode> st = new Stack<>();
if(root == null) return ans;
TreeNode tmp = root;
while(tmp != null || !st.empty()){
while(tmp != null){
st.push(tmp);
tmp = tmp.left;
}
tmp = st.pop();
ans.add(tmp.val);
tmp = tmp.right;
}
return ans;
}
//后续遍历
public List<Integer> postorderTraversal(TreeNode root) {
Stack<TreeNode> s1 = new Stack<TreeNode>();
Stack<TreeNode> s2 = new Stack<TreeNode>();
List<Integer> myList = new LinkedList<Integer>();
if(root == null ) return myList;
TreeNode tmpNode = root;
s1.push(root);
while(!s1.empty())
{
tmpNode = s1.pop();
s2.push(tmpNode);
if(tmpNode.left != null) s1.push(tmpNode.left);
if(tmpNode.right != null) s1.push(tmpNode.right);
}
while(!s2.empty())
{
tmpNode = s2.pop();
myList.add(tmpNode.val);
}
return myList;
}
在二叉搜索搜索树中，插入和删除是比较难实现的，不过借助递归将大大减小显示的难度（时间复杂度并不比其他的方法高）
//insert
public TreeNode insertIntoBST(TreeNode root, int val) {
if(root == null) return new TreeNode(val);
if(val < root.val) root.left = insertIntoBST(root.left, val);
else if (val > root.val) root.right = insertIntoBST(root.right, val);
else x.val = val;
return root;
}
}
// delete
public TreeNode deleteNode(TreeNode root, int key) {
if(root == null ) return null;
if(key < root.val) root.left = deleteNode(root.left, key);
else if( key > root.val) root.right = deleteNode(root.right, key);
else{
if(root.right == null) return root.left;
if(root.left == null) return root.right;
TreeNode t = root;
root = min(t.right);
root.right = deleteMin(t.right);
root.left = t.left;
}
return root;
}
private TreeNode min(TreeNode root){
if(root.left == null) return root;
else return min(root.left);
}
private TreeNode deleteMin(TreeNode x){
if(x.left == null ) return x.right;
x.left = deleteMin(x.left);
return x;
}
二叉平衡树的判断也是一个优雅的递归算法的例子
public boolean isValidBST(TreeNode root) {
if(root == null ) return true;
return valid(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
private boolean valid(TreeNode root, long min, long max){
if( root == null) return true;
if(root.val <= min || root.val >= max) return false;
return valid(root.left, min, root.val) && valid(root.right, root.val,max);
}
总之，递归程序并不一定简单编写，也不一定都拥有较高的复杂度。巧妙的利用递归，可以达到性能和易读性的兼顾。当然，一些迭代程序本来就很简单实现的，就不必使用递归了。