【原】从1到100求和学算法思维（五）

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

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

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

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

问题描述

前面几篇文章为大家介绍了多种递归算法来实现1到100求和，但是这些算法都无一例外利用static关键词定义了一个sum变量，即：

static int sum = 0;

此处是利用了静态变量的特性完成和的累加操作，是否可以不使用这种类型的变量呢？本文将为大家介绍一种新的思维方式来求解。

解决方案

前面设计的所有的递归函数的返回值类型都为void，是否可以让递归函数有返回值，尝试着从这点入手来考虑解决问题。

如果每一次的递归函数都需要返回值，那么应该返回什么呢？

在数学的学习中，有一个非常重要的概念叫函数，即f(x)=y。其中x叫自变量，y叫因变量，意思就是任意的给定一个定义域内自变量的值，将其带入到函数f中进行计算，就会得到因变量y的值。举例如下：

假设有函数y=f(x)=2·x + 1，

当x=1时，y=f(1)=2·1+1=3；

当x=2时，y=f(2)=2·2+1=5；

我们尝试着用函数的概念和思想来解决1到100的求和问题，假设现在有1到x的求和函数y=f(x)，其中自变量x的值为1到100。至于这个函数具体是什么，可以先不用管，只需要了解这个函数所要表达的意义即可。

当x=1时        y=f(1)的值表示1到1的和。

当x=2时        y=f(2)的值表示1到2的和。

当x=100时    y=f(100)的值表示1到100的和。

有了上述的函数，就可以快速的表示1到100的求和了即f(100)，接下来考察f(100)和f(99)之间的关系是什么？

显而易见：

f(100) = 100 + f(99)

f(99) = 99 + f(98)

···

f(2) = 2 + f(1)

f(1) = 1

从上面的递推关系可以得出，如果要求f(100)就必须先求f(99)，依次类推，最后必须要知道f(1)的值，而f(1)=1，因此反过来即可知道f(100)。

这种思想简单描述就是：

f(100)

f(99)

···

f(2)

f(1)  // 递归结束，返回。

这种思维方式是否和第二篇文章介绍的思维方式极其相似，在第二篇文章中，让整数n从100开始一直递减到1，然后才开始打印1，2，···，100。这两种情况虽然形式不同，但是思维的本质是一致的，因此学会了思维就可以解决无穷多的问题。

编程语言中的函数的概念和数学中函数的概念是极其的相似，可以将函数的形参理解为自变量x，而函数的返回值理解为因变量y。结合上面得出的递推关系y=f(x) = x + f(x-1)，可以很快写出下面的代码：

int foo(int x){

    return x + foo(x-1); // 此处函数的返回值就是因变量y

}

由于递归函数必须有结束条件否则会陷入无限循环，因此加上其结束条件即可，其Java版本完整的代码为：

至此，我们消除了static类型的sum变量，圆满的解决了问题。

结语

本文最大的贡献就是将数学中函数的思想引入到算法思维中来解决问题，建立函数的模型，引出递推关系，进而采用递归函数来编程实现。这种利用数学函数的思维来解决问题的思维方式是非常常见的，也是非常重要的一种思维方式。同时，有了函数的思维，还要学会其编程实现思路。