数据结构与算法之递归
简介
递归就是方法自己调用自己，每次调用时传入不同的参数，递归有助于解决复杂的问题，同时也能使代码变得简洁。
递归调用机制
有编程的基础的同学，应该知道递归的写法，下面我将使用两个小案例来分析递归的调用机制。
案例一 递归打印数字：
public static void main(String[] args) {testRecursion(5);}public static void testRecursion(int n) {if (n > 2) {testRecursion(n - 1);}System.out.println("n=" + n);}
输出结果：
n=2n=3n=4n=5
递归打印数字流程示意图：
流程分析：
- 当递归方法调用自己时，就会在栈中开辟一个独立的空间；
- 每个空间的基本数据类型变量，是独立的，互不影响，如果变量是引用类型，则会指向同一个内存地址；
- 递归调用时，直到方法执行完毕，或者遇到
return语句，才会结束； - 上述案例，
main方法调用testRecursion传入参数n=5，当n大于2时，会递归调用testRecursion。当递归到n不大于2时，会依次执行递归调用后面的语句，此处是System.out.println("n=" + n)。直到方法执行完毕。
案例二 递归计算阶乘：
public static void main(String[] args) {int factorial = factorial(3);System.out.println("factorial=" + factorial);}public static int factorial(int n) {if (n == 1) {return n;} else {return factorial((n - 1)) * n;}}
输出结果：
factorial=6
递归使用场景
- 可用于解决各种数学问题，例如：汉诺塔、阶乘、迷宫回溯等；
- 应用到算法中，例如：快速排序、归并排序、二分查找、粉质算法等；
- 遇到复杂的数据结构时，可使用递归，可使代码更简洁；
递归需要遵守的规则
- 执行一个方法时，就创建了一个新的，受保护的独立空间，也就是栈；
- 方法的局部变量是独立的，不会相互受到影响，例如上面演示的案例所用到的参数
n，只针对基本数据类型； - 如果方法中使用的是引用类型的变量，就会共享该引用类型的数据；
- 递归方法必须要有退出的条件，否则就会出现无限递归，最终抛出
StackOverflowError异常； - 当一个方法执行完毕，或者遇到
return语句，就会返回结果，遵守谁调用就会将结果返回给谁，同时当方法执行完毕或者返回时，该方法也就执行完毕；
╰半夏微凉°
忘是亡心i
刺骨的言语ヽ痛彻心扉
不念不忘少年蓝@
太过爱你忘了你带给我的痛
港控/mmm°
还没有评论，来说两句吧...