您好,登錄后才能下訂單哦!
今天小編給大家分享一下Java遞歸和迭代區(qū)別是什么的相關(guān)知識點,內(nèi)容詳細,邏輯清晰,相信大部分人都還太了解這方面的知識,所以分享這篇文章給大家參考一下,希望大家閱讀完這篇文章后有所收獲,下面我們一起來了解一下吧。
當(dāng)實體調(diào)用自身
時,程序稱為遞歸
。
當(dāng)存在循環(huán)(或重復(fù))
時,程序稱為迭代調(diào)用
。
示例:求一個數(shù)的階乘的程序
時間復(fù)雜度比較
查找遞歸的時間復(fù)雜度比迭代更難。
遞歸
:遞歸的時間復(fù)雜度可以通過根據(jù)先前的調(diào)用找到第 n 次遞歸調(diào)用的值來找到。因此,根據(jù)基本情況找到目標(biāo)情況,并根據(jù)基本情況求解,可以讓我們了解遞歸方程的時間復(fù)雜度。
迭代
:迭代的時間復(fù)雜度可以通過找到循環(huán)內(nèi)重復(fù)的循環(huán)數(shù)來找到。
用法比較
使用這些技術(shù)中的任何一種都是時間復(fù)雜度和代碼大小之間的權(quán)衡。
如果時間復(fù)雜度是重點,遞歸調(diào)用的次數(shù)會很大,那么最好使用迭代。
但是,如果時間復(fù)雜度不是問題而代碼的短小是問題,那么遞歸將是可行的方法。
遞歸:遞歸涉及再次調(diào)用相同的函數(shù),因此代碼長度非常短。然而,正如我們在分析中看到的那樣,當(dāng)遞歸調(diào)用數(shù)量相當(dāng)多時,遞歸的時間復(fù)雜度可能會呈指數(shù)級增長。因此,遞歸的使用在更短的代碼中是有利的,但時間復(fù)雜度更高。
迭代:迭代是代碼塊的重復(fù)。這涉及較大的代碼量,但時間復(fù)雜度通常低于遞歸。
開銷
與迭代相比,遞歸有大量的開銷。
遞歸
:遞歸有函數(shù)重復(fù)調(diào)用的開銷,即由于重復(fù)調(diào)用同一個函數(shù)
,代碼的時間復(fù)雜度增加了很多倍
。
迭代
:迭代不涉及任何此類開銷。
無限重復(fù)
遞歸
中的 Infinite Repetition 會導(dǎo)致 CPU crash,但在迭代中,當(dāng)內(nèi)存耗盡時它會停止。
遞歸
:在Recursion中,由于指定的基本條件錯誤,可能會出現(xiàn)無限遞歸調(diào)用,在永遠不會為假的情況下,不斷調(diào)用函數(shù),這可能會導(dǎo)致系統(tǒng)CPU崩潰。
迭代
:由于迭代器賦值或遞增錯誤或終止條件錯誤而導(dǎo)致的無限迭代將導(dǎo)致無限循環(huán),這可能會或可能不會導(dǎo)致系統(tǒng)錯誤,但肯定會停止程序的進一步執(zhí)行。
遞歸 | 迭代 | |
---|---|---|
定義 | 函數(shù)調(diào)用自身。 | 重復(fù)執(zhí)行的一組指令。 |
應(yīng)用 | 對于功能。 | 對于循環(huán)。 |
終止 | 通過 base case,這里不會有函數(shù)調(diào)用。 | 當(dāng)不再滿足迭代器的終止條件時。 |
用法 | 當(dāng)代碼大小需要很小并且時間復(fù)雜度不是問題時使用。 | 當(dāng)時間復(fù)雜度需要與擴展的代碼大小進行平衡時使用 |
代碼大小 | 更少的代碼 | 更多的代碼 |
時間復(fù)雜度 | 非常高(通常是指數(shù))的時間復(fù)雜度。 | 時間復(fù)雜度相對較低(一般為多項式-對數(shù))。 |
空間復(fù)雜度 | 空間復(fù)雜度高于迭代。 | 空間復(fù)雜度較低。 |
堆 | 這里的棧是用來存放函數(shù)調(diào)用時的局部變量的。 | 不使用堆棧。 |
速度 | 執(zhí)行速度很慢,因為它有維護和更新堆棧的開銷。 | 通常,它比遞歸更快,因為它不使用堆棧。 |
存儲 | 與迭代相比,遞歸使用更多內(nèi)存。 | 沒有開銷,因為迭代中沒有函數(shù)調(diào)用。 |
高架 | 擁有重復(fù)函數(shù)調(diào)用的開銷。 | 沒有開銷,因為迭代中沒有函數(shù)調(diào)用。 |
無限重復(fù) | 如果遞歸函數(shù)不滿足終止條件或未定義或從未達到基本情況,則會導(dǎo)致堆棧溢出錯誤,并且系統(tǒng)有可能在無限遞歸中崩潰。 | 如果迭代語句的控制條件永遠不為假或控制變量沒有達到終止值,就會造成死循環(huán)。在無限循環(huán)中,它一次又一次地使用 CPU 周期。 |
public class Test { // ----- 遞歸 ----- // 求給定數(shù)的階乘的方法 static int factorialUsingRecursion(int n) { if (n == 0) return 1; // 遞歸呼叫 return n * factorialUsingRecursion(n - 1); } // -----迭代 ----- //求給定數(shù)的階乘的方法 static int factorialUsingIteration(int n) { int res = 1, i; // 迭代 for (i = 2; i <= n; i++) res *= i; return res; } public static void main(String[] args) { int num = 5; System.out.println("Factorial of " + num + " using Recursion is: " + factorialUsingRecursion(5)); System.out.println("Factorial of " + num + " using Iteration is: " + factorialUsingIteration(5)); } }
Factorial of 5 using Recursion is: 120 Factorial of 5 using Iteration is: 120
以上就是“Java遞歸和迭代區(qū)別是什么”這篇文章的所有內(nèi)容,感謝各位的閱讀!相信大家閱讀完這篇文章都有很大的收獲,小編每天都會為大家更新不同的知識,如果還想學(xué)習(xí)更多的知識,請關(guān)注億速云行業(yè)資訊頻道。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。