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

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

創(chuàng)新互聯(lián)公司是一家專注網(wǎng)站建設(shè)、網(wǎng)絡(luò)營銷策劃、小程序定制開發(fā)、電子商務(wù)建設(shè)、網(wǎng)絡(luò)推廣、移動互聯(lián)開發(fā)、研究、服務(wù)為一體的技術(shù)型公司。公司成立10余年以來，已經(jīng)為上千余家自拌料攪拌車各業(yè)的企業(yè)公司提供互聯(lián)網(wǎng)服務(wù)?，F(xiàn)在，服務(wù)的上千余家客戶與我們一路同行，見證我們的成長；未來，我們一起分享成功的喜悅。

樓梯一共有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)致棧溢出。在計(jì)算機(jī)中，函數(shù)的調(diào)用是通過棧進(jìn)行實(shí)現(xiàn)的，如果遞歸調(diào)用的次數(shù)過多，就會導(dǎo)致棧溢出。

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

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

python-027-遞歸-求序列最大值、計(jì)算第n個調(diào)和數(shù)、轉(zhuǎn)換字符到整數(shù)

遞歸，emmmmmmm，擁有一種魅力，接近人的立即思維，容易理解，又不容易理解。

遞歸算法的優(yōu)點(diǎn)： 它使我們能夠簡潔地利用重復(fù)結(jié)構(gòu)呈現(xiàn)諸多問題。通過使算法描述以遞歸的方式利用重復(fù)結(jié)構(gòu)，我們經(jīng)?？梢员荛_復(fù)雜的案例分析和嵌套循環(huán)。這種算法會得出可讀性更強(qiáng)的算法描述，而且十分有效。

但是 ，遞歸的使用要根據(jù)相應(yīng)的成本來看，每次遞歸python解釋器都會給一個空間來記錄函數(shù)活動狀態(tài)。但是有時候內(nèi)存成本很高，有時候?qū)⑦f歸算法轉(zhuǎn)為非遞歸算法是一種好辦法。

當(dāng)然我們可以換解釋器、使用堆棧數(shù)據(jù)結(jié)構(gòu)等方法，來管理遞歸的自身嵌套，減小儲存的活動信息，來減小內(nèi)存消耗。

最近算法學(xué)到了遞歸這一塊，寫了三個課后習(xí)題：

給一個序列S，其中包含n個元素，用遞歸查找其最大值。

輸出：

調(diào)和數(shù)：Hn = 1 + 1/2 + 1/3 + ··· + 1/n

輸出：

例如："12345"class 'str' 轉(zhuǎn)換為12345class 'int'

輸出：

遞歸分為線性遞歸、二路遞歸、多路遞歸。

python 遞歸限制

python不能無限的遞歸調(diào)用下去。并且當(dāng)輸入的值太大，遞歸次數(shù)太多時，python 都會報(bào)錯

首先說結(jié)論，python解釋器這么會限制遞歸次數(shù)，這么做為了避免"無限"調(diào)用導(dǎo)致的堆棧溢出。

tail recursion 就是指在程序最后一步執(zhí)行遞歸。這種函數(shù)稱為 tail recursion function。舉個例子：

這個函數(shù)就是普通的遞歸函數(shù)，它在遞歸之后又進(jìn)行了 乘 的操作。 這種普通遞歸，每一次遞歸調(diào)用都會重新推入一個調(diào)用堆棧。

把上述調(diào)用改成 tail recursion function

tail recursion 的好處是每一次都計(jì)算完，將結(jié)果傳遞給下一次調(diào)用，然后本次調(diào)用任務(wù)就結(jié)束了，不會參與到下一次的遞歸調(diào)用。這種情況下，只重復(fù)用到了一個堆棧。因此可以優(yōu)化結(jié)構(gòu)。就算是多次循環(huán)，也不會出現(xiàn)棧溢出的情況。這就是 tail recursion optimization 。

c和c++都有這種優(yōu)化， python沒有，所以限制了調(diào)用次數(shù)，就是為了防止無限遞歸造成的棧溢出。

如果遞歸次數(shù)過多，導(dǎo)致了開頭的報(bào)錯，可以使用 sys 包手動設(shè)置recursion的limit

手動放大 recursionlimit 限制：

Python 實(shí)現(xiàn)遞歸

一、使用遞歸的背景

先來看一個??接口結(jié)構(gòu)：

這個孩子，他是一個列表，下面有6個元素

展開children下第一個元素[0]看看：

發(fā)現(xiàn)[0]除了包含一些字段信息，還包含了 children 這個字段（喜當(dāng)?shù)?，同時這個children下包含了2個元素：

展開他的第一個元素，不出所料，也含有children字段（人均有娃）

可以理解為children是個對象，他包含了一些屬性，特別的是其中有一個屬性與父級children是一模一樣的，他包含父級children所有的屬性。

比如每個children都包含了一個name字段，我們要拿到所有children里name字段的值，這時候就要用到遞歸啦～

二、find_children.py

拆分理解：

1.首先import requests庫，用它請求并獲取接口返回的數(shù)據(jù)

2.若children以上還有很多層級，可以縮小數(shù)據(jù)范圍，定位到children的上一層級

3.來看看定義的函數(shù)

我們的函數(shù)調(diào)用：find_children(node_f, 'children')

其中，node_f：json字段

??? children：遞歸對象

?以下這段是實(shí)現(xiàn)遞歸的核心：

?? if items['children']:

?items['children']不為None，表示該元素下的children字段還有子類數(shù)據(jù)值，此時滿足if條件，可理解為 if 1。

?items['children']為None，表示該元素下children值為None，沒有后續(xù)可遞歸值，此時不滿足if條件，可理解為 if 0，不會再執(zhí)行if下的語句（不會再遞歸）。

至此，每一層級中children的name以及下一層級children的name就都取出來了

希望到這里能幫助大家理解遞歸的思路，以后根據(jù)這個模板直接套用就行

（晚安啦～）

源碼參考：