不使用循环递归的方式求1~n的和

今天在牛客网上看到一道面试题，感觉很有意思自己也思考了很长时间，希望可以分享下来，题目是这样描述的：

求1+2+3+...+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

刚开始的时候我想1+2+3+…+n不正好是等差数列吗？直接使用等差数列的求和公式不就可以吗？n*(n+1)/2，但是公式中依然有乘法啊，所以这个想法被pass掉。
后来我就想到了逻辑运算中的逻辑与&&操作，这个操作有一个特性就是短路特性，如果当前面的条件成立的时候后面的条件就不再执行了，如果我用前面一个条件代表递归结束，后面一个条件代表递归执行，不正好可以实现这个目的吗？于是我写出了下面的代码：

size_t Sum_Solution(size_t n)
{
    //当n为0的时候只执行前面的条件，结果为false
    //当n大于0的时候可以执行到后面的条件，实现递归计算，
    int sum=n;
    bool ret=(n > 0) && ((sum += Sum_Solution(n-1)) > 0);
    return sum;
}

当然了，还有其他的解决方法了。。。

方法一.利用构造函数的方法实现循环

如果我们一次创建n个对象，每次创建对象都会调用一次构造函数，而每调用一次构造函数循环变量就增加1，而sum也随之递增，这不就利用构造函数达到循环的效果了吗？

//利用构造函数模拟循环
class Sum_Solution
{
public:
    Sum_Solution()  //构造函数控制循环的次数
    {
        ++_i;
        _sum += _i;
    }
    static void InitData()
    {
        _i=0;
        _sum=0;
    }
    static size_t GetSum()  //返回最终结果
    {
        return _sum;
    }
private:
    static size_t _i;
    static size_t _sum;
};
//使用静态的变量可保证累加的效果
size_t Sum_Solution::_i=0;
size_t Sum_Solution::_sum=0;

void testSum_Solution()
{
    int n=100;
    Sum_Solution::InitData();//调用初始化函数给变量_i，和_sum赋初值
    Sum_Solution *tmp=new Sum_Solution[n];
    delete[]tmp;
    size_t ret=Sum_Solution::GetSum();
    cout<<ret<<endl;
}

方法二.利用虚函数的方法模拟递归

所谓的递归就是要有实现递归的函数以及递归结束的条件，如果可以使得实现递归的函数和判断递归结束的条件用两个类实现就可以解决这个问题了。

//使用虚函数模拟递归实现
class A
{
public:
    virtual size_t GetSum(size_t n)  //递归结束的条件
    {
        return 0;
    }
};
A *arr[2];
class B:public A
{
public:
    virtual size_t GetSum(size_t n)  //递归的实现
    {
        return arr[!!n]->GetSum(n-1)+n;
    }
};
void testSolution()
{
    //n==0,调用A::GetSum(),当n != 0的时候调用B::GetSum()
    int n=100;
    A a;
    B b;
    arr[0]=&a;
    arr[1]=&b;
    size_t sum=arr[1]->GetSum(n); 
    cout<<sum<<endl;
}

方法三.使用函数指针的方式来解决

如果面试官不让你使用C++的方法该怎仫办？函数指针可以很好的解决这个问题。

//利用函数指针来实现
typedef size_t (*GetSum)(size_t);
size_t Finish(size_t n)
{
    return 0;
}
size_t Sum_Solution(size_t n)
{
    static GetSum arr[2]={Finish,Sum_Solution};
    return n+arr[!!n](n-1);
}

在这里就分享结束啦~~~