递归定义

程序调用自身的编程技巧称为递归(recursion).
递归就是程序调用自身不断深入嵌套,直到满足条件退出的一种算法.
一般来说,递归需要有边界条件/递归前进段和递归返回段.当边界条件不满足时,递归前进;当边界条件满足时,递归返回.

阶乘的代码

//阶乘
public static int factorial(int n) {
    if(n==0) return1; //限制条件,对该方法调用自己做了限制
    return n * factorial(n - 1);
}

image

注意事项

• 递归程序必须事先判断好终点,不然就会造成无限调用的情况
• 递归程序执行的动作虽然一样,但是每次执行的参数不同,不然就会无意义.

应用场景

删除指定路径下的文件夹里内容以及子文件夹以及子文件夹内容

一般树状结果的都可以使用递归查询,比如查询地区,梳妆的菜单等.递归比普通的算法耗内存,谨慎使用.还有一种叫作"尾递归"就是把上一个方法的返回值当作参数传给下一个方法,不用像递归向上返回.

递归的优点

• 简洁
• 在树的前序,中序,后序遍历算法中,递归的实现明显要比循环简单得多

递归的缺点

• 递归由于是函数调用自身,而函数调用是有时间和空间的消耗:每一次函数调用,都需要在内存栈中分配空间以保存参数,返回地址以及临时变量,而往栈中压入数据和弹出数据都需要时间. ->效率低
• 递归中很多计算都是重复的,由于其本质是把一个问题分解成两个或者多个小问题,多个小问题存在相互重叠的部分,则存在重复计算,如fibonacci斐波那契数列的递归实现. ->效率
• 调用栈可能会溢出,其实每一次函数调用会在内存栈中分配空间,而每个进程的栈的容量是有限的，当调用的层次太多时，就会超出栈的容量，从而导致栈溢出。->性能