递归与非递归实现

第六章实验报告
一．题目要求
（1）实验题目
题目1：将非负十进制整数n转换成b进制。（其中b=2~16）
题目2：任何一个正整数都可以用2的幂次方表示。例如：
　　　　137=2⁷⁺²3+2^0　　　　
同时约定幂次方用括号来表示，即ab 可表示为a（b）。
　　由此可知，137可表示为：
　　　　 2（7）+2（3）+2（0）
进一步：7= 2²⁺²⁺²0 （21用2表示）
　　　　 3=2+2^0
所以最后137可表示为：
　　　　 2（2（2）+2+2（0））+2（2+2（0））+2（0）
　　又如：
　　　　 1315=2^10 +2^8 +2^5 +2+2^0
所以1315最后可表示为：
　　 2（2（2+2（0））+2）+2（2（2+2（0）））+2（2（2）+2（0））+2+2（0）
　　输入：正整数（n≤20000）
输出：符合约定的n的0，2表示（在表示中不能有空格）
输入格式 Input Format
一个正整数
输出格式 Output Format
符合约定的n的0，2表示（在表示中不能有空格）
样例输入 Sample Input
73
样例输出 Sample Output
2(2(2)+2)+2(2+2(0))+2(0)

（2）实验目的

掌握递归程序设计的方法。明确递归的概念，通过对问题的分析，找出递归关系以及递归出口以对问题进行递归结构设计；
掌握递归程序转换为非递归程序的方法。
二．问题分析
2.1 题目一
①递归实现：
此题需要将一个任意的非负十进制数转换为任意的2—16进制的表示，可分为两部分来实现，将转化为2—9进制分为一部分利用void hift_a(n,x)函数来实现，因为10—16进制会涉及字符串的输出等问题，所以将10—16进制用另外的函数void Shift_A(int n,int y)来实现。关于void shift_a(n,x)函数，将非负十进制n除以其需要转化的进制数x（2–9），然后不断取余数c，将n/x的值再次赋给n进行计算，直到n=0时结束递归，将其倒序输出。关于void Shift_A(int n,int y)函数，将输入的非负十进制数n转化为需要的进制数y（10–16），先定义一个字符串str，用来输出相应的进制。将n/y的余数赋值给j,若j=0，则输出字符串跳出循环，若j >0且j<10，输出字符串str+=(j+‘0’)；若j>=10,输出字符串str += (‘A’+(j-10))，然后不断取余数j，将n/y的值再次赋给n进行计算，直到j=0时结束递归，将其输出。
此外还需要考虑，若非负十进制数n小于需要转换的进制数，则不能实现进制转换。
递归函数如下：(递归出口为n=0)
(Shift_a(n,x),&n≠0
return ,&n=0) (计算2—9进制转换)
█(Shift_A(n,x),&n≠0
return ,&n=0)（计算10—16进制转换）
②非递归实现：
非递归实现用while循环来解决。定义字符数组a[]，把数n赋值给b，当b/x大于0时，计算a[i]=b%x，不断地将b/x赋值给b，当结果为0时，跳出循环并进行倒序输出。
2.1 题目二
①递归实现
定义一个fun（）函数，定义输入的整数为n。设 s为2的次方的值，t=为指数的值，若n=1，则直接输出2（0）即2的零次方；若n=2直接输出2，即2的一次方；否则通过不断s*2找出大于n时的指数，不断t++，找到该数后将t-1的值赋给t，从2的t次方不断地开始计算，如果 n==s/2，即刚好为2的某次方的值，则直接输出2（fun（t）），否则，fun(n-s/2)进行一步步计算，直到得出值为止。
递归函数如下：（递归出口为n=0或n=1）
(fun（int n），n>2
return ,n=2
return ,n=1

三．调试及测试截图
（一）进制转化问题
①运行开始界面如下
递归与非递归实现
②输入一个非负十进制数进行2—16进制的转化

递归与非递归实现
③调试（以十进制数15调试为例）
15的二进制调试：

15的三进制调试：

15的四进制调试：

因为15<16，所以15的十六进制无法表示

（二）2的幂次方表示问题
1.开始界面如下：

2.输入整数得出结果，选择是否继续：
递归与非递归实现
3.调试（以整数18为例）

四．个人总结
（1）开始时对递归问题的递归出口和函数体不太熟悉，导致花费了较多的时间，最后通过反复思考查阅资料，对递归有了更加清楚的认识，递归问题要分解为若干个规模较小的与原问题形式相同的子问题，这些子问题可以用相同的解题思路来解决。
（2）通过递归与非递归方法的使用，让我进一步认识到递归方法的优势，递归方法相对于非递归的方法更加简洁好实现，很清晰的描述了算法的步骤，对于不知道循环次数的函数，调用递归求解具有更大的优势。
（3）通过对递归栈的调用的实践，让我对递归程序有了更加深入的理解。在刚开始进行递归设计时，让我觉得难度很大，通过对问题的分解，先设计递归出口，想清楚内部结构，然后再设计递归方法，这样，将会使程序设计的实现更加容易。

参考资料： https://blog.****.net/sinat_38052999/article/details/73303111
https://blog.****.net/poiuyds/article/details/81196916

递归与非递归实现

相关推荐