面试算法之递归和循环

        我们在抽象算法问题时，如果需要重复多次的计算相同的问题，可以用递归或循环。递归方式是在函数内部调用自身函数实现堆栈上的递归，直到终止条件结束为止；循环方式是通过设置计算的初始值和终止条件，在一个范围内循环运算。比如我们求1+2+3+...+n的值，我们可以用递归或者循环的方式求解(甚至数学功底好的可以想到背后的数学公式和定理；这个比较简单n*(n+1)/2)；

        递归算法如下：

int add_1toN_recursive(int n)
{       
        return n <= 1 ? 1 : n + add_1toN_recursive(n-1);
}

       循环算法如下：

int add_1toN_iterative(int n)
{
        int value = 0;
        int i = 0;
        for (i = 1; i <= n; ++i)
                value+=i;
        return value;
}

        通常递归代码比较简洁，上面就可以看出，在树的前序、中序、后序遍历算法中，递归算法明显比循环算法简单易懂的多，面试时如果面试官没有特别要求，尽量使用递归。

        但是递归有明显的缺点，因为递归是函数调用自身，每一次函数调用，需要压栈保存参数、临时变量和返回地址，不但需要时间，而且因为每个进程的栈空间是有限的，

       可以很明显的看出，递归和循环算法的优缺点，递归代码简洁易懂，但是性能跟循环比差，递归受堆栈大小限制，过度的递归次数可能导致堆栈溢出，所以项目中很多设备上是不建议使用递归的。