问题描述
"从简单的问题学算法"，从1到100求和，学习算法的基本思维，本文是系列的第二篇文章。从1到100求和学算法思维（一）上一篇，为大家介绍了如何一步步的提出方案，发现问题，解决问题，螺旋式上升的思路来解决问题，强调了提出问题远比解决问题更重要。
本文将为大家介绍一种新的算法思维即递归算法，递归算法是程序设计中的一种非常重要的算法，因其抽象程度较高，不易理解，因此对于大部分初学者来说 都是比较困难的，学会递归算法解决问题的基本思路，并灵活运用其分析问题、解决问题。
解决方案
递归算法的核心是递归函数，那递归函数与一般的函数有什么不同呢？首先来看函数的一般定义形式为:
void foo(){}
为描述方便，形参、函数题、返回值类型等均省略。函数主要有函数名、一对小括号、一对大括号以及返回值类型这几部分构成。而递归函数与一般函数最大的区别在于函数体里面调用自己即：
void foo(){
foo();
}
上面的函数并没有写完整，如果是这样的形式，会发现函数的调用永远不会结束，即陷入死循环，最终会因为栈溢出而报错，大家可以在自己的电脑上亲自测试感受一下。
因此递归函数除了满足上面第一条特征外，还需要有函数调用结束的判断条件，即函数什么情况下会返回。
接下来，我们将设计这样的一个递归函数，给定初始整数100，然后每次递减1，当最后递减的整数值为0时返回，如下：
100
99
···
2
1 (此时递归结束，返回)
如何设计函数满足上面的要求，分三步走：
（1）写出递归的一般形式，即
void foo(){
foo();
}
（2）函数有初始整数值100，且每次递减1，可将上述继续修改为：
void foo(int n){ // 初始值100
foo(n-1); // n递减1即n-1
}
（3）编写递归的结束条件，根据需求当整数递减为0时返回。
void foo(int n){ // 初始值100
if ( n == 1)
return ;
foo(n-1); // n递减1即n-1
}
切记，如果递归函数没有结束条件将会陷入无限循环，最终会因为栈溢出而终止程序。
此时再运行的时候，程序就不会出错：
接下来在这个基础上，再增加一点打印信息，即打印每一次减小后的整数。
与
这两种方式有什么区别？foo(n-1)在System.out.println(n)的上面和下面有什么不一样的地方？
从测试的结果可以看到，
当foo在下面的时候，打印的是100，99，···，1。
当foo在上面的时候，打印的是1，2，···，100。
深入的理解这一点，对于理解递归具有非常的意义，同时今后也能设计非常灵活的算法。这两种方式在今后的学习都会用到，因此需要加以区别。
当打印信息在foo函数上面的时候，意味着先打印整数再递减，由于初始值为100，即先打印100再递减，以此类推。
当打印信息在foo函数下面，则意味着先递减再打印，那是否意味着递减1，就打印一个整数呢？这也是非常重要的一点，同时也是递归与众不同的地方。
如果是递减1就打印一个整数，那打印的结果为100，99，···，1这和上面的打印是一样的结果，因此显然不是这样。递归的神奇地方就在于，从100一直递减，直到递减为1时结束，然后才执行打印操作。因此打印的结果就是1，2，···，99，100。
现在，可以回到解决1到100求和问题了。利用递归的思想来求解就是让100一直递减到0结束，对于每一次递减后的整数，将其累加起来。因此可以快速的写出下面的代码：
当整数n一直从100递减到1时结束，按照之前的分析是依次打印1，2，···，100，此时将每一次递减后的整数累加到sum变量中，即可完成求和。
结语
本文介绍了什么是递归算法，递归函数设计的注意事项，如何一步步设计递归函数，最后利用递归算法解决了1到100求和问题。递归的思想较为抽象，学习的过程也是从模仿到自己设计，初学时不必追求递归的原理，随着学习的逐步深入慢慢的就会理解。
上述的递归算法是否可以进一步改进呢？欢迎留言，同时也为大家准备了一道习题。
习题：利用递归算法完成1*2*····*100.
