递归
}
private static void g() { }
private static int f(int i) { }
private static int k(int i) { }
return i; return i+k(i);
f(3);
一 基础知识
<1> 递归中每次循环都必须使问题规模有所缩小。
<2> 递归操作的每两步都是有紧密的联系，如在“递归”的“归操作时”，前一次的输出就是后一次的输入。
<3> 当子问题的规模足够小时，必须能够直接求出该规模问题的解，其
实也就是必须要有结束递归的条件。
二 递归要解决什么问题呢?
1 不同的方法体之间的传递
public static void main(String[] args) {
g();
2 相同的方法体 不同方法名之间的传递
public static void main(String[] args) { }
private static int g(int i) { }
private static int g1(int i) { }
private static int g2(int i) { }
private static int g3(int i) {
return i*g3(1); return i+g2(2); return i*g1(3); int i = g(4);
System.out.println(i);
1 / 44
}
return i;
3 看一看得出 其实功能相同所以直接使用递归
public static void main(String[] args) { }
private static int g(int i) { }
if(i == 1){ }
return i*g(i-1);
return i; int i = g(4);
System.out.println(i);
根据 2 与 3 的比较明显的看得出 使用递归明显的缩短了代码的使用量
4 递归的使用框架 返回值类型 f(形参){
}
if(终止条件){ } else{ }
return f(形参递减或者递增); return 结果;
5递归算法一般用于解决三类问题：
(1)数据的定义是按递归定义的。（Fibonacci函数） (2)问题解法按递归算法实现。
这类问题虽则本身没有明显的递归结构， 但用递归求解比迭代求解更简单，如汉诺塔 (3)数据的结构形式是按递归定义的。 如二叉树、广义表等，
由于结构本身固有的递归特性，则它们的操作可递归地描述。
三 经典 案例
1 斐波纳契数列 斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列以如下被以递归的方法定义：F（0）=0，F（1）=1，F（n）=F(n-1)+F(n-2)（n≥2，n∈N*） public static int f(int x){
if(x == 0){ }
if(x == 1 || x == 2){
return 1; return 0;
2 / 44
}
}
return f(x-1)+f(x-2);
2 阶乘 public static int f(int x){
}
if(x == 1){ }
return 1; return x*f(x-1); }else{
3全排列 4汉诺塔
public static void hanoi(int n, char origin, char assist, char destination) { }
if (n == 1) {
System.out.println(\ + origin + \ + destination); } else {
hanoi(n - 1, origin, destination, assist);
System.out.println(\ + origin + \ + hanoi(n - 1, assist, origin, destination); }
destination);
四 试题：
I 递归定义
33.递归的框架 题意试数 字符串反转
/*
我们把“cba”称为“abc”的反转串。 题意就是 对字符串的反转
求一个串的反转串的方法很多。下面就是其中的一种方法，代码十分简洁（甚至有些神秘）， 请聪明的你通过给出的一点点线索补充缺少的代码。
把填空的答案（仅填空处的答案，不包括题面）存入考生文件夹下对应题号的“解答.txt”中即可。 */
思路 就是每次保存最后一位并且放在第一个上返回 或者 每次保存第一个并且放在最后一个
public class Demo03 {
public static String reverseString(String s){
if(s.length()<2||s==null) return s;
//每一次将第一位放在最后，将第二位放在倒数第二位然后进行递归 return reverseString(s.substring(1))+s.charAt(0);
// return s.charAt(s.length()-1)
+reverseString(s.substring(0,s.length()-1)); }
3 / 44
}
public static void main(String[] args){ }
String s = \;
String ss = reverseString(s); System.out.println(ss);
运行结果：
654321
132、递归 把串s中第一个出现的数字的值返回。
如果找不到数字，返回-1 例如： s = \ 则返回2 s = \ 则返回8 s = \ 则返回-1
public static int getFirstNum(String s) {
}
public static void main(String[] args) { }
String s = \;
System.out.println(getFirstNum(s)); if(s==null || s.length()==0) return -1; char c = s.charAt(0);
if(c>='0' && c<='9') return c-'0'; //填空 return getFirstNum(s.substring(1)); //填空
102.递归的定义 试数 连续数
以下程序打印出0~9的数字，请补充缺少的代码。 */
public class 递归连续数 {
public static void f(int begin, int end) { if(begin>end) return; // 填空 System.out.println(begin); f(begin + 1, end); }
public static void main(String[] args) { f(0, 9); }
}
运行结果: 0 1 2
4 / 44
相关推荐：
loading