递归实现十进制与二进制的转换

欢迎去我的个人博客转转：
Uncle_drew
早在之前学dfs的时候，师父就教我说用递归写二进制的转换。当时也是碰巧写了出来，进来遇见这类问题时，发现这样转换的人确实少，我还是记录一下，免得以后再忘，有兴趣的也可以看一下啦。
二进制：二进制是计算技术中广泛采用的一种数制。二进制数据是用0和1两个数码来表示的数。它的基数为2，进位规则是“逢二进一”，借位规则是“借一当二”，由18世纪德国数理哲学大师莱布尼兹发现。当前的计算机系统使用的基本上是二进制系统，数据在计算机中主要是以补码的形式存储的。计算机中的二进制则是一个非常微小的开关，用“开”来表示1，“关”来表示0。
20世纪被称作第三次科技革命的重要标志之一的计算机的发明与应用，因为数字计算机只能识别和处理由‘0’.‘1’符号串组成的代码。其运算模式正是二进制。19世纪爱尔兰逻辑学家乔治布尔对逻辑命题的思考过程转化为对符号"0’’.’‘1’'的某种代数演算，二进制是逢2进位的进位制。0、1是基本算符。因为它只使用0、1两个数字符号，非常简单方便，易于用电子方式实现。
转换二进制我们用的都是余数短除法，就是要转换的数对二取余，然后除以二，直到这个数为0，再将余数倒序排列即可。不懂的话请看图示：

这里的倒序输出，我们想到的就是用数组或者栈来实现，这也是等很大众化的一种方式。我要介绍的这种方法采用的是递归，其实本质都是一样的，且不分优劣，这样写只单纯为了加深对递归的理解！

void Binary(int x)
{
	if(x==0)
			return ;
	Binary(x/2);
	cout<<x%2;
    return ;
}

这部分就是代码的核心。
我们手动执行一下就知道这种使用递归实现的巧妙之处了。

当x=10时：
此时x不为0，所以会执行Binary(x/2)
x/2=5
此时x不为0，所以会执行Binary(x/2)
x/2=2
此时x不为0，所以会执行Binary(x/2)
x/2=1
此时x不为0，所以会执行Binary(x/2)
x/2=0
此时x为0，所以会返回至上一次递归，而上一次递归中的x为1，所以输出x%2就是1，然后遇见return，返回上一次递归。上一次递归中x为2。
所以输出x%2就是0，然后遇见return，返回上一次递归。上一次递归中x为5。
所以输出x%2就是1，然后遇见return，返回上一次递归。上一次递归中x为10。
所以输出x%2就是10，然后遇见return，返回上一次递归。上一次递归中x为1。
此时这一次整体的递归就已经结束了，输出是1010，就是10的二进制形式。

这里比较难理解的就是每一次新的递归开始的时候，上一次的执行会“保留现场”。然后每一次递归结束后就返回上一层递归。注意：x==0时return这个判断条件必须存在，不然递归不会结束。
完整代码

#include<bits/stdc++.h>
using namespace std;
void Binary(int x)
{
	if(x==0)
			return ;
	Binary(x/2);
	cout<<x%2;
	return ;
}
int main()
{
	int n;
	while(~scanf("%d",&n))
	{
    	if(n==0)
		{
			puts("0");
			continue;
		}
		Binary(n);
		cout<<endl;
	}
	return 0;
}

这样的话会发现如果输入的数是负数会出现错误，只需要小小的改正一下就行

#include<bits/stdc++.h>
using namespace std;
void Binary(int x)
{
	if(x==0)
			return ;
	Binary(x/2);
	cout<<abs(x%2);
	return ;
}
int main()
{
	int n;
	while(~scanf("%d",&n))
	{
		if(n==0)
		{
			puts("0");
			continue;
		}
		if(n<0)
			cout<<'-';
		Binary(n);
		cout<<endl;
	}
	return 0;
}

这样就实现了任意整数转化成二进制的功能啦