从1到100求和学算法思维（四）

欢迎点击「算法与编程之美」↑关注我们！

本文首发于微信公众号："算法与编程之美"，欢迎关注，及时了解更多此系列文章。

上一篇通过递归算法实现整数n从100逐渐递减到1，然后将每一个递减的整数累加到变量sum中，这是一种单向的递减操作，如图：

单向的递减最主要的问题在于下降速度过慢，是否有更快的遍历速度呢？相信聪明的您可能已经发现，那就是使用双向的速度来遍历。

思路已经有了，那接下来如何利用代码编程实现呢？需要注意的地方有哪些呢？

单向递减我们的做法是：

void foo(int n){

    if( n==0) return ;

    foo(n-1);

}

为描述方便，其余部分略过。要想实现双向，就必须得有两个控制变量。

void foo(int i, int j){

    foo(i+1, j-1);

}

让变量i实现自增，变量j实现自减，但是什么时候递归结束呢？答案就是i超过j的时候，得出代码为：

void foo(int i, int j){

    if( i > j) return ;

    foo(i+1, j-1);

}

注：在使用递归函数的时候，切记不要忘记递归结束的条件。

学会了变量i和变量j的双向控制，最后将每一次递减后的变量i和变量j累加到sum即可。

本文为大家介绍了一种新的思维方式来实现递归，可能大家在阅读本文的时候觉得很简单，但是这种思维却是今后解决复杂递归问题的基础，如果缺乏这种思维方式，复杂的问题一定难以解决。这也是本系列文章要为大家传达的核心理念：透过简单的问题来学习复杂的算法思维，帮助大家更好的理解复杂问题。

更多精彩文章：