Java中的迭代和遞歸講解
迭代使用的是循環(for,while,)或者迭代器,當循環條件不滿足時退出。而遞歸,一般是函數遞歸,可以是自身調用自身,也可以是非直接調用,即方法A調用方法B,而方法B反過來調用方法A,遞歸退出的條件為if,else語句,當條件符合基的時候退出。下面是小編為大家整理的Java中的迭代和遞歸講解,歡迎參考~
Java中的迭代和遞歸講解前言
迭代使用的是循環(for,while,)或者迭代器,當循環條件不滿足時退出。而遞歸,一般是函數遞歸,可以是自身調用自身,也可以是非直接調用,即方法A調用方法B,而方法B反過來調用方法A,遞歸退出的條件為if,else語句,當條件符合基的時候退出。
上面是迭代和遞歸的語法特性,他們在Java中有什麼不同呢?
一、遞歸
提到迭代,不得不提一個數學表達式: n!=n*(n-1)*(n-2)*...*1
有很多方法來計算階乘。有一定數學基礎的人都知道n!=n*(n-1)!因此,代碼的實現可以直接寫成:
代碼一
int factorial (int n) {
if (n == 1) {
return 1;
} else {
return n*factorial(n-1);
}
}
在執行以上代碼的時候,其實機器是要執行一系列乘法的: factorial(n) → factorial(n-1) → factorial(n-2) → … → factorial(1) 。所以,需要不斷的跟蹤(跟蹤上次計算的結果)並調用乘法進行計算(構建一個乘法鏈)。這類不斷調用自身的運算形式稱之為遞歸。遞歸可以進一步的分為線性遞歸和數形遞歸。信息量隨着算法的輸入呈線性增長的遞歸稱之為線性遞歸。計算n!(階乘)就是線性遞歸。因為隨着N的增大,計算所需的時間呈線性增長。另外一種信息量隨着輸入的增長而進行指數增長的稱之為樹形遞歸。
二、迭代
另外一種計算n!的方式是:先計算1乘以2,然後用其結果乘以3,再用的到的結果乘以4….一直乘到N。在程序實現時,可以定義一個計數器,每進行一次乘法,計數器都自增一次,直到計數器的值等於N截至。代碼如下:
代碼二
int factorial (int n) {
int product = 1;
for(int i=2; i<n; i++) {
product *= i;
}
return product;
}
和代碼一相比,代碼二沒有構建一個乘法鏈。在進行每一步計算時,只需要知道當前結果(product)和i的值就可以了。這種計算形式稱之為迭代。迭代有這樣幾個條件:1、有一個有初始值的變量。2、一個説明變量值如何更新的規則。3、一個結束條件。(循環三要素:循環變量、循環體和循環終止條件)。和遞歸一樣。時間要求隨着輸入的增長呈線性的可以叫做線性迭代。
三、迭代 VS 遞歸
比較了兩個程序,我們可以發現,他們看起來幾乎相同,特別是其數學函數方面。在計算n!的時候,他們的計算步數都是和n的值成正比的。但是,如果我們站在程序的角度,考慮他們是如何運行的話,那麼這兩個算法就有很大不同了。
(注:原文中關於其區別寫的有點扯,這裏就不翻譯了,下面是筆者自己總結內容。)
首先分析遞歸,其實遞歸最大的有點就是把一個複雜的算法分解成若干相同的可重複的步驟。所以,使用遞歸實現一個計算邏輯往往只需要很短的.代碼就能解決,並且這樣的代碼也比較容易理解。但是,遞歸就意味着大量的函數調用。函數調用的局部狀態之所以用棧來記錄的。所以,這樣就可能浪費大量的空間,如果遞歸太深的話還有可能導致堆棧溢出。
接下來分析迭代。其實,遞歸都可以用迭代來代替。但是相對於遞歸的簡單易懂,迭代就比較生硬難懂了。尤其是遇到一個比較複雜的場景的時候。但是,代碼的難以理解帶來的有點也比較明顯。迭代的效率比遞歸要高,並且在空間消耗上也比較小。
遞歸中一定有迭代,但是迭代中不一定有遞歸,大部分可以相互轉換。
能用迭代的不要用遞歸,遞歸調用函數不僅浪費空間,如果遞歸太深的話還容易造成堆棧的溢出。
四、數形遞歸
前面介紹過,樹遞歸隨輸入的增長的信息量呈指數級增長。比較典型的就是斐波那契數列:
用文字描述就是斐波那契數列中前兩個數字的和等於第三個數字:0,1,1,2,3,5,8,13,21……
遞歸實現代碼如下:
int fib (int n) {
if (n == 0) {
return 0;
} else if (n == 1) {
return 1;
} else {
return fib(n-1) + fib(n-2);
}
}
計算過程中,為了計算fib(5) ,程序要先計算fib(4) 和 fib(3) ,要想計算fib(4) ,程序同樣需要先計算 fib(3) 和 fib(2) 。在這個過程中計算了兩次fib(3)。
從上面分析的計算過程可以得出一個結論:使用遞歸實現斐波那契數列存在宂餘計算。
就像上面提到的,可以用遞歸的算法一般都能用迭代實現,斐波那契數列的計算也一樣。
int fib (int n) {
int fib = 0;
int a = 1;
for(int i=0; i<n; i++) {
int temp = fib;
fib = fib + a;
a = temp;
}
return fib;
}
雖然使用遞歸的方式會有宂餘計算,可以用迭代來代替。但是這並不表明遞歸可以完全被取代。因為遞歸有更好的可讀性。
-
2017上半年計算機二級Java練習題及答案
計算機等級證書是我們找工作的敲門磚,現在越來越多人重視計算機等級考試。下面是本站小編為大家帶來的2017上半年計算機二級Java練習題及答案,希望對大家的學習有幫助!一、單選題1、結構化程序設計主要強調的是______。A、程序的規模B、程序的易讀性C、程序的執...
-
Java語言的學習技巧
知識改變命運,對於Java程序員來説,技術不斷更新,只有及時充電,才能不被市場淘汰。今天小編為大家分享Java程序員學習的6個小技巧。一定要看書現在學習Java變得比以前容易多了,除了有大量的視頻教程外,還有專業的java培訓機構,這都使學習變得更加傻瓜化,然而我要説的是,J...
-
關於java實驗報告模板
1.掌握JavaApplet的程序結構和開發過程。2.學會編寫Applet對應的HTML文件,掌握從HTML文件向Applet傳遞參數的方法。3.掌握文本框對象的使用方法。4.掌握按鈕類對象的使用方法。5.掌握佈局管理器的用法。6.理解ActionEvent事件的`含義。7.掌握事件源、監視器、處理事...
-
Java技術怎麼學習
對於很多隻會C語言的初學者而言,面對java基礎語法學習,反而感覺很難,其實其中最大的問題不是語法難,而是一種編程思想的轉變。怎麼學習才是正確的呢?下面是相關的知識,歡迎閲讀。1.概述學過一段時間的同學一定會覺得Java學習最頭疼的不是語法結構的繁雜,而是Java本身...