JAVA递归试题库

《JAVA递归试题库》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、递归一基础知识<1>递归中每次循环都必须使问题规模有所缩小。<2>递归操作的每两步都是有紧密的联系，如在“递归”的“归操作时”，前一次的输出就是后一次的输入。<3>当子问题的规模足够小时，必须能够直接求出该规模问题的解，其实也就是必须要有结束递归的条件。二递归要解决什么问题呢?1不同的方法体之间的传递publicstaticvoidmain(String[]args){g();}privatestaticvoidg(){f(3);}privatestaticintf(inti){returni+k(i)

2、;}privatestaticintk(inti){returni;}2相同的方法体不同方法名之间的传递publicstaticvoidmain(String[]args){inti=g(4);System.out.println(i);}privatestaticintg(inti){returni*g1(3);}privatestaticintg1(inti){returni+g2(2);}privatestaticintg2(inti){returni*g3(1);}privatestaticin

3、tg3(inti){returni;}3看一看得出其实功能相同所以直接使用递归publicstaticvoidmain(String[]args){inti=g(4);System.out.println(i);}privatestaticintg(inti){if(i==1){returni;}returni*g(i-1);}根据2与3的比较明显的看得出使用递归明显的缩短了代码的使用量4递归的使用框架返回值类型f(形参){if(终止条件){return结果;}else{returnf(形参递减或者递增

4、);}}5递归算法一般用于解决三类问题：(1)数据的定义是按递归定义的。（Fibonacci函数）(2)问题解法按递归算法实现。这类问题虽则本身没有明显的递归结构，但用递归求解比迭代求解更简单，如汉诺塔(3)数据的结构形式是按递归定义的。如二叉树、广义表等，由于结构本身固有的递归特性，则它们的操作可递归地描述。三经典案例1斐波纳契数列斐波那契数列（Fibonaccisequence），又称黄金分割数列、因数学家列昂纳多·斐波那契以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：0、1、1

5、、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*）publicstaticintf(intx){if(x==0){return0;}if(x==1

6、

7、x==2){return1;}returnf(x-1)+f(x-2);}2阶乘publicstaticintf(intx){if(x==1){return1;}else{returnx*f(x-1);}}3全排列4汉诺塔publicst

8、aticvoidhanoi(intn,charorigin,charassist,chardestination){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,de

9、stination);}}四试题：I递归定义33.递归的框架题意试数字符串反转/*我们把“cba”称为“abc”的反转串。题意就是对字符串的反转求一个串的反转串的方法很多。下面就是其中的一种方法，代码十分简洁（甚至有些神秘），请聪明的你通过给出的一点点线索补充缺少的代码。把填空的答案（仅填空处的答案，不包括题面）存入考生文件夹下对应题号的“解答.txt”中即可。*/思路就是每次保存最后一位并且放在第一个上返回或者每次保存第一个并且放在最后一个publicclassDemo03{publicstaticS

10、tringreverseString(Strings){if(s.length()<2

11、

12、s==null)returns;//每一次将第一位放在最后，将第二位放在倒数第二位然后进行递归returnreverseString(s.substring(1))+s.charAt(0);//returns.charAt(s.length()-1)+reverseString(s.substring(0,s.length()-1));}publics