迭代與嵌套是面向過程的兩個非常有用的算法，在一些java開發(fā)中也應(yīng)用的比較多。今天學(xué)習(xí)了一些皮毛，將其總結(jié)如下。

1線型的遞歸和迭代：

線型過程結(jié)構(gòu)比較簡單，比較容易理解，并且從描述到代碼的書寫比較容易實(shí)現(xiàn)。最常見的是計(jì)算階乘：

1.1、用迭代的想法是，從1開始計(jì)算，每次乘上新的i，新計(jì)算的結(jié)果代替舊的結(jié)果：n->n*i;

int n=1;for(int i=1;i<n;i++){n=n*i;}

1.2、用嵌套的想法是，f(n)=nf(n-1),當(dāng)n等于1時返回1；于是

PRivate static int factorial(int n){if(n==1)return 1;elsereturn n*factorial(n-1);}

1.3、迭代的過程比較簡單，不想多說，在寫程序時，可以寫成迭代的盡量使用迭代，嵌套相對而言更消耗計(jì)算資源。

這里要簡單的說一下迭代的整個計(jì)算過程。編寫嵌套算法，最重要有兩點(diǎn)：程序的出口和程序過程。例如

程序的出口是指，程序最末端程序應(yīng)該返回的值，例如在1.2中的if(n==1) return 1;就是程序的末端。

有了程序的末端，就要去設(shè)計(jì)程序的過程，嵌套的過程并不容易書寫，很容犯錯。比如有這樣兩個方法，很類似，得出的結(jié)果相差卻很大：

private static void show1(int i) {        // TODO 自動生成的方法存根        if (i < 6)            t(i + 1);        else            System.out.print(i + " ");    }

private static void show2(int i) {        // TODO 自動生成的方法存根        if (i < 6)            t(i + 1)        

       System.out.print(i + " ");    }

同樣給i初值是1時，show1打印的是6，show2打印的 是6 5 4 3 2 1。

分析一下這兩個程序，show1(1),返回show1(2)。。。最后，當(dāng)show1（6）時，程序結(jié)束，打印6。而show2（1）就不一樣了，show2（1）的出口也是6，但是，在執(zhí)行show1（1）時，程序有一部分（system.out.print(…)）沒有執(zhí)行，因?yàn)槌绦蜻M(jìn)入了下一個嵌套show2（2），稱沒有執(zhí)行的語句被暫時掛起。這樣每個循環(huán)都被掛起一段代碼，直到show2（6）時，程序找到出口，開始往回執(zhí)行嵌套過程。先打印6 之后5 再4 。。。注意打印不是先1 再2 再3 。。。

由此也可見，在嵌套中出口對于程序是很重要的。

嵌套的計(jì)算機(jī)算法可以理解為，先掛起執(zhí)行代碼直到找到出口，從出口開始執(zhí)行代碼。

還有一個經(jīng)典的例子是求最大公約數(shù)的問題，這里就不多說過程了，將前人的算法留下。數(shù)學(xué)過程是，(a,b)的最大公約數(shù)，與（b,a%b）的最大公約數(shù)相等，算法因歐幾里德而出名，命名為歐幾里德輾轉(zhuǎn)算法。代碼這里就不在給出了

當(dāng)然線型過程都是可以優(yōu)化的，在這里就不多說了。

如果說線型結(jié)構(gòu)相對而言簡單一下，樹形結(jié)構(gòu)要復(fù)雜很多，也更管用，可以解決許多日常世紀(jì)問題。

2、樹形遞歸

樹形算法要復(fù)雜很多，并且使用嵌套的方式更容易理解。

一個簡單的例子是斐波數(shù)：

最常用的數(shù)學(xué)描述f（n）=f（n-1）+f(n-2)。n=2時 1，n=1時 1。

使用迭代或者是遞歸的方法都很容易實(shí)現(xiàn)，這里就不在寫詳細(xì)的實(shí)現(xiàn)過程了。簡單的把嵌套的樹形圖畫一下：

樹形過程還是挺復(fù)雜的，上面只是一個最簡單的例子，下面舉一個很有意思的例子說明一下嵌套在解決復(fù)雜問題中比迭代更容易解決問題的例子：

有1個美國人，他有一枚祖?zhèn)鞯?美元（100美分）硬幣。有一天，他找到正在雜貨店的我，對我我“嗨，哥們，你那有零錢嗎”，“當(dāng)然有”我回答道，“你要哪種，我這有50美分、25美分的、10美分的、5美分的和1美分的。”“這么多啊”他詫異道，“我想把1美分換成零錢，你能告訴我一共多少中不同的方式嗎？”

當(dāng)然對于這個刁難我的問題，我是不會回答他的，我立馬叫來隔壁正在忙著破解美國軍方網(wǎng)絡(luò)的jack，“Hi，jack，help me”我大聲叫道，jack卻在忙著他手頭的活，沉靜了半分種，他晃了晃腦袋，說了句“I know what you want to say，wait me one miniter”，果然，不到一分鐘，jack說了個數(shù)字292。當(dāng)我還在霧里時，那位害我死了不少腦細(xì)胞的美國人大叫道：“不可思議，你是怎么做到的，我整整算了一周才把所有的情況排序出來”。聰明的你想到解決方案了嗎。

使用遞歸到并不是很難實(shí)現(xiàn)，稍微動些腦筋。

數(shù)學(xué)描述是這樣的：假設(shè)Fk（n）表述n美分兌換成k枚金幣的所有結(jié)果，那么Fk（n）可以遞歸的看成，沒有其中一種硬幣的結(jié)果，和除去一個其中一種硬幣的剩下錢的兌換結(jié)果，寫成：Fk(n)=Fk-1(n)+Fk(n-a).

比如上面的例子可以描述成，最終結(jié)果是由（100美分去除一個50美分）剩余的50美分兌換成5種硬幣的全部方法加上100美分兌換成4種硬幣的方法（沒有50美分的這種硬幣）。圖形可以更好的說明這一過程，聰明的你可以在紙上做一做圖形。

但是，我想提醒的是，想把這一數(shù)學(xué)過程寫成計(jì)算機(jī)代碼并不是一件容易的事情，這里我先不給出Java語言的代碼，你可以寫出來，我們一下討論一下。

當(dāng)然這里有一個挑戰(zhàn)留給大家，包括我自己，就是怎樣把這個過程寫成其他的方式，大家都知道，遞歸法是很消耗資源的，如果你設(shè)計(jì)出了更好的算法，請與我分享，ahrty0814@Gmail.com

謝謝！