递归求解进制转换
第六章作业
- 题目分析
基础要求:
题目：要求将10进制数转换为2-16进制。
递归实现：先找递归出口，我们采用除d倒取余的方法求进制转换，很明显递归出口就是当n等于0时，当n等于0时，递归结束，输出转换结果。再找递归公式，发现，每次递归循环时，只改变n的值，每次n的值都整除d。所以递归公式为change（str，n/d，d）。
非递归实现：将递归循环转换为while循环，循环退出条件为n=0；
n每次更新为n/d；
提高要求：
题目：输入：正整数（n≤20000）
输出：符合约定的n的0，2表示（在表示中不能有空格）
列如:1315最后可表示为：
2(2（2+2（0））+2）+2（2（2+2（0）））+2（2（2）+2（0））+2+2（0）
递归实现：
先找递归出口,根据题目分析，最后要转换成0,2的表示，所有的数都表示成0,2,特别2（1）表示成2。很明显，递归出口不只一个，当n等于0,1,2时各一个出口，输出2(0),2,2(2);
再找递归公式，对每个2的(m)中的m循环，用位运算，右移1
位，除二，取出所有有值的位，进行输出2（d）的格式，将每一个数都转换为0,2的格式。只要不是0,1,2的2进制都进行递归。
所以递归公式change（i>>1）仅当i&1>0;
- 递归模型和递归栈
基础要求：
递归模型：
{ return str； n==0
Change（str，n，d）
Return change（str，n/d，d）n！=0
}
递归栈：以5的二进制位例；
|
递归的层次 |
递归栈的状态(n的值) |
说明 |
|
1 |
Change（5） |
第一次递归入栈 |
|
2 |
Cahnge（2） Change（5） |
由第一层进入第二层 第二次递归，入栈 |
|
3 |
Change（1） Cahnge（2） Change（5） |
由第二层进入第三层 第三次递归，入栈 |
|
4 |
Change（0） Change（1） Change（2） Change（5） |
由第三层进入第四次递归，进入第四次递归，入栈 |
|
5 |
Change（1） Change（2） Change（5） |
得change（0）的值，出栈 |
|
6 |
Change（2） Change（5） |
得change（1）的值，出栈 |
|
7 |
Change（5） |
得change（2）的值，出栈 |
|
8 |
栈空 |
得change（5）的值，出栈 |
提高要求：
递归模型：change（n）{
Return ：Print（2（0））；n==0；
Return ：Print（2）；n==1；
Return ：Print(2(2)); n==2;
Change(n>>1) n!=0,1,2;
}
- 测试，调试，运行结果
基础要求：
余数赋值：
测试代码：
Scanner in=new Scanner(System.in);
int n=in.nextInt();
System.out.println(j.fuzhi(n));
运行结果：
提高要求：
测试：
进入第一层循环
进入第二层循环
进入第三次循环
在第三次循环中，3=2+1，则分别输出
进第四次循环
退循环：
退循环
退循环
-
总结
1）了解了递归和栈的关系，将无法求的先入栈，一直到递归出口，也就是能求解的递归公式，然后一个个出栈，倒着求目标函数。
- 非递归和递归的转化，一种是迭代的方法，例如进制转换的题，就是这样转变成非递归的。用while循环来表达递归的迭代。还有就是将其利用和栈的关系，用出栈和入栈来转换。
- 递归的关键就是寻找递归出口和递归公式，只要找到这两点，就能搭建出递归模型，进行求解。