递归算法详解：从入门到精通

1 概述

什么是递归

方法自身调用自身

递归分类

间接递归：方法A调用方法B，方法B调用方法C，方法C调用方法A

直接递归：方法A调用方法A

递归的使用注意事项

递归必须有要出口：结束递归的条件

递归次数不要太多

java.lang.StackOverflowError：栈内存溢出错误

代码

public class DGDemo {
private static int index = 1;
public static void main(String[] args){
System.out.println("main = " + index++);
testA();
System.out.println("main = " + index++);
}
public static void testA(){
if (index >= 4) return;
System.out.println("testA = " + index++);
testB();
System.out.println("testA = " + index++);
}
public static void testB(){
System.out.println("testB = " + index++);
testC();
System.out.println("testB = " + index++);
}
public static void testC(){
System.out.println("testC = " + index++);
testA();
System.out.println("testC = " + index++);
}
}

2 递归求1到n的和

/**

使用递归求2到n的和，n大于2

*/

public class DGDemo01 {
public static void main(String[] args){
System.out.println(sum(3));
System.out.println(sum(5));
}
/*
求1到n的和
*/
public static int sum(int n){
// 如果n等于，则直接返回2，结束递归
if (n == 2) return 2;
return n + sum(n-1);
}
}

3 递归求n的阶乘

/**

递归求n！阶乘

*/

public class DGDemo02 {
public static void main(String[] args){
System.out.println(sum(4));
System.out.println(sum(6));
}
/*
求n！
*/
public static int sum(int n){
// 如果n等于，则直接返回1，结束
if (n == 1) return 1;
return n * sum(n-1);
}
}