函數(shù)的遞歸調(diào)用
我們提供的服務(wù)有：做網(wǎng)站、成都網(wǎng)站設(shè)計、微信公眾號開發(fā)、網(wǎng)站優(yōu)化、網(wǎng)站認證、長順ssl等。為成百上千家企事業(yè)單位解決了網(wǎng)站和推廣的問題。提供周到的售前咨詢和貼心的售后服務(wù)，是有科學(xué)管理、有技術(shù)的長順網(wǎng)站制作公司
遞歸問題是一個說簡單也簡單，說難也有點難理解的問題.我想非常有必要對其做一個總結(jié).
首先理解一下遞歸的定義，遞歸就是直接或間接的調(diào)用自身.而至于什么時候要用到遞歸，遞歸和非遞歸又有那些區(qū)別？又是一個不太容易掌握的問題，更難的是對于遞歸調(diào)用的理解.下面我們就從程序+圖形的角度對遞歸做一個全面的闡述.
我們從常見到的遞歸問題開始:
1 階層函數(shù)
#include iostream
using namespace std;
int factorial(int n)
{
if (n == 0)
{
return 1;
}
else
{
int result = factorial(n-1);
return n * result;
}
}
int main()
{
int x = factorial(3);
cout x endl;
return 0;
}
這是一個遞歸求階層函數(shù)的實現(xiàn)。很多朋友只是知道該這么實現(xiàn)的，也清楚它是通過不斷的遞歸調(diào)用求出的結(jié)果.但他們有些不清楚中間發(fā)生了些什么.下面我們用圖對此做一個清楚的流程:
根據(jù)上面這個圖，大家可以很清楚的看出來這個函數(shù)的執(zhí)行流程。我們的階層函數(shù)factorial被調(diào)用了4次.并且我們可以看出在調(diào)用后面的調(diào)用中，前面的調(diào)用并不退出。他們同時存在內(nèi)存中?？梢娺@是一件很浪費資源的事情。我們該次的參數(shù)是3.如果我們傳遞10000呢。那結(jié)果就可想而知了.肯定是溢出了.就用int型來接收結(jié)果別說10000，100就會產(chǎn)生溢出.即使不溢出我想那肯定也是見很浪費資源的事情.我們可以做一個粗略的估計:每次函數(shù)調(diào)用就單變量所需的內(nèi)存為:兩個int型變量.n和result.在32位機器上占8B.那么10000就需要10001次函數(shù)調(diào)用.共需10001*8/1024 = 78KB.這只是變量所需的內(nèi)存空間.其它的函數(shù)調(diào)用時函數(shù)入口地址等仍也需要占用內(nèi)存空間。可見遞歸調(diào)用產(chǎn)生了一個不小的開銷.
2 斐波那契數(shù)列
int Fib(int n)
{
if (n = 1)
{
return n;
}
else
{
return Fib(n-1) + Fib(n-2);
}
}
這個函數(shù)遞歸與上面的那個有些不同.每次調(diào)用函數(shù)都會引起另外兩次的調(diào)用.最后將結(jié)果逐級返回.
我們可以看出這個遞歸函數(shù)同樣在調(diào)用后買的函數(shù)時，前面的不退出而是在等待后面的結(jié)果，最后求出總結(jié)果。這就是遞歸.
3
#include iostream
using namespace std;
void recursiveFunction1(int num)
{
if (num 5)
{
cout num endl;
recursiveFunction1(num+1);
}
}
void recursiveFunction2(int num)
{
if (num 5)
{
recursiveFunction2(num+1);
cout num endl;
}
}
int main()
{
recursiveFunction1(0);
recursiveFunction2(0);
return 0;
}
運行結(jié)果:
1
2
3
4
4
3
2
1
該程序中有兩個遞歸函數(shù)。傳遞同樣的參數(shù)，但他們的輸出結(jié)果剛好相反。理解這兩個函數(shù)的調(diào)用過程可以很好的幫助我們理解遞歸:
我想能夠把上面三個函數(shù)的遞歸調(diào)用過程理解了，你已經(jīng)把遞歸調(diào)用理解的差不多了.并且從上面的遞歸調(diào)用中我們可以總結(jié)出遞歸的一個規(guī)律：他是逐級的調(diào)用，而在函數(shù)結(jié)束的時候是從最后面往前反序的結(jié)束.這種方式是很占用資源，也很費時的。但是有的時候使用遞歸寫出來的程序很容易理解，很易讀.
為什么使用遞歸:
1 有時候使用遞歸寫出來的程序很容易理解，很易讀.
2 有些問題只有遞歸能夠解決.非遞歸的方法無法實現(xiàn).如:漢諾塔.
遞歸的條件:
并不是說所有的問題都可以使用遞歸解決，他必須的滿足一定的條件。即有一個出口點.也就是說當滿足一定條件時，程序可以結(jié)束，從而完成遞歸調(diào)用，否則就陷入了無限的遞歸調(diào)用之中了.并且這個條件還要是可達到的.
遞歸有哪些優(yōu)點:
易讀，容易理解，代碼一般比較短.
遞歸有哪些缺點:
占用內(nèi)存資源多，費時，效率低下.
因此在我們寫程序的時候不要輕易的使用遞歸，雖然他有他的優(yōu)點，但是我們要在易讀性和空間，效率上多做權(quán)衡.一般情況下我們還是使用非遞歸的方法解決問題.若一個算法非遞歸解法非常難于理解。我們使用遞歸也未嘗不可.如:二叉樹的遍歷算法.非遞歸的算法很難與理解.而相比遞歸算法就容易理解很多.
對于遞歸調(diào)用的問題，我們在前一段時間寫圖形學(xué)程序時，其中有一個四連同填充算法就是使用遞歸的方法。結(jié)果當要填充的圖形稍微大一些時，程序就自動關(guān)閉了.這不是一個人的問題，所有人寫出來的都是這個問題.當時我們給與的解釋就是堆棧溢出。就多次遞歸調(diào)用占用太多的內(nèi)存資源致使堆棧溢出，程序沒有內(nèi)存資源執(zhí)行下去，從而被操作系統(tǒng)強制關(guān)閉了.這是一個真真切切的例子。所以我們在使用遞歸的時候需要權(quán)衡再三.
可以看出來的是，該題可以用斐波那契數(shù)列解決。
樓梯一共有n層，每次只能走1層或者2層，而要走到最終的n層。不是從n-1或者就是n-2來的。
F(1) = 1
F(2) = 2
F(n) = F(n-1) + F(n-2) (n=3)
這是遞歸寫法，但是會導(dǎo)致棧溢出。在計算機中，函數(shù)的調(diào)用是通過棧進行實現(xiàn)的，如果遞歸調(diào)用的次數(shù)過多，就會導(dǎo)致棧溢出。
針對這種情況就要使用方法二，改成非遞歸函數(shù)。
將遞歸進行改寫，實現(xiàn)循環(huán)就不會導(dǎo)致棧溢出
作為初學(xué)者，第一個月的月目標應(yīng)該是這樣的：
熟悉基本概念（變量，條件，列表，循環(huán)，函數(shù)）
練習(xí)超過 30 個編程問題
利用這些概念完成兩個項目
熟悉至少 2 個框架
開始使用集成開發(fā)環(huán)境（IDE），Github，hosting，services 等
整體計劃
現(xiàn)在，我們先將月計劃細化成周計劃。
第一周：熟悉 Python
要積極探索 Python 的使用方法，盡可能多的完成下面這些任務(wù)：
第一天：基本概念（4 小時）：print，變量，輸入，條件語句
第二天：基本概念（5 小時）：列表，for 循環(huán)，while 循環(huán)，函數(shù)，導(dǎo)入模塊
第三天：簡單編程問題（5 小時）：交換兩個變量值，將攝氏度轉(zhuǎn)換為華氏溫度，求數(shù)字中各位數(shù)之和，判斷某數(shù)是否為素數(shù)，生成隨機數(shù)，刪除列表中的重復(fù)項等等
第四天：中級編程問題（6 小時）：反轉(zhuǎn)一個字符串（回文檢測），計算最大公約數(shù)，合并兩個有序數(shù)組，猜數(shù)字游戲，計算年齡等等
第五天：數(shù)據(jù)結(jié)構(gòu)（6 小時）：棧，隊列，字典，元組，樹，鏈表。
第六天：面向?qū)ο缶幊蹋∣OP）（6 小時）：對象，類，方法和構(gòu)造函數(shù)，面向?qū)ο缶幊讨^承
第七天：算法（6 小時）：搜索（線性和二分查找）、排序（冒泡排序、選擇排序）、遞歸函數(shù)（階乘、斐波那契數(shù)列）、時間復(fù)雜度（線性、二次和常量）
通過第一周時間，python大致能熟悉了，自學(xué)能力稍微弱一點找人帶下你，節(jié)約自己的時間。
注意：別急著安裝 Python 環(huán)境！
這看起來很矛盾，但是你一定要相信我。我有幾個朋友，他們因為語言工具包和 IDE 安裝的失敗而逐漸失去了學(xué)習(xí)下去的欲望。因此，我的建議是先使用一些安卓 app 來探索這門語言，如果你是個技術(shù)小白，安裝 Python 環(huán)境可不是你的首要任務(wù)。
第二周：開始軟件開發(fā)（構(gòu)建項目）
接下來，讓我們朝著軟件開發(fā)任務(wù)進軍吧！不妨嘗試綜合你學(xué)到的知識完成一個實際的項目：
第一天：熟悉一種 IDE（5 小時）: IDE 是你在編寫大型項目時的操作環(huán)境，所以你需要精通一個 IDE。在軟件開發(fā)的初期，我建議你在 VS code 中安裝 Python 擴展或使用 Jupyter notebook。
第二天：Github（6 小時）：探索 Github，并創(chuàng)建一個代碼倉庫。嘗試提交（Commit）、查看變更（Diff）和上推（Push）你的代碼。另外，還要學(xué)習(xí)如何利用分支工作，如何合并（merge）不同分支以及如何在一個項目中創(chuàng)建拉取請求（pull request）。
第三天：第一個項目——簡單計算器（4 小時）：熟悉 Tkinter，創(chuàng)建一個簡單的計算器
第四、五、六天：個人項目（每天 5 小時）：選定一個項目并完成它。如果你不知道你該做什么，可以查看下面的清單（ pythonprojects -for-an- middle - programmer/answer/jhankar - mahbub2）
第七天：托管項目（5 小時）：學(xué)習(xí)使用服務(wù)器和 hosting 服務(wù)來托管你的項目。創(chuàng)建一個 Heroku 設(shè)置并部署你構(gòu)建的應(yīng)用程序。
為什么要寫項目？
如果僅僅按部就班地學(xué)習(xí)課堂上或視頻中的內(nèi)容，你無法擁有獨立思考能力。所以，你必須把你的知識應(yīng)用到一個項目中。當你努力尋找答案時，你也在慢慢地學(xué)會這些知識。
第三周：讓自己成為一名程序員
第 3 周的目標是熟悉軟件開發(fā)的整體過程。你不需要掌握所有的知識，但是你應(yīng)該知道一些常識，因為它們會影響你的日常工作。
第一天：數(shù)據(jù)庫基礎(chǔ)（6 小時）：基本 SQL 查詢（創(chuàng)建表、選擇、Where 查詢、更新）、SQL 函數(shù)（Avg、Max、Count）、關(guān)系數(shù)據(jù)庫（規(guī)范化）、內(nèi)連接、外連接等
第二天：使用 Python 數(shù)據(jù)庫（5 小時）：利用一種數(shù)據(jù)庫框架（SQLite 或 panda），連接到一個數(shù)據(jù)庫，在多個表中創(chuàng)建并插入數(shù)據(jù)，再從表中讀取數(shù)據(jù)。
第三天：API（5 小時）：如何調(diào)用 API。學(xué)習(xí) JSON、微服務(wù)（micro-service）以及表現(xiàn)層應(yīng)用程序轉(zhuǎn)換應(yīng)用程序接口（Rest API）。
第四天：Numpy（4 小時）：熟悉 Numpy（- Numpy -for- datascies-beginners-b8088722309f）并練習(xí)前 30 個 Numpy 習(xí)題（- 100/blob/master/100_numpy_excercises.md)
第五、六天：作品集網(wǎng)站（一天 5 小時）：學(xué)習(xí) Django，使用 Django 構(gòu)建一個作品集網(wǎng)站（- start-with-django -1/），也要了解一下 Flask 框架。
第七天：單元測試、日志、調(diào)試（5 小時）：學(xué)習(xí)單元測試（PyTest），如何設(shè)置和查看日志，以及使用斷點調(diào)試。
真心話時間（絕密）
如果你非?！腐偪瘛?，并且非常專注，你可以在一個月內(nèi)完成這些任務(wù)。你必須做到：
把學(xué)習(xí) Python 作為你的全職活動。你需要從早上 8 點開始學(xué)習(xí)，一直到下午 5 點。在此期間，你可以有一個午休時間和茶歇時間（共 1 小時）。
8 點列出你今天要學(xué)的東西，然后花一個小時復(fù)習(xí)和練習(xí)你昨天學(xué)過的東西。
從 9 點到 12 點：開始學(xué)習(xí)，并進行少量練習(xí)。在午飯后，你需要加大練習(xí)量，如果你卡在某個問題上，可以在網(wǎng)上搜索解決方案。
嚴格保持每天 4-5 小時的學(xué)習(xí)時間和 2-3 小時的練習(xí)時間（每周最多可以休息一天）。
你的朋友可能會認為你瘋了。走自己的路，讓別人去說吧！
如果你有一份全職工作，或者你是一名學(xué)生，完成這些流程可能需要更長的時間。作為一名全日制學(xué)生，我花了 8 個月的時間來完成這份清單?，F(xiàn)在我是一名高級開發(fā)人員。所以，不管花多長時間，一定要完成它們。要想成功完成一個目標，必須付出百分之百的努力。
第四周：認真考慮工作（實習(xí)）問題
第 4 周的目標是認真思考如何才能被錄用。即使你現(xiàn)在不想找工作，你也可以在探索這條道路的過程中學(xué)到很多東西。
第一天：準備簡歷（5 小時）：制作一份一頁的簡歷。把你的技能總結(jié)放在最上面，必須在寫項目的同時附上 Github 鏈接。
第二天：作品集網(wǎng)站（6 小時）：寫幾個博客，將它們添加到你之前開發(fā)的作品集網(wǎng)站中。
第三天：LinkedIn 簡介（4 小時）：創(chuàng)建一個 LinkedIn 個人簡介，把簡歷上的所有內(nèi)容都放到 LinkedIn 上。
第四天：面試準備（7 小時）：準備一些谷歌常見的面試問題，練習(xí)白皮書中的 10 個面試編程問題。在 Glassdoor、Careercup 等網(wǎng)站中查看前人遇到的面試問題。
第五天：社交（~小時）：走出房門，開始參加聚會、招聘會，與其他開發(fā)人員和招聘人員見面。
第六天：工作申請（~小時）：搜索「Python Job」，查看 LinkedIn Job 和本地求職網(wǎng)站。選擇 3 個工作崗位并發(fā)送工作申請。為每個工作定制你的簡歷。在每個工作要求中找出 2 到 3 件你不知道的事情，并在接下來的 3-4 天里學(xué)會它們。
第七天：在拒絕中學(xué)習(xí)（~小時）：每次你被拒絕的時候，找出兩件為了獲得這份工作你應(yīng)該知道的事情，然后花 4-5 天 的時間來掌握它們。這樣，每次拒絕都會讓你成為更好的開發(fā)人員。
重慶分公司
重慶分公司
