算法系列之递归

如何理解递归？

把一个直接调用自己或通过一系列的调用语句间接的调用自己的函数，称做递归函数。

递归的用途：文件目录搜索、DFS 深度优先搜索、前中后序二叉树遍历等等。

递归需要满足的三个条件

• 一个问题的解可以分解为多个子问题的解
• 这个问题与分解之后的子问题，除了数据规模不同，求解思路一致
• 递归终止条件

如何写好递归代码？

1. 找出大问题化小问题的规律
2. 推敲递推公式
3. 推敲终止条件
4. 演化代码

递归代码需要注意的问题

1. 警惕堆栈溢出。 如果遇到计算机资源较小的情况下，递归代码，调用层次深，往往会造成堆栈溢出的情况，所以为了避免发生该异常，控制递归层次可以有效的避免堆栈溢出。
2. 重复计算。因为递归函数在求解时通常会发生某个数据重复计算，为了避免这种情况，可以使用散列数据结构来保存已计算后的数据，如果已经数据已经计算过了，直接去散列值中的数据即可。
3. 递归代码时间复杂度为O(n)

举一个递归的例子，这个例子当时是去面试时面试官出的一道题目，现场编码比较Jdk1.6源码包与Jdk1.8源码包，求Jdk1.6在1.8中不存在的文件。当时由于时间原因，并没有把所有代码写完，写完了伪代码，并且把思路给面试官大概讲解了下。这个题目其实就用到了递归的算法，递归求1.6与1.8中所有的文件，并且将文件存入容器中，最终进行对比。把不存在的文件进行输出。具体代码如下：

文件实体类

package fileDemo;

public class JavaFile {
    private String fileName;
    private String filePath;
    public JavaFile(String fileName,String filePath){
        this.fileName = fileName;
        this.filePath = filePath;
    }
    public String getFileName() {
        return fileName;
    }
    public void setFileName(String fileName) {
        this.fileName = fileName;
    }
    public String getFilePath() {
        return filePath;
    }
    public void setFilePath(String filePath) {
        this.filePath = filePath;
    }
}

文件工具类

package fileDemo;

import java.io.File;
import java.util.ArrayList;
import java.util.List;

public class FileUtil {
    /**将所有文件放入容器**/
    public List<JavaFile> getAllJavaFile(String name){
        List<JavaFile> listFile = new ArrayList<JavaFile>();
        getJavaFileByPath(name,listFile);
        return listFile;
    }
    /**递归获取文件**/
    public List<JavaFile> getJavaFileByPath(String name,List<JavaFile> fileList){
        File    file = new File(name);
        File [] files = file.listFiles();
            for(File f : files){
                if(!f.isDirectory()){
                    //如果不是文件夹，则将文件存入容器中
                    fileList.add(new JavaFile(f.getName(),f.getPath()));
                }else{
                    //如果是文件夹，继续调用自己
                    getJavaFileByPath(f.getAbsolutePath(),fileList);
                }
            }
        return fileList;
    }
    /** 对比文件*/
    public List<JavaFile> compareJDK8AndJDK6File(List<JavaFile> jdk8List,List<JavaFile> jdk6List){
        /**文件名比较，将jdk6不存在的文件输出，并且将路径输出**/
        List<JavaFile> noneFileList = new ArrayList<JavaFile>();
        for(JavaFile j8: jdk8List){
            boolean isNone = false;
            for(JavaFile j6:jdk6List){
                if(j8.getFileName().equals(j6.getFileName())){
                    isNone = true;
                    break;
                }
            }
            /**如果沒有相同的，則將J8該文件存入容器中**/
            if(!isNone){
                noneFileList.add(j8);
            }
        }
        return noneFileList;
  }
}

最终测试类

package fileDemo;

import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * JDK1.8与JDK1.6文件对比
 * @author liumengxi
 */
public class Main {

    /**
     * @param args
     */
    public static void main(String[] args) {
        Map map = new HashMap();
        FileUtil fu = new FileUtil();
        String jdk8 = "E:\\javaSrc\\JDK1.8";
        String jdk6 = "E:\\javaSrc\\JDK1.6";
        List<JavaFile> jdk8List = fu.getAllJavaFile(jdk8);
        List<JavaFile> jdk6List = fu.getAllJavaFile(jdk6);
        List<JavaFile> noneJ8 = fu.compareJDK8AndJDK6File(jdk8List, jdk6List);
        /**循環不存在的類*/
        for(JavaFile jf : noneJ8){
            System.out.println("JDK6不存在的文件名稱是--->" + jf.getFileName() + " JDK8的類路徑是 --->"  + jf.getFilePath());
        }
    }
}

文件工具类中，针对文件查找就利用了递归思路，文件的深度检索直到查找到文件，存入比较容器中。这个思路刚好切合递归的三个条件:一个问题的解可以分解为多个子问题的解、这个问题与分解之后的子问题，除了数据规模不同，求解思路一致、递归终止条件。当然，上述代码没有充分考虑到时间复杂度，效率一般，还是可以进行优化的。这里不是重点，重点是利用递归的思路，写好更简单易懂的代码，多联系、多思考、多动手。