Python3：怎么通過(guò)遞歸函數(shù)

函數(shù)的遞歸調(diào)用

我們提供的服務(wù)有：做網(wǎng)站、成都網(wǎng)站設(shè)計(jì)、微信公眾號(hào)開發(fā)、網(wǎng)站優(yōu)化、網(wǎng)站認(rèn)證、長(zhǎng)順ssl等。為成百上千家企事業(yè)單位解決了網(wǎng)站和推廣的問(wèn)題。提供周到的售前咨詢和貼心的售后服務(wù)，是有科學(xué)管理、有技術(shù)的長(zhǎng)順網(wǎng)站制作公司

遞歸問(wèn)題是一個(gè)說(shuō)簡(jiǎn)單也簡(jiǎn)單，說(shuō)難也有點(diǎn)難理解的問(wèn)題.我想非常有必要對(duì)其做一個(gè)總結(jié).

首先理解一下遞歸的定義，遞歸就是直接或間接的調(diào)用自身.而至于什么時(shí)候要用到遞歸，遞歸和非遞歸又有那些區(qū)別？又是一個(gè)不太容易掌握的問(wèn)題，更難的是對(duì)于遞歸調(diào)用的理解.下面我們就從程序+圖形的角度對(duì)遞歸做一個(gè)全面的闡述.

我們從常見(jiàn)到的遞歸問(wèn)題開始:

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;

}

這是一個(gè)遞歸求階層函數(shù)的實(shí)現(xiàn)。很多朋友只是知道該這么實(shí)現(xiàn)的，也清楚它是通過(guò)不斷的遞歸調(diào)用求出的結(jié)果.但他們有些不清楚中間發(fā)生了些什么.下面我們用圖對(duì)此做一個(gè)清楚的流程:

根據(jù)上面這個(gè)圖，大家可以很清楚的看出來(lái)這個(gè)函數(shù)的執(zhí)行流程。我們的階層函數(shù)factorial被調(diào)用了4次.并且我們可以看出在調(diào)用后面的調(diào)用中，前面的調(diào)用并不退出。他們同時(shí)存在內(nèi)存中。可見(jiàn)這是一件很浪費(fèi)資源的事情。我們?cè)摯蔚膮?shù)是3.如果我們傳遞10000呢。那結(jié)果就可想而知了.肯定是溢出了.就用int型來(lái)接收結(jié)果別說(shuō)10000，100就會(huì)產(chǎn)生溢出.即使不溢出我想那肯定也是見(jiàn)很浪費(fèi)資源的事情.我們可以做一個(gè)粗略的估計(jì):每次函數(shù)調(diào)用就單變量所需的內(nèi)存為:兩個(gè)int型變量.n和result.在32位機(jī)器上占8B.那么10000就需要10001次函數(shù)調(diào)用.共需10001*8/1024 = 78KB.這只是變量所需的內(nèi)存空間.其它的函數(shù)調(diào)用時(shí)函數(shù)入口地址等仍也需要占用內(nèi)存空間。可見(jiàn)遞歸調(diào)用產(chǎn)生了一個(gè)不小的開銷.

2 斐波那契數(shù)列

int Fib(int n)

{

if (n = 1)

{

return n;

}

else

{

return Fib(n-1) + Fib(n-2);

}

}

這個(gè)函數(shù)遞歸與上面的那個(gè)有些不同.每次調(diào)用函數(shù)都會(huì)引起另外兩次的調(diào)用.最后將結(jié)果逐級(jí)返回.

我們可以看出這個(gè)遞歸函數(shù)同樣在調(diào)用后買的函數(shù)時(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;

}

運(yùn)行結(jié)果:

1

2

3

4

4

3

2

1

該程序中有兩個(gè)遞歸函數(shù)。傳遞同樣的參數(shù)，但他們的輸出結(jié)果剛好相反。理解這兩個(gè)函數(shù)的調(diào)用過(guò)程可以很好的幫助我們理解遞歸:

我想能夠把上面三個(gè)函數(shù)的遞歸調(diào)用過(guò)程理解了，你已經(jīng)把遞歸調(diào)用理解的差不多了.并且從上面的遞歸調(diào)用中我們可以總結(jié)出遞歸的一個(gè)規(guī)律：他是逐級(jí)的調(diào)用，而在函數(shù)結(jié)束的時(shí)候是從最后面往前反序的結(jié)束.這種方式是很占用資源，也很費(fèi)時(shí)的。但是有的時(shí)候使用遞歸寫出來(lái)的程序很容易理解，很易讀.

為什么使用遞歸:

1 有時(shí)候使用遞歸寫出來(lái)的程序很容易理解，很易讀.

2 有些問(wèn)題只有遞歸能夠解決.非遞歸的方法無(wú)法實(shí)現(xiàn).如:漢諾塔.

遞歸的條件:

并不是說(shuō)所有的問(wèn)題都可以使用遞歸解決，他必須的滿足一定的條件。即有一個(gè)出口點(diǎn).也就是說(shuō)當(dāng)滿足一定條件時(shí)，程序可以結(jié)束，從而完成遞歸調(diào)用，否則就陷入了無(wú)限的遞歸調(diào)用之中了.并且這個(gè)條件還要是可達(dá)到的.

遞歸有哪些優(yōu)點(diǎn):

易讀，容易理解，代碼一般比較短.

遞歸有哪些缺點(diǎn):

占用內(nèi)存資源多，費(fèi)時(shí)，效率低下.

因此在我們寫程序的時(shí)候不要輕易的使用遞歸，雖然他有他的優(yōu)點(diǎn)，但是我們要在易讀性和空間，效率上多做權(quán)衡.一般情況下我們還是使用非遞歸的方法解決問(wèn)題.若一個(gè)算法非遞歸解法非常難于理解。我們使用遞歸也未嘗不可.如:二叉樹的遍歷算法.非遞歸的算法很難與理解.而相比遞歸算法就容易理解很多.

對(duì)于遞歸調(diào)用的問(wèn)題，我們?cè)谇耙欢螘r(shí)間寫圖形學(xué)程序時(shí)，其中有一個(gè)四連同填充算法就是使用遞歸的方法。結(jié)果當(dāng)要填充的圖形稍微大一些時(shí)，程序就自動(dòng)關(guān)閉了.這不是一個(gè)人的問(wèn)題，所有人寫出來(lái)的都是這個(gè)問(wèn)題.當(dāng)時(shí)我們給與的解釋就是堆棧溢出。就多次遞歸調(diào)用占用太多的內(nèi)存資源致使堆棧溢出，程序沒(méi)有內(nèi)存資源執(zhí)行下去，從而被操作系統(tǒng)強(qiáng)制關(guān)閉了.這是一個(gè)真真切切的例子。所以我們?cè)谑褂眠f歸的時(shí)候需要權(quán)衡再三.

Python算法-爬樓梯與遞歸函數(shù)

可以看出來(lái)的是，該題可以用斐波那契數(shù)列解決。

樓梯一共有n層，每次只能走1層或者2層，而要走到最終的n層。不是從n-1或者就是n-2來(lái)的。

F(1) = 1

F(2) = 2

F(n) = F(n-1) + F(n-2) (n=3)

這是遞歸寫法，但是會(huì)導(dǎo)致棧溢出。在計(jì)算機(jī)中，函數(shù)的調(diào)用是通過(guò)棧進(jìn)行實(shí)現(xiàn)的，如果遞歸調(diào)用的次數(shù)過(guò)多，就會(huì)導(dǎo)致棧溢出。

針對(duì)這種情況就要使用方法二，改成非遞歸函數(shù)。

將遞歸進(jìn)行改寫，實(shí)現(xiàn)循環(huán)就不會(huì)導(dǎo)致棧溢出

Python該怎么入門?

作為初學(xué)者，第一個(gè)月的月目標(biāo)應(yīng)該是這樣的：

熟悉基本概念（變量，條件，列表，循環(huán)，函數(shù)）

練習(xí)超過(guò) 30 個(gè)編程問(wèn)題

利用這些概念完成兩個(gè)項(xiàng)目

熟悉至少 2 個(gè)框架

開始使用集成開發(fā)環(huán)境（IDE），Github，hosting，services 等

整體計(jì)劃

現(xiàn)在，我們先將月計(jì)劃細(xì)化成周計(jì)劃。

第一周：熟悉 Python

要積極探索 Python 的使用方法，盡可能多的完成下面這些任務(wù)：

第一天：基本概念（4 小時(shí)）：print，變量，輸入，條件語(yǔ)句

第二天：基本概念（5 小時(shí)）：列表，for 循環(huán)，while 循環(huán)，函數(shù)，導(dǎo)入模塊

第三天：簡(jiǎn)單編程問(wèn)題（5 小時(shí)）：交換兩個(gè)變量值，將攝氏度轉(zhuǎn)換為華氏溫度，求數(shù)字中各位數(shù)之和，判斷某數(shù)是否為素?cái)?shù)，生成隨機(jī)數(shù)，刪除列表中的重復(fù)項(xiàng)等等

第四天：中級(jí)編程問(wèn)題（6 小時(shí)）：反轉(zhuǎn)一個(gè)字符串（回文檢測(cè)），計(jì)算最大公約數(shù)，合并兩個(gè)有序數(shù)組，猜數(shù)字游戲，計(jì)算年齡等等

第五天：數(shù)據(jù)結(jié)構(gòu)（6 小時(shí)）：棧，隊(duì)列，字典，元組，樹，鏈表。

第六天：面向?qū)ο缶幊蹋∣OP）（6 小時(shí)）：對(duì)象，類，方法和構(gòu)造函數(shù)，面向?qū)ο缶幊讨^承

第七天：算法（6 小時(shí)）：搜索（線性和二分查找）、排序（冒泡排序、選擇排序）、遞歸函數(shù)（階乘、斐波那契數(shù)列）、時(shí)間復(fù)雜度（線性、二次和常量）

通過(guò)第一周時(shí)間，python大致能熟悉了，自學(xué)能力稍微弱一點(diǎn)找人帶下你，節(jié)約自己的時(shí)間。

注意：別急著安裝 Python 環(huán)境！

這看起來(lái)很矛盾，但是你一定要相信我。我有幾個(gè)朋友，他們因?yàn)檎Z(yǔ)言工具包和 IDE 安裝的失敗而逐漸失去了學(xué)習(xí)下去的欲望。因此，我的建議是先使用一些安卓 app 來(lái)探索這門語(yǔ)言，如果你是個(gè)技術(shù)小白，安裝 Python 環(huán)境可不是你的首要任務(wù)。

第二周：開始軟件開發(fā)（構(gòu)建項(xiàng)目）

接下來(lái)，讓我們朝著軟件開發(fā)任務(wù)進(jìn)軍吧！不妨嘗試綜合你學(xué)到的知識(shí)完成一個(gè)實(shí)際的項(xiàng)目：

第一天：熟悉一種 IDE（5 小時(shí)）: IDE 是你在編寫大型項(xiàng)目時(shí)的操作環(huán)境，所以你需要精通一個(gè) IDE。在軟件開發(fā)的初期，我建議你在 VS code 中安裝 Python 擴(kuò)展或使用 Jupyter notebook。

第二天：Github（6 小時(shí)）：探索 Github，并創(chuàng)建一個(gè)代碼倉(cāng)庫(kù)。嘗試提交（Commit）、查看變更（Diff）和上推（Push）你的代碼。另外，還要學(xué)習(xí)如何利用分支工作，如何合并（merge）不同分支以及如何在一個(gè)項(xiàng)目中創(chuàng)建拉取請(qǐng)求（pull request）。

第三天：第一個(gè)項(xiàng)目——簡(jiǎn)單計(jì)算器（4 小時(shí)）：熟悉 Tkinter，創(chuàng)建一個(gè)簡(jiǎn)單的計(jì)算器

第四、五、六天：個(gè)人項(xiàng)目（每天 5 小時(shí)）：選定一個(gè)項(xiàng)目并完成它。如果你不知道你該做什么，可以查看下面的清單（ pythonprojects -for-an- middle - programmer/answer/jhankar - mahbub2）

第七天：托管項(xiàng)目（5 小時(shí)）：學(xué)習(xí)使用服務(wù)器和 hosting 服務(wù)來(lái)托管你的項(xiàng)目。創(chuàng)建一個(gè) Heroku 設(shè)置并部署你構(gòu)建的應(yīng)用程序。

為什么要寫項(xiàng)目？

如果僅僅按部就班地學(xué)習(xí)課堂上或視頻中的內(nèi)容，你無(wú)法擁有獨(dú)立思考能力。所以，你必須把你的知識(shí)應(yīng)用到一個(gè)項(xiàng)目中。當(dāng)你努力尋找答案時(shí)，你也在慢慢地學(xué)會(huì)這些知識(shí)。

第三周：讓自己成為一名程序員

第 3 周的目標(biāo)是熟悉軟件開發(fā)的整體過(guò)程。你不需要掌握所有的知識(shí)，但是你應(yīng)該知道一些常識(shí)，因?yàn)樗鼈儠?huì)影響你的日常工作。

第一天：數(shù)據(jù)庫(kù)基礎(chǔ)（6 小時(shí)）：基本 SQL 查詢（創(chuàng)建表、選擇、Where 查詢、更新）、SQL 函數(shù)（Avg、Max、Count）、關(guān)系數(shù)據(jù)庫(kù)（規(guī)范化）、內(nèi)連接、外連接等

第二天：使用 Python 數(shù)據(jù)庫(kù)（5 小時(shí)）：利用一種數(shù)據(jù)庫(kù)框架（SQLite 或 panda），連接到一個(gè)數(shù)據(jù)庫(kù)，在多個(gè)表中創(chuàng)建并插入數(shù)據(jù)，再?gòu)谋碇凶x取數(shù)據(jù)。

第三天：API（5 小時(shí)）：如何調(diào)用 API。學(xué)習(xí) JSON、微服務(wù)（micro-service）以及表現(xiàn)層應(yīng)用程序轉(zhuǎn)換應(yīng)用程序接口（Rest API）。

第四天：Numpy（4 小時(shí)）：熟悉 Numpy（- Numpy -for- datascies-beginners-b8088722309f）并練習(xí)前 30 個(gè) Numpy 習(xí)題（- 100/blob/master/100_numpy_excercises.md)

第五、六天：作品集網(wǎng)站（一天 5 小時(shí)）：學(xué)習(xí) Django，使用 Django 構(gòu)建一個(gè)作品集網(wǎng)站（- start-with-django -1/），也要了解一下 Flask 框架。

第七天：?jiǎn)卧獪y(cè)試、日志、調(diào)試（5 小時(shí)）：學(xué)習(xí)單元測(cè)試（PyTest），如何設(shè)置和查看日志，以及使用斷點(diǎn)調(diào)試。

真心話時(shí)間（絕密）

如果你非常「瘋狂」，并且非常專注，你可以在一個(gè)月內(nèi)完成這些任務(wù)。你必須做到：

把學(xué)習(xí) Python 作為你的全職活動(dòng)。你需要從早上 8 點(diǎn)開始學(xué)習(xí)，一直到下午 5 點(diǎn)。在此期間，你可以有一個(gè)午休時(shí)間和茶歇時(shí)間（共 1 小時(shí)）。

8 點(diǎn)列出你今天要學(xué)的東西，然后花一個(gè)小時(shí)復(fù)習(xí)和練習(xí)你昨天學(xué)過(guò)的東西。

從 9 點(diǎn)到 12 點(diǎn)：開始學(xué)習(xí)，并進(jìn)行少量練習(xí)。在午飯后，你需要加大練習(xí)量，如果你卡在某個(gè)問(wèn)題上，可以在網(wǎng)上搜索解決方案。

嚴(yán)格保持每天 4-5 小時(shí)的學(xué)習(xí)時(shí)間和 2-3 小時(shí)的練習(xí)時(shí)間（每周最多可以休息一天）。

你的朋友可能會(huì)認(rèn)為你瘋了。走自己的路，讓別人去說(shuō)吧！

如果你有一份全職工作，或者你是一名學(xué)生，完成這些流程可能需要更長(zhǎng)的時(shí)間。作為一名全日制學(xué)生，我花了 8 個(gè)月的時(shí)間來(lái)完成這份清單。現(xiàn)在我是一名高級(jí)開發(fā)人員。所以，不管花多長(zhǎng)時(shí)間，一定要完成它們。要想成功完成一個(gè)目標(biāo)，必須付出百分之百的努力。

第四周：認(rèn)真考慮工作（實(shí)習(xí)）問(wèn)題

第 4 周的目標(biāo)是認(rèn)真思考如何才能被錄用。即使你現(xiàn)在不想找工作，你也可以在探索這條道路的過(guò)程中學(xué)到很多東西。

第一天：準(zhǔn)備簡(jiǎn)歷（5 小時(shí)）：制作一份一頁(yè)的簡(jiǎn)歷。把你的技能總結(jié)放在最上面，必須在寫項(xiàng)目的同時(shí)附上 Github 鏈接。

第二天：作品集網(wǎng)站（6 小時(shí)）：寫幾個(gè)博客，將它們添加到你之前開發(fā)的作品集網(wǎng)站中。

第三天：LinkedIn 簡(jiǎn)介（4 小時(shí)）：創(chuàng)建一個(gè) LinkedIn 個(gè)人簡(jiǎn)介，把簡(jiǎn)歷上的所有內(nèi)容都放到 LinkedIn 上。

第四天：面試準(zhǔn)備（7 小時(shí)）：準(zhǔn)備一些谷歌常見(jiàn)的面試問(wèn)題，練習(xí)白皮書中的 10 個(gè)面試編程問(wèn)題。在 Glassdoor、Careercup 等網(wǎng)站中查看前人遇到的面試問(wèn)題。

第五天：社交（~小時(shí)）：走出房門，開始參加聚會(huì)、招聘會(huì)，與其他開發(fā)人員和招聘人員見(jiàn)面。

第六天：工作申請(qǐng)（~小時(shí)）：搜索「Python Job」，查看 LinkedIn Job 和本地求職網(wǎng)站。選擇 3 個(gè)工作崗位并發(fā)送工作申請(qǐng)。為每個(gè)工作定制你的簡(jiǎn)歷。在每個(gè)工作要求中找出 2 到 3 件你不知道的事情，并在接下來(lái)的 3-4 天里學(xué)會(huì)它們。

第七天：在拒絕中學(xué)習(xí)（~小時(shí)）：每次你被拒絕的時(shí)候，找出兩件為了獲得這份工作你應(yīng)該知道的事情，然后花 4-5 天 的時(shí)間來(lái)掌握它們。這樣，每次拒絕都會(huì)讓你成為更好的開發(fā)人員。

網(wǎng)站標(biāo)題：python遞歸函數(shù)入門,python 遞歸函數(shù)
鏈接地址：http://chinadenli.net/article20/hsjsjo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站營(yíng)銷、外貿(mào)網(wǎng)站建設(shè)、軟件開發(fā)、云服務(wù)器、網(wǎng)站建設(shè)、電子商務(wù)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)