JAVA递归试题库.docxVIP

递归一基础知识1 递归中每次循环都必须使问题规模有所缩小。 2 递归操作的每两步都是有紧密的联系，如在“递归”的“归操作时”，前一次的输出就是后一次的输入。3 当子问题的规模足够小时，必须能够直接求出该规模问题的解，其实也就是必须要有结束递归的条件。二递归要解决什么问题呢?1 不同的方法体之间的传递publicstaticvoid main(String[] args) {g();}privatestaticvoid g() {f(3);}privatestaticint f(int i) {return i+k(i);}privatestaticint k(int i) {return i;}2 相同的方法体不同方法名之间的传递publicstaticvoid main(String[] args) {int i = g(4);System.out.println(i);}privatestaticint g(int i) {return i*g1(3);}privatestaticint g1(int i) {return i+g2(2);}privatestaticint g2(int i) {return i*g3(1);}privatestaticint g3(int i) {return i;} 3 看一看得出其实功能相同所以直接使用递归publicstaticvoid main(String[] args) {int i = g(4);System.out.println(i);}privatestaticint g(int i) {if(i == 1){return i;}return i*g(i-1);}根据 2 与 3 的比较明显的看得出使用递归明显的缩短了代码的使用量 4 递归的使用框架返回值类型 f(形参){if(终止条件){return结果;}else{return f(形参递减或者递增);}}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*）publicstaticint f(int x){if(x == 0){return 0;}if(x == 1 || x == 2){return 1;}returnf(x-1)+f(x-2);}2 阶乘publicstaticint f(int x){if(x == 1){return 1;}else{return x*f(x-1);}}3全排列4汉诺塔publicstaticvoid hanoi(int n, char origin, char assist, char destination) {if (n == 1) {System.out.println(Direction: + origin + --- + destination); } else {hanoi(n - 1, origin, destination, assist); System.out.println(Direction: + origin + --- + destination);hanoi(n - 1, assist, origin, destination); } }四试题：I 递归定义33.递归的框架题意试数字符串反转/*我们把“cba”称为“abc”的反转串。题意就是对字符串的反转求一个串的反转串的方法很多。下面就是其中的一种方法，代码十分简洁（甚至有些神秘），请聪明的你通过给出的一点点线索补充缺少的代码。把填空的答案（仅填空处的答案，不包括题面）存入考生文件夹下对应题号的“解答.txt”中即可。 */思路就是每次保存最后一位并且放在第一个上返回或者每次保存第一个并且放在最后一个publicclassDemo03 {publicstatic String reverseString(String s){if(s.length()2||s==null) return s;//每一次将第一位放在最后，将第