目录
一、递归的概念
二、递归执行过程分析
三、递归练习
3.1 按顺序打印一个数字的每一位，例如123打印出1 2 3
3.2 递归求 1 + 2 + 3 + ... + n 的和
3.3 输入一个非负整数，返回组成它的数字之和，例如123，得1+2+3
3.4 求斐波那契数列的第 N 项
一、递归的概念
1. 生活中例子：
从前有坐山，山上有座庙，庙里有个老和尚给小和尚将故事，讲的就是：
"从前有座山，山上有座庙，庙里有个老和尚给小和尚讲故事，讲的就是：
"从前有座山，山上有座庙..."
"从前有座山……" "
像这种自身中又包含了自己的现象，在数学和编程中非常有用，因为有些时候，我们遇到的问题直接并不好解决，但是会发现将原问题拆分成其子问题之后，子问题与原问题有相同的解法，这样的话子问题解决之后，原问题也就会迎刃而解了。
2. 递归的概念：一个方法在执行过程中调用自身，就称为 "递归"，与上面生活中的例子不同的是，递归不是无限递归，它必须有一个递归结束的条件。
3. 在程序层面要完整的写出一个递归需要两个必备的条件：
① 起始条件：可以理解为递归结束的条件
② 递归公式：每个问题的递推公式是不一样的，例如求N!，可以转换成求 N+(N-1)!
4. 递归的缺点：空间复杂度高，能用迭代的就不要用递归。
二、递归执行过程分析
1. 要想弄清楚递归执行的过程，通常会通过画图的方式进行理解，下面以求N!为例进行分析
2. 思路：假如要求3!，通过分析我们可以将其拆分为求3*2!，而2!又可以拆分为求2*1!，很明显可以看出我们在做一件重复的事，即求一个数的阶乘里面又可以看成求一个数的阶乘，而我们知道1!=1，因此这道题是满足使用递归所需的两个必备条件的，所以可以采用递归的方式进行求解。
3. 求解的代码思路为，定义一个求阶乘的方法，如果n==1，就返回1，否则返回n*fac(n-1)，递归执行的过程，见下图图片所示。
public static int fac(int n) {
if (n == 1) {
return 1;
}
return n * fac(n - 1);
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
System.out.println(fac(n));
}
三、递归练习
3.1 按顺序打印一个数字的每一位，例如123打印出1 2 3
思路：打印123的每位，可以看成先打印12(123/10)的每位，再打印3(123%10)，打印12的每位可以看成先打印1(12/10)的每位，再打印2(12%10)，而我们知道当要打印的数为小于10的数时，直接打印即可，这道题是满足使用递归所需的两个必备条件的，所以可以采用递归的方式进行求解。
求解的代码思路：定义一个求打印一个数字每位的方法，如果n < 10，直接打印并返回，否则返回n*printNum(n-1)，递归执行的过程，见下图图片所示。
public static void printNum(int n) {
if (n < 10) {
System.out.printf("%d ", n);
return;
}
printNum(n / 10);
System.out.printf("%d ", n % 10);
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
printNum(n);
}
3.2 递归求 1 + 2 + 3 + ... + n 的和
思路：当n=3时，表示我们要求3~1之间整数的和，这个式子又可以看成3加2~1之间整数的和，2~1之间整数的和又可以看成求2加1~1之间整数的和，而1~1之间整数的和就是1，这道题是满足使用递归所需的两个必备条件的，所以可以采用递归的方式进行求解。
求解的代码思路：定义一个求n~1之间整数和的方法，如果n == 1，直接返回1，否则返回n+addNum(n-1)，递归执行的过程，见下图图片所示。
public static int addNum(int n) {
if (n == 1) {
return 1;
}
return n + addNum(n - 1);
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
System.out.println(addNum(n));
}
3.3 输入一个非负整数，返回组成它的数字之和，例如123，得1+2+3
思路：假设我们要求组成123每一位数字的和，可以看成求3(123%10)加组成12(123/10)每一位数字的和，求组成12每位数字的和，又可以看成求2(12%10)加组成1(12/10)每一位数字的和，当我们要求的和的数小于10时直接返回即可，这道题是满足使用递归所需的两个必备条件的，所以可以采用递归的方式进行求解。
求解的代码思路：定义一个求组成某数字的每位和的方法，如果n < 1，直接返回n，否则返回 n%10 + numAdd(n/10)，递归执行的过程，见下图图片所示。
public static int numAdd(int n) {
if (n < 10) {
return n;
}
return n % 10 + numAdd(n /10);
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
System.out.println(numAdd(n));
}
3.4 求斐波那契数列的第 N 项
什么是斐波那契数列：斐波那契数列 - 搜狗百科 (sogou.com)，指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……，即从第3项开始，每一项都等于前两项之和。
思路：如果我们要求斐波那契数的第n项，那么求得斐波那契数的第n-1项和n-2项之和即可，而求斐波那契数的第n-1项，又可以看作求斐波那契数的第n-2项和n-3项之和...，如果n为1则直接返回0即可，如果n为2则直接返回1即可，这道题是满足使用递归所需的两个必备条件的，所以可以采用递归的方式进行求解。
求解的代码思路：定义一个求斐波那契数第n项的方法，如果n == 1，直接返回0，否则如果n == 2返回1，否则返回 fib(n-1) + fib(n -2)，递归执行的过程，见下图图片所示。
public static int fib(int n) {
if (n == 1) {
return 0;
} else if (n == 2) {
return 1;
}
return fib(n - 1) + fib(n - 2);
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
System.out.println(fib(n));
}但当我们求 fib(40) 的时候发现, 程序执行速度极慢，原因是进行了大量的重复运算，如在上面基础上加上一个成员变量，当n=40时，记录fib(1)一共计算了多少次，结果为39088169次。因此本道题不适合用递归的方式求，而更适合用迭代的方式求。
public static int count = 0;//成员变量，实现累加
public static int fib(int n) {
if (n == 1) {
count++;
return 0;
} else if (n <= 2) {
return 1;
}
return fib(n - 1) + fib(n - 2);
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
System.out.println(fib(n));
System.out.println(count);
}(以后求斐波那契数列的第 N 项都用迭代的方法)
思路：我们可以定义fib3、fib2、fib1分别表示要求的第n项，和第n-1项、第n-2项，如果是要求第1项或第2项的斐波那契数，特殊处理返回即可；当n>=3时，n-2等于几就执行几次求 fib3 和更新fib1、fib2的操作，循环结束后fib3就是斐波那契数列的第n项项的值。
public static int fib2(int n) {
int f1 = 0;
int f2 = 1;
int f3 = 1;
/*前两项特殊处理*/
if (n == 1) {
return 0;
} else if (n == 2){
return 1;
}
/* n>=3时 */
for (int i = 3; i <= n; i++) {
f3 = f1 + f2;
f1 = f2;
f2 = f3;
}
return f3;
}本篇文章已完结，谢谢支持哟 ^^ ！！！
