網(wǎng)站設計主頁,怎么開發(fā)一個游戲,成都易站網(wǎng)站建設,做網(wǎng)站需要固定ip么文章目錄第一章 數(shù)據(jù)結構與算法基本概念1.1 數(shù)據(jù)結構定義1.2 算法定義1.3 遞歸與迭代1.3.1 迭代1.3.1 遞歸1 遞歸和迭代的思想比較2 調(diào)用棧3 尾遞歸4 遞歸樹5 遞歸和迭代對比本文記錄數(shù)據(jù)結構與算法的定義#xff0c;遞歸和迭代的定義和比較#xff0c;下一篇筆記介紹時間復雜…文章目錄第一章 數(shù)據(jù)結構與算法基本概念1.1 數(shù)據(jù)結構定義1.2 算法定義1.3 遞歸與迭代1.3.1 迭代1.3.1 遞歸1 遞歸和迭代的思想比較2 調(diào)用棧3 尾遞歸4 遞歸樹5 遞歸和迭代對比本文記錄數(shù)據(jù)結構與算法的定義遞歸和迭代的定義和比較下一篇筆記介紹時間復雜度和字符編碼。第一章 數(shù)據(jù)結構與算法基本概念1.1 數(shù)據(jù)結構定義數(shù)據(jù)結構相互之間存在一種或者多種特定關系的數(shù)據(jù)元素的集合。在邏輯上可以分為線性結構、散列結構、樹形結構和圖形結構等。1.2 算法定義算法 求解具體問題的步驟描述代碼上表現(xiàn)出來是解決特定問題的一組有限的指令序列。1.3 遞歸與迭代這一節(jié)參考了《hello 算法》的第二章。1.3.1 迭代迭代iteration是一種重復執(zhí)行某個任務的控制結構。在迭代中程序會在滿足一定的條件下重復執(zhí)行某段代碼直到這個條件不再滿足。下面以for循環(huán)為例求123…100的和。intforLoop(intn){intret0;// 循環(huán)求和for(inti1;in;i){reti;}returnret;}1.3.1 遞歸遞歸recursion是一種算法策略通過函數(shù)調(diào)用自身來解決問題。它主要包含兩個階段。遞程序不斷深入地調(diào)用自身通常傳入更小或更簡化的參數(shù)直到達到“終止條件”。歸觸發(fā)“終止條件”后程序從最深層的遞歸函數(shù)開始逐層返回匯聚每一層的結果。而從實現(xiàn)的角度看遞歸代碼主要包含三個要素。終止條件用于決定什么時候由“遞”轉(zhuǎn)“歸”。遞歸調(diào)用對應“遞”函數(shù)調(diào)用自身通常輸入更小或更簡化的參數(shù)。返回結果對應“歸”將當前遞歸層級的結果返回至上一層。比如下面代碼intrecursum(intn){// 1 終止條件if(n1){return1;}// 2 遞歸調(diào)用intretrecursum(n-1)n;coutret retendl;//3 歸返回結果returnret;}理解和總結每次遞歸都開辟一個棧幀開始遞的過程然后當n1時結束遞的過程開始歸歸的時候從遞的下面一行開始運行比如上面代碼中歸時每次都執(zhí)行下面代碼程序運行結果/* ret3ret6ret10ret15*/1 遞歸和迭代的思想比較以123…100為例雖然遞歸和迭代都能求出這個問題但是這兩種完全不同的思考和解決問題的范式。迭代“自下而上”地解決問題。從最基礎的步驟開始然后不斷重復或累加這些步驟直到任務完成。比如先求123然后再求34…這樣的方法最后求出sum() 100.從小數(shù)一直累加的方法。遞歸“自上而下”地解決問題。先將遠問題分解為更小的問題這些子問題和原問題有相同的形式。然后再將子問題分解為更小的子問題直到基本情況時停止。比如上面的求和代碼中遞的過程就是分解子問題() (?1)將100分解為99100, 9899的過程一直分解為12然后開始歸。2 調(diào)用棧遞歸函數(shù)每次調(diào)用自身時系統(tǒng)都會為新開啟的函數(shù)分配一個棧空間。而迭代只有一個?？臻g因此遞歸比迭代更加消費內(nèi)存空間。函數(shù)調(diào)用會產(chǎn)生額外的開銷因此遞歸比循環(huán)效率更低。3 尾遞歸如果函數(shù)在返回前的最后一步才進行遞歸調(diào)用則函數(shù)可以被編譯器優(yōu)化使其在空間上與迭代相當這中情況稱為尾遞歸。普通遞歸當函數(shù)返回到上一層級的函數(shù)后需要繼續(xù)執(zhí)行代碼因此系統(tǒng)需要保存上一層調(diào)用的上下文。求和操作是在“歸”的過程中執(zhí)行的每層返回后都要再執(zhí)行一次求和操作。尾遞歸遞歸調(diào)用是函數(shù)返回前的最后一個操作這意味著函數(shù)返回到上一層級后無須繼續(xù)執(zhí)行其他操作因此系統(tǒng)無須保存上一層函數(shù)的上下文。inttailRecursum(intn,intret){// 1 終止條件if(n0){returnret;}// 2 遞歸調(diào)用returntailRecursum(n-1,retn);}求和操作是在“遞”的過程中執(zhí)行的“歸”的過程只需層層返回。4 遞歸樹當處理與“分治”相關的算法問題時遞歸往往比迭代的思路更加直觀、代碼更加易讀。以“斐波那契數(shù)列”為例。Question給定一個斐波那契數(shù)列 0, 1, 1, 2, 3, 5, 8, 13, … 求該數(shù)列的第 個數(shù)字。數(shù)列的前兩個數(shù)字為 (1) 0 和 (2) 1 。數(shù)列中的每個數(shù)字是前兩個數(shù)字的和即 () ( ? 1) ( ? 2) 。代碼實現(xiàn)intfib(intn){// 終止條件if(n1||n2){returnn-1;}// 遞歸調(diào)用 f(n) f(n-1) f(n-2)intretfib(n-1)fib(n-2);returnret;}上面代碼在函數(shù)內(nèi)遞歸調(diào)用了兩個函數(shù)這意味著從一個調(diào)用產(chǎn)生了兩個調(diào)用分支這樣的遞歸會產(chǎn)生一個遞歸樹層數(shù)為n的遞歸樹以5層為例子。遞歸體現(xiàn)了“將問題分解為更小子問題”的思維范式這種分支策略至關重要。5 遞歸和迭代對比為了理解遞歸過程使用棧來模擬遞歸的過程intforLoopRecursum(intn){// 1 終止條件stackints;intret0;// 模擬遞的過程for(intin;i0;--i){s.push(i);}// 歸的過程while(!s.empty()){rets.top();s.pop();}returnret;}