迭代使用单一关系式,要考虑迭代次数或结束条件,分精确迭代(如最大公约数)和近似迭代(如求平方根)。

递推的递推变量和递推关系式(包含初始表达式,已知条件或结果,形成初始或边界条件),分为顺推(如斐波那契数列)、逆推(如五猴分桃)。

由编译器隐式实现一个函数调用栈,函数可以自己调用自己,参数之间相互迭代,所以使用递推法能解决的问题也可以通过递归法来解决,递推形成递归的一个阶段。递归调用语句前的部分,一般包含返回的边界条件及其它部分,可用一个局部变量及参数顺序迭代的循环来简单代替,即递推阶段;递归语句本身即回归阶段;递归调用语句的后面部分,可用一个局部变量及参数逆序迭代的循环来代替,但需要程序员自己维护一个显式栈来记忆参数、局部变量和返回值。

#include <stdio.h> void counting(int n) { int lv=10; lv*=n; if(n>3) return; printf("递归调用语句前面部分数据的顺序输出,参数n和局部变量lv:%d,%d\n",n,lv); counting(n 1); printf("递归调用语句后面部分数据的逆序输出,参数n和局部变量lv:%d,%d\n",n,lv); } int main() { counting(1); getchar(); return 0; } /* 递归调用语句前面部分数据的顺序输出,参数n和局部变量lv:1,10 递归调用语句前面部分数据的顺序输出,参数n和局部变量lv:2,20 递归调用语句前面部分数据的顺序输出,参数n和局部变量lv:3,30 递归调用语句后面部分数据的逆序输出,参数n和局部变量lv:3,30 递归调用语句后面部分数据的逆序输出,参数n和局部变量lv:2,20 递归调用语句后面部分数据的逆序输出,参数n和局部变量lv:1,10 */

其顺序如下:

递归算法一定要有初始值吗(算法递归参数)(1)

在逆序时为什么能够记忆参数值和局部变量?

函数调用时编译器使用了一个隐式栈,每一个函数使用一个栈帧来记录需要返回的函数地址、参数值、局部变量值。为了能够在出发后经过一系列调用能回到最初的出发地,需要一个后进先出的数据结构,这就是栈。

当递归用递推的循环来实现时,对于递归调用语句后面的部分,需要由程序员使用一个显式栈来记录参数值和局部变量,并逆序输出:

#include <stdio.h> #include <stack> using namespace std; typedef struct Node{ int para1; int lv1; }node; // 用一个结构体为保存参数与局部变量 void counting2(int n) { stack<node> sf; int init = n; while(n<=3) { int lv=10; lv*=n; printf("数据的顺序输出,参数n和局部变量lv:%d,%d\n",n,lv); node newnode = {n,lv}; sf.push(newnode); // 压栈操作,后面要逆序输出数据 n ; } while(!sf.empty()) { node newnode = sf.top(); printf("数据的顺序输出,参数n和局部变量lv:%d,%d\n",newnode.para1,newnode.lv1); sf.pop(); } } int main() { counting2(1); getchar(); return 0; } /* 数据的顺序输出,参数n和局部变量lv:1,10 数据的顺序输出,参数n和局部变量lv:2,20 数据的顺序输出,参数n和局部变量lv:3,30 数据的顺序输出,参数n和局部变量lv:3,30 数据的顺序输出,参数n和局部变量lv:2,20 数据的顺序输出,参数n和局部变量lv:1,10 */

如浮点数的二进制编码输出:

十进制整数部分:除二取余,逆向处理。

十进制小数部分:乘二取整,顺向处理。

#include<stdio.h> #include<math.h> #define N 16 void itobin(int n) { if(n==0) return; itobin(n/2); printf("%d",n%2); } void ftobin(double x) { for(int i=1;i<=N;i ) { x*=2; if(x>=1.0) { x-=1; printf("1"); } else printf("0"); } } void main() { int a[N 1],b[N 1],i,k=0,value; float x; double ipart; for(i=0;i<=N;i ) b[i]=0; printf("请输入一个十进制小数:"); scanf("%f",&x); x=modf(x,&ipart);//x为小数部分,ipart为整数部分 value=(int)ipart; while(value) // 十进制整数部分:除二取余 { b[k ]=value%2; value/=2; } float d = x; for(i=1;i<=N;i ) // 十进制小数部分:乘二取整 { x*=2; if(x>=1.0) { x-=1; a[i]=1; } else a[i]=0; } printf("二进制数:"); for(i=k;i>=0;i--) // 逆向输出整数 printf("%d",b[i]); printf("."); for(i=1;i<=N;i ) // 顺向输出小数 { if(a[i]==0) printf("0"); else printf("1"); } printf("\n"); itobin(ipart); printf("\n"); ftobin(d); getchar();getchar(); } /* 请输入一个十进制小数:22.62525 二进制数:010110.1010000000010000 10110 1010000000010000 */

附整数与浮点数的表示与存储:

对于浮点数的存储,却是用记阶法表示的,如:

1001.011B = 0.1001011B×2^ 100

-0.0010101B = -0.10101B×2^-10

可见,任一个二进制实数 N 均可表示为:

N=±S×2^P

其中, ±是该数的符号; S是N 的尾数;P是N的阶码。

因此,32位的单精度浮点数在计算机中可表示为:

由于指数(阶码)可以选用不同的编码(原码、补码等),尾数的格式和小数点位置也可以有不同的规定,因此早期计算机中浮点数的表示方法互不相同。

现代计算机中,一般都以IEEE 754标准存储浮点数,这个标准的在内存中存储的形式为:

对于不同长度的浮点数,阶码与小数位分配的数量不一样,如对于32位的单精度浮点数,数符分配是1位,阶码分配了8位,尾数分配了是23位:

递归算法一定要有初始值吗(算法递归参数)(2)

符号位:0表示正;1表示负;

偏移阶码e:e=指数的实际值 127。

假有一个浮点数10110010.001,则指数是7,阶码就要用7 127的二进制数表示,也就是:111 01111111 = 10000110

尾数使用原码表示,绝对值在1与2之间,其中1和小数点都是隐含的,并不直接表示。

递归算法一定要有初始值吗(算法递归参数)(3)

根据这个标准,我们来尝试把一个十进制的浮点数转换为IEEE754标准表示。

例如:178.125

先把浮点数分别把整数部分和小数部分转换成2进制:

整数部分用除2取余的方法,求得:10110010

小数部分用乘2取整的方法,求得:001

合起来即是:10110010.001

转换成二进制的浮点数,即把小数点移动到整数位只有1,即为:1.0110010001 * 2^111,111是二进制,由于左移了7位,所以是111

把浮点数转换二进制后,这里基本已经可以得出对应3部分的值了:

数符:由于浮点数是正数,故为0(负数为1)。

阶码 : 阶码的计算公式:阶数 偏移量, 阶码是需要作移码运算,在转换出来的二进制数里,阶数是111(十进制为7),对于单精度的浮点数,偏移值为01111111(127)[偏移量的计算是:2^(e-1)-1, e为阶码的位数,即为8,因此偏移值是127],即:111 01111111 = 10000110

尾数:小数点后面的数,即0110010001

最终根据位置填到对位的位置上:

递归算法一定要有初始值吗(算法递归参数)(4)

可能有个疑问:小数点前面的1去哪里了?由于尾数部分是规格化表示的,最高位总是“1”,所以这是直接隐藏掉,同时也节省了1个位出来存储小数,提高精度。

浮点数的二进制显示可以使用以下代码:

//位运算结合union输出int和float的二进制位 #include <iostream> using namespace std; union { //用于将浮点数的二进制位解析为int位输出 float input; int output; } data; void int2binary(unsigned n)//位运算只能用于整形 { unsigned b32 = 1<<31;//32位二进制,最高位是1,其它位是0 cout<<((n&b32)>>31)<<" ";//最高位与运算,移位后最高位输出 for(int i=1;i<32; i) { n=n<<1;//循环左移一位,用于最高位的与运算 cout<<((n&b32)>>31);//最高位与运算,移位后最高位输出 if(i==7) cout<<" "; if(i>8 && (i-7)%8==0) cout<<" "; } cout<<"\n"; } void float2binary(unsigned n) { unsigned b32 = 1<<31;//32位二进制,最高位是1,其它位是0 cout<<((n&b32)>>31)<<" ";//最高位与运算,移位后最高位输出 for(int i=1;i<32; i) { n=n<<1;//循环左移一位,用于最高位的与运算 cout<<((n&b32)>>31);//最高位与运算,移位后最高位输出 if(i%8==0) cout<<" "; } cout<<"\n"; } void main() { while(1) { int n; cout<<"please input a int:"; cin>>n; int2binary(n); cout<<endl; cout<<"please input a float:"; cin>>data.input; float2binary(data.output); cout<<endl; } } /* please input a int:178 0 0000000 00000000 00000000 10110010 please input a float:178.625 0 10000110 01100101 01000000 0000000 please input a int:-178 1 1111111 11111111 11111111 01001110 please input a float:-178.625 1 10000110 01100101 01000000 0000000 please input a int:134 0 0000000 00000000 00000000 10000110 please input a float: 10110010的阶数是7,最高位总是1,直接隐藏掉; 阶码=阶数 偏移量 =阶数 2^(e-1)-1 =阶数 2^(8-1)-1 =7 127 =134(10000110) */

要区别整数的补码和浮点数的符号位存储,虽然两者都是以高位0表示正数,1表示负数,但两者规定的规则却是不一样的,负整数是通过正整数的二进制自然码(最高位是0)取反 1而来的。而负浮点数却是直接取1而来的,阶码、尾数都是用自然码来表示的。

还需要注意的是,编码的数据在内存中的存储还要区分大头、小头,如以下小头存储:

递归算法一定要有初始值吗(算法递归参数)(5)

对比以下二进制表示,小端存储是从低位往高位存储的:

178

0 0000000 00000000 00000000 10110010 (低8位的16进制编码是B2)

-178

1 1111111 11111111 11111111 01001110(低8位的16进制编码是4E)

178.625

0 10000110 01100101 01000000 0000000(高8位的16进制编码是43)

:-178.625

1 10000110 01100101 01000000 0000000(高8位的16进制编码是C3)

-End-

,