数据结构之递归

------------恢复内容开始------------

1.什么是递归

在java中，递归就是方法直接或者间接的调用自己本身。
核心思想：就是分治算法，将大问题分解成小问题求解
优缺点：

优点缺点

代码简洁、可读性好
递归调用，占用空间大

递归太深，容易发生堆栈溢出

容易出现重复计算

2.常用的递归场景：

各种数学问题，如八皇后问题、汉诺塔、阶乘问题、迷宫问题以及球和篮子的问题
各种算法问题，如归并排序、快速排序、二分查找、分治算法等
将栈解决的问题转化为递归解决的问题

3.递归使用需要满足的三个条件：

存在截止条件，即有明确的递归结束条件
求出递归公式
可以将大问题分成若干个小问题，每个小问题的求解思路和大问题一样，除了数据规模上存在差异

4.递归常见的思维误区以及注意事项区

不要尝试利用大脑将递归的每一步都搞清楚，这将会越搞越乱。我们只需要明确递归两要素即可：递归结束条件和递归公式
每次执行一个方法时，会创建一个新的受保护的独立栈空间
方法的局部变量是相互独立的，不存在相互影响。其中，若局部变量是引用类型（数组），则会共享该引用类型的数据

5.递归常见的问题

堆栈溢出：
产生原因：函数调用时，会将临时变量存储到堆栈中。每次调用，都会将临时变量保存到栈中。而系统站或者虚拟机栈的空间有限。如果求解数据规模太大，会造成堆栈溢出，进而导致系统崩溃
解决方法： 1. 限制递归深度。局限：当前栈内存空间的大小与当前线程剩余的占空间大小有关，无法事先估算，只适用于递归深度比较小的场景。

2.将递归代码改成非递归代码，即循环迭代（递归的天敌和好友）。不需要额外的空间和时间

存在重复计算：
解决方法：利用散列表，保存已经调用过的函数，然后每次调用会先进行检查
时间和空间复杂度高：
解决方法：改成迭代循环

6.递归的优化

重复计算的优化：利用散列表
利用尾递归进行优化：函数调用时，直接返回调用结果，然后把调用结果当作参数，放入到函数中。避免对局部变量的存储。例如

用线性递归实现Fibonacci函数：
1 public int FibonacciRecursive(int n)
2 {
3     if( n < 2)
4         return n;
5     return (FibonacciRecursive(n-1)+FibonacciRecursive(n-2));
6 }
用尾递归来实现Fibonacci函数：
public int FibonacciRecursive(int n,int a,int b){
　　if(n == 0){
　　　　return 0;
}
return FibonacciRecursive(n - 1,b,a + b);}
优点：不需要返回去，省区了对栈内存的消耗。

------------恢复内容结束------------