递归
条件
-
可以通过递归调用来缩小问题规模,且新问题与原问题有着相同的形式。(自身调用)
-
存在一种简单情境,可以使递归在简单情境下退出。(递归出口)
递归三要素
-
一定有一种可以退出程序的情况;
-
总是在尝试将一个问题化简到更小的规模
-
父问题与子问题不能有重叠的部分
例子
public class Factorial {
public static void main(String[] args) {
printNum(5);
}
public static void printNum(int num){
if (num > 1){ //------>如果num<=1 就退出,递归的出口
num = num - 1; //将num逐渐变小,逐渐靠近退出的情况
printNum(num); //------>调用自己
}
System.out.print(num + ",");
}
}
执行结果:1,1,2,3,4,
流程分析
public static void printNum(5){
if (num > 1){ //--->num = 5,成立
num = num - 1; //--->num = 4
printNum(num);
}
System.out.print(num + ",");
}
public static void printNum(5){
public static void printNum(4){
if (num > 1){ //--->num = 4,成立
num = num - 1; //--->num = 3
printNum(num);
}
System.out.print(num + ",");
}
System.out.print(num + ","); //--->num:4
}
public static void printNum(5){
public static void printNum(4){
public static void printNum(3){
if (num > 1){ //--->num = 3,成立
num = num - 1; //--->num = 2
printNum(num);
}
System.out.print(num + ",");
}
System.out.print(num + ","); //------3
}
System.out.print(num + ","); //----->4
}
public static void printNum(int num){
public static void printNum(int num){
public static void printNum(int num){
public static void printNum(int num){
if (num > 1){ //--->num = 2,成立
num = num - 1; //--->num = 1
printNum(num);
}
System.out.print(num + ",");
}
System.out.print(num + ","); //------>2
}
System.out.print(num + ",");//------->3
}
System.out.print(num + ","); // ------>4
}
public static void printNum(int num){
public static void printNum(int num){
public static void printNum(int num){
public static void printNum(int num){
public static void printNum(int num){
if (num > 1){ //--->num = 1,不成立
num = num - 1;
printNum(num);
}
System.out.print(num + ","); //当前打印:1,
}
System.out.print(num + ","); //-------->1
}
System.out.print(num + ","); // ------->2
}
System.out.print(num + ","); // ------->3
}
System.out.print(num + ","); // ----->4
}
public static void printNum(int num){
public static void printNum(int num){
public static void printNum(int num){
public static void printNum(int num){
public static void printNum(int num){
System.out.print(num + ","); //--->打印当前的num:1
}
System.out.print(num + ","); // -------->1 //当前打印:1,
}
System.out.print(num + ",");//-------->2
}
System.out.print(num + ",");//-------->3
}
System.out.print(num + ",");//-------->4
}
public static void printNum(int num){
public static void printNum(int num){
public static void printNum(int num){
public static void printNum(int num){
System.out.print(num + ","); //--->打印当前的num:1
} //当前打印:1,1,
System.out.print(num + ",");
}
System.out.print(num + ",");
}
System.out.print(num + ",");
}
public static void printNum(int num){
public static void printNum(int num){
public static void printNum(int num){
System.out.print(num + ",");//--->打印当前的num:2 //当前打印:1,1,2,
}
System.out.print(num + ",");
}
System.out.print(num + ",");
}
public static void printNum(int num){
public static void printNum(int num){
System.out.print(num + ",");//--->打印当前的num:3 //当前打印:1,1,2,3
}
System.out.print(num + ",");
}
public static void printNum(int num){
System.out.print(num + ",");//--->打印当前的num:4 //当前打印:1,1,2,3,4
}