我对递归的认识

首先明确一点:
递归是不符合人自然的逻辑思维的,需要训练.

(1)递归的例子

求5的阶乘

/***
     * 阶乘
     * @param n
     * @return
     */
    public static int arrayArrange(int n){
        if(n<2){
            return 1;
        }else{
            return n*arrayArrange(n-1);
        }
    }

arrayArrange方法体中调用了自身,只是参数不同.

求1到100的和

public static int getSum(int n){
        if(n<2){
            return 1;
        }else{
            return n+getSum(n-1);
        }
    }
    @Test
    public void test_getSum(){
        int n=10;
        System.out.println(getSum(n));
    }

获取指定目录下的所有的文件（不包括文件夹）

/***
     * 获取指定目录下的所有的文件（不包括文件夹），采用了递归
     * 
     * @param obj
     * @return
     */
    public static List<File> getListFiles(Object obj) {
        File directory = null;
        if (obj instanceof File) {
            directory = (File) obj;
        } else {
            directory = new File(obj.toString());
        }
        ArrayList<File> files = new ArrayList<File>();
        if (directory.isFile()) {
            files.add(directory);
            return files;
        } else if (directory.isDirectory()) {
            File[] fileArr = directory.listFiles();
            if(!ValueWidget.isNullOrEmpty(fileArr)){
                for (int i = 0; i < fileArr.length; i++) {
                    File fileOne = fileArr[i];
                    files.addAll(getListFiles(fileOne));
                }
            }
        }
        return files;
    }

级联删除文件

/***
     * delete a directory/folder<br>
     * 采用了递归
     * @param someFile
     *            :directory
     */
    public static boolean deleteDir(File someFile) {
        if (!someFile.exists()) {
            System.out.println("[deleteDir]File " + someFile.getAbsolutePath()
                    + " does not exist.");
            return false;
        }
        if (someFile.isDirectory()) {// is a folder
            File[] files = someFile.listFiles();
            if (!ValueWidget.isNullOrEmpty(files)) {
                for (File subFile : files) {
                    boolean isSuccess = deleteDir(subFile);
                    if (!isSuccess) {
                        return isSuccess;
                    }
                }
            }

        } else {// is a regular file
            boolean isSuccess = someFile.delete();
            if (!isSuccess) {
                return isSuccess;
            }
        }
        return !someFile.isDirectory() || someFile.delete();
    }

(2)递归的特征

(a)方法体中调用方法自身.拿累加举例说明

getSum方法体中又调用了getSum,并且参数列表是完全一样的.

(b)每次调用参数都会有变化,至少有一个参数充当迭代器,类似于for循环的迭代器.

(c)一定有一个出口,要不然就死循环了.
这里的出口就是n<2的if条件分支.

(d)可以分解出来n个步骤,每个步骤的操作完全一样,只是参数不同而已.
n的累加等于n加上(n-1)的累加
(n-1)的累加等于(n-1)加上(n-2)的累加
(n-2)的累加等于(n-2)加上(n-3)的累加
(n-3)的累加等于(n-3)加上(n-4)的累加
……
每个步骤的操作都是”加上”.
当然有的递归,其操作可能复杂一些.
比如求组合:

(3)递归使用的场景

哪些场景适用于递归呢?
(a)计算的次数与参数的规模成正相关
即参数越大,计算的次数越多
(b)每一步计算的规则完全一样,只是参数不同而已.
(c)后一次的计算结果依赖上一次的计算结果

(4)动态规划

说到递归,不得不说动态规划
(待续…)

(5)递归可以用for循环来代替吗?

哪些递归可以用for循环代替?
可以确定循环次数的
比如求累加

public static int getSum(int n){
        int sum=0;
        for(int i=0;i<n;i++){
            sum=sum+(i+1);
        }
        return sum;
    }

阶乘:

/***
     * 阶乘
     * @param n
     * @return
     */
    public static int arrayArrange(int n){
        int power=1;
        for(int i=0;i<n;i++){
            power=power*(i+1);
        }
        return power;
    }
    @Test
    public void test_arrayArrange2(){
        int n=4;
        System.out.println(arrayArrange(n));
    }

(6)回答网上一个递归的问题

问题见:递归调用中不明白的地方
我把问题翻译成为java:

public static void main(String[] args) {
        up(1);
    }
    public static void up(int n)
    {
        System.out.println(String.format("rank1 %d", n ));
        if (n < 4)    
            up(n+1);
        System.out.println(String.format("rank2 %d", n) );
    }

题主的问题:
不明白的地方就是：程序不能直接返回到main()中的初始调用部分吗？是因为递归的存在而导致的每一级逐步返回吗？为什么会出现4–>1的输出呢
程序的输出是:

如果我是刚参加工作那会儿,也会不明白.
我们可以想象成中断处理程序


递归调用是多次执行一个函数，也就是多次将一个函数压栈，请注意，这里是将整个完整的函数压栈，而栈是一个先入先出的数据结构。递归的本质其实都可以用for循环来替代。在你的代码中，递归调用函数的顺序，也就是压栈的操作是up1,up2,up3,up4.而up2的调用时间是在up1内，up3得调用时间在up2内，up4得调用在up3内，所以up1得函数是在up2出栈以后才出栈，up2是在up3出栈以后才出栈，up3是在up4出栈以后才出栈。这样推一下，你就清楚函数的执行顺序和先后出栈顺序啦！
作者:hw1287789687
联系邮箱:1287789687@qq.com