方法递归调用
大约 2 分钟
方法递归调用
介绍
递归就是方法自己调用自己,每次调用时传入不同的变量递归有助于编程者解决 复杂问题,同时可以让代码变得简洁
递归能解决什么问题?
- 各种数学问题如: 8皇后问题,汉诺塔, 阶乘问题,迷宫问题,球和篮子的问题(google编程大赛)
- 各种算法中也会使用到递归,比如快排,归并排序,二分查找,分治算法等
- 将用栈解决的问题-->递归代码比较简洁
递归的重要规则
- 执行一个方法时,就创建一个新的受保护的独立空间(栈空间)
- 方法的局部变量是独立的,不会相互影响,
- 如果方法中使用的是引用类型变量(比如数组),就会共享该引用类型的数据.
- 递归必须向退出递归的条件逼近,否则就是无限递归,出现 StackOverflowError,死龟了
- 当一个方法执行完毕,或者遇到 return,就会返回,遵守谁调用,就将结果返回给谁,同时当方法执行完毕或者返回时,该方法也就执行完毕
演示
演示一:求斐波那契数
请使用递归的方式求出斐波那契数1,1,2,3,5,8,13...给你一个整数n,求出它的值是多少
- 提示: 斐波那契数就是后面的一个数就是前面两个数的和,例如:
- 1 + 1 = 2;
- 1 + 2 = 3;
- 2 + 3 = 5;
- 3 + 5 = 8;
- 5 + 8 = 13;
public class Hello {
public static void main(String[] args){
T t1 = new T();
int n = 0;
int res = t1.fibonacci(n);
if(res != -1){
Sytem.out.println("当 n=" + n + " 对饮的斐波那契数为" + res);
}
}
}
class T {
public fibonacci(int n){
if(n >= 1){
if(n == 1 || n == 2){
return 1;
} else {
return fibonacci(n - 1) + fibonacci(n - 2);
} else {
System.out.println("要求输入的 n >= 1 的正整数");
return -1;
}
}
}
}
演示二:猴子吃桃
有一堆桃子,猴子第一天吃了其中的一半,并再多吃了一个! 以后每天猴子都吃其中的一半,然后再多吃一个。当到第10天时,想再吃时 (即还没吃)发现只有1个桃子了。问题: 最初共多少个桃子?
演示三:老鼠出迷宫
演示四:汉诺塔
演示五:八皇后