從1到100求和學(xué)算法思維（一）

從1到100求和學(xué)算法思維（二）

從1到100求和學(xué)算法思維（三）

從1到100求和學(xué)算法思維（四）

前面幾篇文章為大家介紹了多種遞歸算法來實(shí)現(xiàn)1到100求和,，但是這些算法都無一例外利用static關(guān)鍵詞定義了一個sum變量，即：

static int sum = 0;

此處是利用了靜態(tài)變量的特性完成和的累加操作,，是否可以不使用這種類型的變量呢,？本文將為大家介紹一種新的思維方式來求解。

前面設(shè)計的所有的遞歸函數(shù)的返回值類型都為void,，是否可以讓遞歸函數(shù)有返回值,，嘗試著從這點(diǎn)入手來考慮解決問題。

如果每一次的遞歸函數(shù)都需要返回值,，那么應(yīng)該返回什么呢？

在數(shù)學(xué)的學(xué)習(xí)中,，有一個非常重要的概念叫函數(shù),，即f(x)=y。其中x叫自變量,，y叫因變量,，意思就是任意的給定一個定義域內(nèi)自變量的值,，將其帶入到函數(shù)f中進(jìn)行計算，就會得到因變量y的值,。舉例如下：

假設(shè)有函數(shù)y=f(x)=2·x + 1,，

當(dāng)x=1時，y=f(1)=2·1+1=3,；

當(dāng)x=2時，y=f(2)=2·2+1=5,；

我們嘗試著用函數(shù)的概念和思想來解決1到100的求和問題,，假設(shè)現(xiàn)在有1到x的求和函數(shù)y=f(x)，其中自變量x的值為1到100,。至于這個函數(shù)具體是什么,，可以先不用管，只需要了解這個函數(shù)所要表達(dá)的意義即可,。

當(dāng)x=1時        y=f(1)的值表示1到1的和,。

當(dāng)x=2時        y=f(2)的值表示1到2的和。

當(dāng)x=100時    y=f(100)的值表示1到100的和,。

有了上述的函數(shù)，就可以快速的表示1到100的求和了即f(100),，接下來考察f(100)和f(99)之間的關(guān)系是什么,？

顯而易見：

f(100) = 100 + f(99)

f(99) = 99 + f(98)

···

f(2) = 2 + f(1)

f(1) = 1

從上面的遞推關(guān)系可以得出，如果要求f(100)就必須先求f(99),，依次類推,，最后必須要知道f(1)的值，而f(1)=1,，因此反過來即可知道f(100),。

這種思想簡單描述就是：

f(100)

f(99)

···

f(2)

f(1)  // 遞歸結(jié)束，返回,。

這種思維方式是否和第二篇文章介紹的思維方式極其相似,，在第二篇文章中，讓整數(shù)n從100開始一直遞減到1,，然后才開始打印1,，2，···,，100,。這兩種情況雖然形式不同，但是思維的本質(zhì)是一致的,，因此學(xué)會了思維就可以解決無窮多的問題。

編程語言中的函數(shù)的概念和數(shù)學(xué)中函數(shù)的概念是極其的相似,，可以將函數(shù)的形參理解為自變量x，而函數(shù)的返回值理解為因變量y,。結(jié)合上面得出的遞推關(guān)系y=f(x) = x + f(x-1)，可以很快寫出下面的代碼：

int foo(int x){

    return x + foo(x-1); // 此處函數(shù)的返回值就是因變量y

}

由于遞歸函數(shù)必須有結(jié)束條件否則會陷入無限循環(huán),，因此加上其結(jié)束條件即可,，其Java版本完整的代碼為：

至此，我們消除了static類型的sum變量,，圓滿的解決了問題。

本文最大的貢獻(xiàn)就是將數(shù)學(xué)中函數(shù)的思想引入到算法思維中來解決問題,，建立函數(shù)的模型,，引出遞推關(guān)系，進(jìn)而采用遞歸函數(shù)來編程實(shí)現(xiàn),。這種利用數(shù)學(xué)函數(shù)的思維來解決問題的思維方式是非常常見的，也是非常重要的一種思維方式,。同時，有了函數(shù)的思維,，還要學(xué)會其編程實(shí)現(xiàn)思路。