Java基础——递归 递归
一、预备知识
1、栈内存
关于栈内存，我们需要了解栈内存管理的细节：
（1）、栈内存分配的基本单位——栈帧
a、之前讲过，局部变量（方法的形式参数和方法中定义的变量）存储在栈空间中；
b、一个方法，当它被调用执行的时候，方法中的局部变量等，才需要在栈空间上存储，当调用结束，立即释放栈空间上占用的内存；
c、即每一个运行中的方法，都需要占用栈内存中的一片内存空间；
d、于是，每一个运行的方法，都会在栈上分配一片，只属于该运行中的方法的内存空间——栈帧（Stack Free）
（2）、栈中内存的基本单位，它的生命周期（何时分配，合适回收）
a、当一个方法被调用执行的时候，给该运行中的方法，分配栈帧；
b、当一个方法执行完毕的时候，它对应的栈帧被回收（销毁释放）
注意：一个方法可以被多次调用，每一次方法的调用（即每一次方法的运行），都会给它分配一个栈帧。（一个方法可以对应多个栈帧，被多次调用）
public class RecursionDemo{
public static void main(String[] args){
//调用递归方法
function(); //报错：*Error
}
/*
不带递归出口的递归方法（错误的递归）
*/
public static void function(){
//自己调用自己
function();
}
*Error产生的原因：
1、function方法，无限的自己调用自己，每次调用执行，都需要给该方法分配栈帧。
2、但是栈内存大小有限。
3、在function方法无限调用自己过程中，每一次方法的执行，都没纸箱完毕（都在调用过程中）
4、最终，导致栈内存会没有可用内存空间，此时如果，我在向栈申请创建栈帧就会出现*Error错误
* —— 一个很有名、很活跃的程序员问答平台
2、栈的内存空间
栈区（stack）：由编译器自动分配释放 ，存放函数的参数值，局部变量的值等。其操作方式类似于数据结构中的栈。
堆区 （heap）：一般由程序员分配释放， 若程序员不释放，程序结束时可能由OS回收 。注意它与数据结构中的堆是两回事，分配方式倒是类似于链表
全局区（静态区）（static）：全局变量和静态变量的存储是放在一块的，初始化的全局变量和静态变量在一块区域， 未初始化的全局变量和未初始化的静态变量在相邻的另一块区域 - 程序结束后有系统释放
文字常量区 ：常量字符串就是放在这里的。 程序结束后由系统释放
程序代码区：存放函数体的二进制代码
关于栈，我们姑且先了解以上内容
更多关于栈的详细知识可参见以下博文：
https://www.cnblogs.com/dwlsxj/p/Stack.html
https://www.cnblogs.com/George1994/p/6399895.html
二、递归
1、递归方法的定义
方法定义中调用方法本身的现象
2、实现递归需要注意的问题
（1）、递归一定要有出口！！（递归需要有出口条件，在满足某种特殊条件的情况下，停止递归调用）
（2）、次数不能太多，否则就会出现Stack overflow
public class RecursionDemo1{
public static void main(String[] args){
//调用递归方法
function(); //*Error
}
/*
不带递归出口的递归方法（错误的递归）
*/
public static void function(){
//自己调用自己
function();
}
/*
带递归出口的递归方法
*/
public static void recursion(int n){
//递归出口
if(n <= 0){
//当达到递归出口，不再自己调用自己
System.out.println("n <= 0, n = " + n);
return;
}
System.out.println("n > 0, n = " + n);
//当未达到递归出口条件时
n--;
recursion(n);
}
}
汉诺塔问题：
/*
1.有三根杆子A，B，C。A杆上有 N 个 (N>1) 穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至 C 杆：
a.每次只能移动一个圆盘。
b.大盘不能叠在小盘上面。
N在原始的汉诺塔问题中64，如果要完成64个圆盘的搬运，需要的很长很长时间。
问：最少要移动多少次？如何移？
解决思路以N个圆盘为例：
1. 当我们要解决N个圆盘的搬运问题，对于N个圆盘，我们可能无法一次性得到结果，
于是，我们把N个圆盘的搬运问题， -> 最大一个的圆盘的搬运 & 最大圆盘上面的 n - 1
2. 对于规模为1那个待搬运的最大的圆盘，直接就知道如何搬运（一步搞定）
3. 在2的基础上，只需要，再解决 N - 1个圆盘搬运的问题
总结一下，汉诺塔问题，解决思路(递归算法的核心思想)：
分而治之: 把一个复杂的大规模的问题，分解成若干相似的小规模的子问题，当问题规模，
足够小的是时候，我们就可以直接得到小规模问题的解，再把小规模问题的解，
组合起来，——> 大规模问题提的解
*/
public class RecursionDemo2{
public static void main(String[] args){
// 测试我们的hanoi的代码
hanoi('A', 'C', 'B', 4);
// 测试计数方法
long result = count(4);
System.out.println(result);
}
/*
计数对于n个圆盘的搬运，一共需要搬运多少次
count(n) 该方法的返回值，n个盘搬运的总次数
*/
public static long count(int n) {
// 递归出口
if (n == 1) {
return 1;
}
//1，hanoi(start, middle, end, n - 1);
long toMiddle = count(n - 1);
//2. 对于最大的那个盘，需要搬运一次，从start -> end
//3. hanoi(middle, end, start, n - 1);
long toEnd = count(n - 1);
// 2* count(n - 1) + 1
return toMiddle + 1 + toEnd;
}
/**
* 用该方法来模拟解决汉诺塔问题中圆盘的搬运
* 方法参数中，3个char类型的变量，代表3个杆的名称‘A’，‘B’,‘C’
* start——> 起始杆
* end ——> 目标杆
* middle ——> 辅助杆
* n ——> 待搬运的圆盘数量
*/
public static void hanoi(char start, char end, char middle, int n){
//递归出口,当规模足够小时，退出递归
if(n == 1){
System.out.println(start + "——>" + end);
return;
}
//按照相同的方式，将最大的圆盘之上的（n-1）个圆盘搬运到辅助杆middle上
hanoi(start, middle, end, n-1);
//最大的圆盘保留在起始杆start上，且起始杆上只有这个圆盘，对应该圆盘直接搬运到目标杆上，一步到位
System.out.println(start + "——>" + end);
//再将辅助杆上的（n-1）个圆盘，从middle杆——>end杆（以start杆为辅助杆）
hanoi(middle, end, start, n-1);
}
}
电影院问题：
/*
周末晚上你和女朋友去看电影，月黑风高，女朋友悄悄地问你：我们在第几排？电影院太黑，没办法数？怎么办？
a. 无法直接看到，自己在第几排，但是我可以，问前排的同学，他在第几排
b. 当依次向前询问，当问到第一排同学的时候，他可以用触觉来判断，比如，摸了一下发现前面没有椅子
递：分解问题 n -> n - 1 -> ... -> 1(出口条件的情况)
归: 组合小规模问题的解 n <- n - 1 <- ... 2 <- 1
递推公式：
location(n) = location（n - 1） + 1
*/
public class Demo2 {
public static void main(String[] args) {
int location = location(10);
System.out.println(location);
}
/*
n代表，实际所处的排数
*/
public static int location(int n) {
//递归出口
if (n == 1) {
// 第一排的同学直接知道自己在第一排
return 1;
}
return location(n - 1) + 1;
}
}
n的阶乘：
/**
* 3. 求n的阶乘
* 1！ = 1
* 100！= 100 * （99 * 98 * ... * 1)
* 100! = 100 * 99!
*
* 如果用f(n) 表示n的阶乘的结果
* f(n) = n * f(n - 1)
*/
public class Demo3 {
public static void main(String[] args) {
int factor = factor(5);
System.out.println(factor);
}
/*
求n的阶乘
*/
public static int factor(int n) {
// 出口条件
if (n == 1) {
return 1;
}
return n * factor(n - 1);
}
}
不死兔神：
/* *
* 4.有一对兔子，从出生后第三个月开始每月生一对兔子，小兔子从第三个月开始每月也生一对兔子，
* 假如是不死神兔，那么第20个月一共生多少对兔子？
*
* 月份 1 2 3 4 5
兔子对数 1 1 2 3 ...
i, i + 1， i + 2 代表任意连续的3个月份
N(i) 表示第i个月出生的兔子数量
N(i - 1) 表示第i - 1个月出生的兔子数量
f(i - 2) 表示第 i - 2个月及之前出生的兔子数量
i i + 1 i + 2
N(i) + N(i) = N(i) * 2
N(i - 1) + N(i - 1) + N(i - 1) = N(i - 1) * 2 + N(i - 1)
f(i - 2) + f(i - 2) + f(i - 2) = f(i - 2) * 2 + f(i - 2)
f(i) 表示第i个月兔子的数量
f(i) = f(i - 1) + f(i - 2)
f(1) = 1
f(2) = 1
兔子数量的数列：
1 2 3 4 5 6 ...
1 1 2 3 5 8 ...
fab(n) = fab(n - 1) + fab(n - 2)
递归的缺陷： 可能存在重复计算问题
*/
public class Demo4 {
public static void main(String[] args) {
int count = countRabbit(20);
System.out.println(count);
//测试利用循环求解斐波那契数列的值
int fab = fab(20);
System.out.println(fab);
}
/*
求解第n个月的兔子数量
*/
public static int countRabbit(int n) {
//出口条件
if (n == 1 || n == 2) {
return 1;
}
return countRabbit(n - 1) + countRabbit(n - 2);
}
/*
当利用递归求解，出现重复计算的时候，我们可以使用循环来替代递归(这种直接的转化主要针对比较简单的情况)
n：代表要求解的第n项的菲波那切数列的项数
*/
public static int fab(int n) {
// 就用来存储已经得到结果的第n项的斐波那契数列的值
int[] tmp = new int[n + 1];
tmp[1] = 1;
tmp[2] = 1;
for (int i = 3; i <= n; i++) {
tmp[i] = tmp[i - 1] + tmp[i - 2];
}
return tmp[n];
}
}