【数据结构和算法】递归和非递归两种方式解决

一：非递归解法

我们先来看一道非常简单的题，在计算机中数字是由二进制位表示的，也就是说是由0和1组成的，如果我们要实现0和1之间的加法该怎么实现呢，他会有4种组合方式

1，0+0=00

2，0+1=01

3，1+0=01

4，1+1=10

我们发现一个很重要的规律，就是只有1+1有进位，其他的都没进位。所以我们判断有没有进位只需要判断a&b是否等于1即可，而a+b的值（不考虑进位）只需要计算a|b即可，看明白了这点，代码就呼之欲出了

     public int add(int a, int b) {
        int c = (a & b) << 1;//进位的值
        int d = a ^ b;//不考虑进位，相加的值
        return c | d;//或者 return c ^ d;
    }

a和b要么是1要么是0，所以这里最多也只有一个进位，很好理解。但我们计算二进制的加减法不光只有1个0或1，可能会有好多个1或0，那我们该怎么实现呢。比如a=13（1101），b=9（1001），我们该怎么计算a+b的结果。首先如果我们不考虑进位问题，那么a+b的运算会是下面这样

但实际上最前面和最后面的1都有了进位。

1，我们看到如果不考虑进位，那么a+b的结果其实就是a^b的结果，我们该怎么把进位问题也考虑在内呢，实际上只有1+1的时候才会出现进位，1+0或者0+0都不会出现进位，所以我们首先想到的是&运算

2，这里我们计算一下a&b的结果是1001，我们知道当&运算的结果为1的时候，说明参与&运算的两个都是1，既然两个都是1，那么相加的时候就肯定会有进位，所以他们进位的值实际上是10010（（a&b）<<1），然后在和0100相加就是我们要求的结果，10010+00100=10110，10110实际上就是22，也就是13+9的结果

3，但我们好像忽略了一个问题，就是这道题要求不能使用加减乘除符号，而上面我们分析的时候使用了加号，所以明显不行。通过上面的分析实际上我们已经发现了一个规律，就是a+b通过^和&运算之后又再执行相加操作，所以我们首先想到的是递归，我们来看下代码

public int Add(int a, int b) {
    if (a == 0 || b == 0)
        return a ^ b;
    return Add(a ^ b, (a & b) << 1);
}

第3行表示的是如果a==0就返回b，如果b==0就返回a，这种写法少了一个if语句的判断会更简洁

看一下运行结果

2，递归解法

上面的递归我们还可以改为非递归的方式

public int Add(int a, int b) {
    while (b != 0) {
        int temp = a ^ b;
        b = (a & b) << 1;
        a = temp;
    }
    return a;
}

这个也很好理解，每次计算的时候要对a和b进行重新赋值，然后再不断的循环，直到b等于0的时候停止循环，我们知道这里在运算的时候b表示的是进位的值，当b等于0的时候就表示没有进位，没有进位就退出循环，这就是使用位运算来实现加法。我们假设a=13，b=9来画个图加深一下理解

其实我们还可以不使用“+”、“-”、“*”、“/”符号来实现加法，减法，乘法，除法。具体可以看下

《不使用“+”,“-”,“×”,“÷”实现四则运算》

截止到目前我在公众号“数据结构和算法”中已经写了500多道算法题，其中部分已经整理成了pdf文档，目前总共有1000多页（并且还会不断的增加），大家可以免费下载
下载链接：https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码：6666

如果觉得有用就给个赞吧，还可以关注我的《牛客博客》查看更多的详细题解