递归与回溯算法

algorithm

0.递归算法介绍

• 递归的含义
• 递归就是通过把问题分解成更小的问题，认为是一个子问题，并通过调用自身解决问题的过程
• 举例说明

1.阶乘的计算

n! = n*(n-1)*(n-2)...(1)

上面是阶乘的定义：

• 我们把问题抽象成一个函数，假设问题可以这么定义
  

  $$f(n) = n!$$

• 那么通过变形，我们可以得到：

• 可以看出来，我们把一个大的问题求$f(n)$， 分解成一个小的问题求$f(n-1)$的，也可以理解，如果我知道$f(n-1)$的值，那么我就能够解决这个$f(n)$的问题了。

• 所有的递归问题，我们都可以假设我们已经有方法求出更小的问题直接定义出来$f(n)$，也就是说，我们在思考的过程当中是，先假设我们能够解决规模较小的问题，然后，再来思考更大的问题，我们该怎么解决。

• 上面的阶乘问题就是这个样子，思考的方式需要改变

(1).让我求f(n)，->>>>
(2).我就直接假设我已经能够有这个能力了f(n)定义出来 ->>>> 
(3).f(n) 什么时候能够直接得到问题的答案，也就是递归的出口 --->>>>> 这个就是递归调用函数的需要return的地方
(4).组合一下更小规模情况下f(n-1)和f(n)的关系，阶乘函数是n*f(n-1)的关系 ->>>> 

public static void main(String []args) {
    int n = 5;
    System.out.println("5! = " + factorial(n));
}
public static int factorial(int n) {
    /* (1).最为基本的情况，也就是说，这个问题已经不能再小了，我已经知道怎么解决了。所有的递归都需要有明确的返回，
        * (2).只有在最基本的情况下返回，递归才不会无线循环下去，因为递归是调用自己的。
        */
    if (n <= 0 )
        return 1;
    else {
        /* (1).一个规模小的问题，和当前的问题的关系是什么
            * (2).这里阶乘的计算是 n*f(n-1)的关系
            * (3).如果是求和，那么是 n + f(n-1)的关系
            */
        return n * factorial(n-1);
    }
}

• 类似的如果求n+(n-1) + (n-2) + ... 1 的值，我们需要把代码中的

n*f(n-1) ->>>>> n + f(n-1)即可

1.1 举例说明递归时如何调用的

• 递归的最为典型的例子，就是树这种数据结构。本身是一个递归的定义，一个树节点，包含其他的树，这里我们以常用的二叉树为例
• 首先就是要假设我们已经能够解决这个问题了，把一个节点的遍历函数定义出来，先定义出来不管实现
• 假设遍历的函数为preOrder,那么，我给一个节点，我首先遍历这个节点，然后对于他的左子树和右子树，分别遍历preOrder(left),preOrder(right),那么我们就完成遍历了
• 现在是组合两个子问题的结果了，这里和上面的阶乘算法一样，我们是要遍历节点，所以我们按照顺序遍历左右子树就可以了。
• 想一下如果我们先遍历右子树，后左子树，那么就是另一种结果了，所以可以根据组合的方式来实现不同的目标。
• 同时，我们把访问函数visited 放在左右子树遍历当中或者之后，就是不同的遍历树的方式，分别为中序遍历、后序遍历

class TreeNode {
    int v;
    TreeNode left,right;
}
public static void preOrder(TreeNode root) {
    if (root == null){ // 一颗空树，最基本的情况，什么时候不需要在递归了
        return ;
    }
    visited(root); //   1: 访问节点
    preOrder(root.left);//2 访问左子树节点
    preOrder(root.right);//3 访问右子树的节点
}
public static void visited(TreeNode node) {
    System.out.println(node.v);
}

1.3 树遍历的扩展

• 上面的遍历情况，只是打印了节点内容
• 比如说你想统计树中节点的个数
• 或者，想要把树中的所有值都加1，并求和
• 这些情况都可以放在visited这个函数里面去做

public class Solution{
    public static nodeCount = 0;
    public static void main(String[] args){
        TreeNode root = new TreeNode();
        preOrder(root);//从根节点开始遍历
    }
    public static void preOrder(TreeNode root) {
        if (root == null){ // 一颗空树，最基本的情况，什么时候不需要在递归了
            return ;
        }
        visited(root); //   1: 访问节点
        preOrder(root.left);//2 访问左子树节点
        preOrder(root.right);//3 访问右子树的节点
    }
    public static void visited(TreeNode node) {
        nodeCount++;// 统计节点的个数
        // 或者nodeCount += node.v + 1;//所有节点的值都+1,求和
        System.out.println(node.v);
    }
}//end class Solution

2.广度优先搜索算法(Breadth First Search：BFS)

• 广度优先搜索顾名思义，就是要广阔 ，不断通过搜索自己旁边的节点，旁边的节点构成一个队列，只有把自己旁边的节点遍历完之后，才会遍历旁边旁边的节点
• 树的层次遍历，可以使用广度优先算法
• 画一个简单的图，带入一下下面的代码，就会很明白

public static void main(String[] args){
    Graph G = new Graph();
    DFS(G.get(0),G);// 表示从0 节点开始遍历
}
public static void BFS(Node S,Graph G) {
        /* 初始化数据结构
         * 队列Q
         * 是否遍历的标志hashmap
         */
        Queue<Node> Q = new LinkedList<Node>();
        HashMap<Node,Boolean> visitedMap = new HashMap<Node,Boolean>();
        /** 初始化标志
         */
        Q.add(S);
        visitedMap.put(S, true); // S 已经认为是在队列当中，说明已经要被访问了，所以这么标志
        while( !Q.isEmpty()) { // (0).队列非空
            Node q = Q.poll(); // (1).出队列
            visited(q); // (2).这个就是遍历函数，或者要通过遍历来实现的目标的函数,,也可以时其他的过程处理，bi'r比如计数，求和等
            /* (3).把它的相邻节点，有个求相邻节点的函数
             * 且未遍历到的标志为遍历并放入队列Q
             */
            ArrayList<Node> adjNodeList = G.getAdjectList(q); // 获取相邻的节点
            for(int i = 0; i < adjNodeList.size() ; ++i) {
                /**没有被访问过，放到队列当中*/
                if (visitedMap.containsKey(adjNodeList.get(i)) == false) { // 没有被访问过
                    Q.add(adjNodeList.get(i)); //加入到队列中
                    visitedMap.put(adjNodeList.get(i),true);// 表示已经访问了
                }
            }//end for
        }// end while
    }
    public static void visited(Node s) {
        System.out.println(s); // 这里只是简单的打印一下，可进行性统计、计数等操作
    }

2.1 广度优先搜索的举例

• 对于二叉树树的遍历来说，除了上面提到的，先序、中序、后序遍历外还有一种层次遍历，
• 层次遍历的顾名思义就是，把树放好，从根节点开始，一层一层的遍历，从一层层的描述可以看出来，这个就是广度优先搜索的一个实例。
• 其实二叉树也是图的一种

 class TreeNode {
    int v;
    TreeNode left,right;
    /**
        (1).获取这个节点相邻节点，也就是从这个节点可以访问到的节点，左子树节点和右子树节点
        (2).虽然这个节点的父节点从实际画出来的结构看也能访问到
        (3).但是定义数据结构的时候，并没有看到有子节点访问父节点的路径
        (4).如果TreeNode 里面存储parent节点表示父节点，那么是可以访问到的，还要看数据结构怎么设计
    */
    public ArrayList<TreeNode> getAdjectList(){
        ArrayList<TreeNode> adj = new ArrayList<TreeNode>();
        if(this.left != null ) {
            adj.add(this.left);
        }
        if(this.right != null ) {
            adj.add(this.right);
        }
    }
}
public static void BFS(TreeNode root) {
        /* 初始化数据结构
         * 队列Q
         * 是否遍历的标志hashmap
         */
        Queue<Node> Q = new LinkedList<Node>();
        HashMap<Node,Boolean> visitedMap = new HashMap<Node,Boolean>();
        /** 初始化标志
         */
        Q.add(root);
        visitedMap.put(root, true); // root 已经认为是在队列当中，说明已经要被访问了，所以这么标志
        while( !Q.isEmpty()) { // (0).队列非空
            TreeNode q = Q.poll(); // (1).出队列
            visited(q); // (2).这个就是遍历函数，或者要通过遍历来实现的目标的函数,,也可以时其他的过程处理，比如计数，求和等
            /* (3).把它的相邻节点，有个求相邻节点的函数
             * 且未遍历到的标志为遍历并放入队列Q
             */
            ArrayList<TreeNode> adjNodeList = q.getAdjectList(); // 获取相邻的节点
            for(int i = 0; i < adjNodeList.size() ; ++i) {
                /**没有被访问过，放到队列当中*/
                if (visitedMap.containsKey(adjNodeList.get(i)) == false) { // 没有被访问过
                    Q.add(adjNodeList.get(i)); //加入到队列中
                    visitedMap.put(adjNodeList.get(i),true);// 表示已经访问了
                }
            }//end for
        }// end while
    }
    public static void visited(TreeNode s) {
        System.out.println(s); // 这里只是简单的打印一下，可进行性统计、计数等操作
    }

• 考虑到二叉树结构的特殊性，一个节点最多只有两个子节点，而且每个节点的前驱节点，也就是父节点有且只有一个，所以不会存在一个节点可以通过两个或者多个节点能够访问
• 这样也就可以避免使用标志数组了，因为被访问到的几点，肯定时没有被访问过的，所以上述的标志数组visitedMap可以不用，而直接把一个节点的非空相邻节点加入到队列当中。

2.3 相关二叉树的层次遍历(BFS)的练习题

• 这里有个二叉树的层次遍历的过程，题目的意思是区分每一层的数据，是这个层次遍历的扩展，可以考虑使用这个标志数组，来表示一层的结束。
• 还有一个二叉树层次遍历的变形 层次遍历变形
• 求二叉树最底层的最左边的节点
• 求二叉树每一层节点的最大值

2.4 图的联通量的遍历

• 这里的这个问题就是找到最大的连通分量

/***
 * A----B    D    E
 * |    |    |    |
 * F----G    H    I
 *           |    |
 * J    K    L    M
 * |         |
 * N    O----P----Q
 * (x-1,y-1)---(x-1,y)----(x,y-1)
 * (x , y-1)---(x , y)----(x,y+1)
 * (x+1,y-1)---(x+1,y)----(x+1,y+1)
 *
 *  11110
    11010
    11000
    00000
    answer:1
 * 
 *  11000
    11000
    00100
    00011
 * answer:3
 */
public class Solution {
    public static HashMap<NodeValue,Boolean> visitedMap = new HashMap<NodeValue,Boolean>();
    public static void main(String[] args) {
        char [][] grid =  new char[n][n];
        System.out.println(grid);
    }
    public static int numIslands(char[][] grid) {
        // 每一个节点都需要遍历,其实，已经遍历过的节点，会在visitedMap当中标志，不会添加相邻节点到队列当中
        int area = 0;
        int count = 0;
        for(int x =0; x < grid.length;++x) {
            for(int y = 0; y < grid[0].length;++y) {
                if(visitedMap.containsKey(new NodeValue(x,y)) == false) {
                    BFS(grid,x,y);
                    count ++;// 表示找到了一个连通分量
                    /**
                    if(area < tarea) {
                        area = tarea;
                    }
                    **/
                }
            }
        }
        return count;
    }
    /**
     * grid 可以认为是一个图，startNodex,startNodey 表示开始遍历的节点
     * */
    public static int BFS(char[][] grid,int startx,int starty) { 
        int area = 1; //当前只有一个节点
        Queue<NodeValue> Q = new LinkedList<NodeValue>();
        NodeValue e = new NodeValue(starty, starty);
        Q.add(e);
        visitedMap.put(e, true);
        while(! Q.isEmpty()) {
            NodeValue q = Q.poll();
            ArrayList<NodeValue> adjlist = getAdjList(grid,q);
            for(int i = 0 ;i < adjlist.size(); ++i) {
                if(visitedMap.containsKey(adjlist.get(i)) == false) {
                    Q.add(adjlist.get(i));
                    visitedMap.put(adjlist.get(i), true);
                    area += 1;// 说明这个是可以到达的和startx,starty 是相邻的
                }
            }
        }
        return area;
    }
    /**寻找其相邻节点的函数*/
    public static ArrayList<NodeValue> getAdjList(char[][] grid,NodeValue e) {
        ArrayList<NodeValue> adjlist = new ArrayList<NodeValue>();
        int xlen = grid.length;
        int ylen = grid[0].length;
        if(e.x - 1 >=0 ) { // 上面
            if (grid[e.x -1 ][e.y] == '1') {
                adjlist.add(new NodeValue(e.x-1,e.y));
            }
        }
        if(e.y - 1 >=0 ) { //左面
            if (grid[e.x ][e.y - 1 ] == '1') {
                adjlist.add(new NodeValue(e.x,e.y - 1 ));
            }
        }
        if(e.x + 1 < xlen ) { // 下面
            if (grid[e.x + 1 ][e.y] == '1') {
                adjlist.add(new NodeValue(e.x + 1,e.y));
            }
        }
        if(e.y + 1 < ylen ) { // 右面
            if (grid[e.x ][e.y + 1] == '1') {
                adjlist.add(new NodeValue(e.x,e.y + 1));
            }
        }
        return adjlist;
    }
}
class NodeValue{
    public int x, y;
    public NodeValue(int x,int y){
        this.x = x;
        this.y = y;
    }
    @Override
    public boolean equals(Object obj) {
        // TODO Auto-generated method stub
        if(this == obj)
            return true;
        if(obj == null)
            return false;
        NodeValue node = (NodeValue)obj;
        return this.x == node.x && this.y == node.y;
    }
}

3.深度度优先算法(Depth First Search:DFS)

• 顾名思义就是要深度去搜索
• 和广度优先算法不同的是，深度优先是(1)通过一个节点，作为当前遍历的开始节点，然后找到它的下一个节点，作为下一次遍历的开始节点，一直到没有节点可以遍历，那么就会返回上一层，(2)再招其他的节点开始遍历，(3)如果还没有，那么在返回上一层，(4)再招其他的节点开始遍历，直到所有节点都遍历了
• 需要有个标志，来表示这个节点是否已经被遍历了。
• 深度优先可以改编为用栈来实现，因为

/**是否已经被遍历的标志，如果被遍历了，是不会在进行遍历的*/
public static HashMap<Node,Boolean> visitedMap= new HashMap<Node,Boolean>();
public static void main(String[] args) {
    Graph G = new Graph();
    Node start;
    /**
    //每个节点开始去遍历，按照一个图所有节点之间都是可以到达的化，这种做法是不必要的，因为从任何一个节点都是可以遍历整个图的，
    但是如果这个图中有两个不可达的节点，这个循环就是必要的了。
    */
    for(int i = 0 ;i < G.size(); ++i)
        if (visitedMap.get(G.get(i)) == false)
            DFS(G.get(i),G);
}
public static void DFS(Node s,Graph G){
    if( visitedMap.get(s) == true){
        /**递归的出口一定要有，
        * 已经被遍历了，所有不需要再遍历了，那么直接返回吧
        */
        return ;
    }
    /**
        没有被遍历、那么遍历一下、设置标志位
    */
    visit(s);//遍历下
    visitedMap.put(s,true);// 标志位已经遍历了
    /** 获取相邻节点，并遍历*/
    ArrayList<Node> adjList = G.getAdjNodeList(s,G);
    for(int i = 0; i < adjList.size(); ++i){
        Node newNode = adjList.get(i);
        if (visitedMap.contains(newNode) == false) {
            DFS(newNode,G);//newNode 作为一个新的节点，从这里又开始向它的相邻节点遍历了
        }
    }
}
public static void visit(Node s) {
    System.out.println(s);// 只是打印
}

4.回溯算法

• 回溯算法是递归算法的一个类型，一种变形，多了条件的判断
• 也就是深度优先遍历 (depth first search) DFS