谷歌遞歸演算法視頻教程

1. Google:有100階樓梯，從底往上爬，每次爬1階或2階，編演算法說明共有多少走法

設 f(x) = 上x層樓的方法數，那麼，顯然

f(1) = 1
f(2) = 2

因為只有1層樓的話，只有一種方法可以走完，那就是直接走一階；
只有2層樓的話，可以走兩步一階，或者走一步2階，共兩種走法；

考慮一般的 x (x >= 3)：
假如你現在面對 x 層樓梯，你只有兩種選擇：

1. 要麼走一階，變成還剩 x-1 層，這種情況下剩下的樓層共有 f(x-1) 種走法。
2. 要麼走兩階，變成 x-2 層，這種情況下剩下的樓層共有 f(x-2) 種走法。

所以對於一般的 x 層樓梯，你實際上有 f(x-1) + f(x-2) 種走法。

於是就得到了一個遞推公式：

f(1) = 1
f(2) = 2
f(x) = f(x-1) + f(x-2) (x >= 3)

2. 什麼是遞歸遞歸有什麼用

1、程序調用自身的編程技巧稱為遞歸。遞歸做為一種演算法在程序設計語言中廣泛應用。 一個過程或函數在其定義或說明中有直接或間接調用自身的一種方法，它通常把一個大型復雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解，遞歸策略只需少量的程序就可描述出解題過程所需要的多次重復計算，大大地減少了程序的代碼量。遞歸的能力在於用有限的語句來定義對象的無限集合。一般來說，遞歸需要有邊界條件、遞歸前進段和遞歸返回段。當邊界條件不滿足時，遞歸前進；當邊界條件滿足時，遞歸返回。

2、遞歸一般的作用用於解決三類問題：
(1)數據的定義是按遞歸定義的。（Fibonacci函數）
(2)問題解法按遞歸演算法實現。
這類問題雖則本身沒有明顯的遞歸結構，但用遞歸求解比迭代求解更簡單，如Hanoi問題。
(3)數據的結構形式是按遞歸定義的。

3. 計算機裡面什麼是遞歸

在數學和計算機科學中，當一類對象或方法可以由兩個屬性定義時，它們表現出遞歸行為:

簡單的基線條件---不使用遞歸產生答案的終止情況

一組規則將所有其他情形縮減到基線條件

例如，以下是某人祖先的遞歸定義:

某人的父母是他的祖先(基線條件)

某人祖先的祖先也是他的祖先(遞歸步驟)

斐波那契數列是遞歸的經典例子:

Fib(0) = 1 基線條件1；

Fib(1) = 1 基線條件2；

對所有整數n,n > 1時：Fib(n) = (Fib(n-1) + Fib(n-2))。

許多數學公理基於遞歸規則。例如，皮亞諾公理對自然數的形式定義可以描述為:0是自然數，每個自然數都有一個後繼數，它也是自然數。通過這種基線條件和遞歸規則，可以生成所有自然數的集合。

遞歸定義的數學對象包括函數、集合，尤其是分形。

遞歸還有多種開玩笑的「定義」。

非正式定義

俄羅斯娃娃或俄羅斯套娃是遞歸概念的一個物理藝術例子。

自1320年喬托的Stefaneschi三聯畫問世以來，遞歸就一直用於繪畫。它的中央面板包含紅衣主教Stefaneschi的跪像，舉著三聯畫本身作為祭品。

M.C. Eschers 印刷畫廊 (1956)描繪了一個扭曲的城市，其中包含一個遞歸包含圖片的畫廊，因此無限。

4. Google 實時流擁塞控制演算法GCC

1、簡介

參考：https://tools.ietf.org/html/draft-ietf-rmcat-gcc-02#section-4.4

gcc是google實時流擁塞控制演算法的簡稱，已經在webrtc中實現，應用於chrome，後面將應用到Hangouts（視頻聊天產品）中，主要用於視頻流的擁塞控制。

網路瓶頸主要發生在中間的傳輸設備上，比如路由器，所以如果有中間設備的幫助（ECN），網路瓶頸應該會更早並且更准確的被檢測到，gcc屬於端到端的擁塞控制演算法，端到端的演算法將中間路徑想像成一個黑盒子，它不藉助中間設備的幫助，這就增加了網路擁塞預測的難度。端到端的實時流擁塞演算法主要有以下難點：

（1）網路擁塞一般與鏈路容量，當前鏈路中的流量以及即將發送的流量有關，由於路由的不確定性以及鏈路是由多個流共享並且瞬息萬變等原因，對於一個流而言這三個因素都是隨機變數。

（2）擁塞控制演算法要求同一種流（都使用gcc）能夠公平分享帶寬，同時能夠與TCP流公平相處，不會被TCP流搶占帶寬，也盡量不要搶佔TCP流的帶寬。

（3）視頻解碼器對丟包敏感，但實時性又不能使用重傳機制，因為需要盡量減少丟包，另一方面解碼器並不能快速的調整碼率，因而估計出的帶寬盡量平滑，減少毛刺。

2、實現

gcc由基於延遲的控制器和基於丟包的控制器組成，信令基於RTP擴展頭和RTCP傳輸。

（1）反饋和擴展

gcc可以有兩種實現，第一種是兩種控制器都在發送端實現，接收端周期性的反饋到達的每一個包的序列號和到達時間，發送端記錄每一個包的發送時間和到達時間，同時計算出丟包率。第二種是延遲控制器在接收端實現，接收端計算出組間延遲，根據組間延遲計算出發送比特率通過REMB消息反饋給發送端，接收端通過RTCP消息將丟包率反饋給發送端，丟包控制器在發送端實現，發送端通過接收端反饋的信息計算出最終的發送比特率。

（2）發送引擎

定速器用於實現發送固定比特率的視頻包，編碼器產生的數據先會放到定時隊列中，定時器會在每個burst_time發送一組包，burst_time建議為5ms，這一組包的大小是由發送比特率和burst_time計算出來的。

（3）延遲控制器

（3.1）到達時間模型

d(i) = t(i) - t(i-1) - (T(i) - T(i-1)) 

d(i)表示第i組包的延遲和第i-1組包的延遲之差，t(i)表示第i組包的到達時間，取最後一個包的到達時間，T(i)表示第i組包的發送時間，取最後一個包的發送時間，忽略亂序的包。

d(i) > 0說明組間的延遲增大了，d(i) < 0說明組間的延遲減少了，d(i) = 0說明組間的延遲沒變化。

我們將組間延遲建模成 d(i) = w(i)，w(i)是一個隨機過程W的采樣，這個隨機過程是鏈路容量，當前鏈路的流量以及當前發送的比特率的函數。將W建模成白高斯過程。如果我們過度使用鏈路則我們期望w(i)增大，如果鏈路中的隊列正在排空，則意味著w(i)將會減小，其它情況w(i)將是0。

d(i) = w(i) = m(i) + v(i)

m(i)是從w(i)中提取出來的使w(i)的均值為0的部分。v(i)是雜訊項代表網路抖動以及其它模型捕捉不到的影響延遲的因素，v(i)是均值為0的高斯白雜訊，方差var_v = E{v(i)^2}。

（3.2）濾波之前

鏈路中斷會使延遲瞬間變化很大，影響模型的准確計算，所以濾波之前會把一些包合並成一組，如果滿足下面的條件將會合並，（1）一些包的發送時間在一個burst_time內（2）一個包的組間到達時間小於burst_time並且組間延遲d(i)小於0。

（3.3）到達時間濾波

我們將要估計m(i)然後用這個估計值檢測鏈路過載。gcc使用kalman濾波器來估計m(i)。

m(i+1) = m(i) + u(i)

上面的是m(i)的狀態轉移方程。u(i)是狀態雜訊，將它建模成均值為0，方差為q(i)的符合高斯統計的穩態過程，其中q(i) = E{u(i)^2}，q(i)建議值為10^-3。

kalman濾波器遞歸地更新m(i)的估計值m_hat(i)

z(i) = d(i) - m_hat(i-1)

m_hat(i) = m_hat(i-1) + z(i) * k(i)

 k(i) = (e(i-1) + q(i)) / var_v_hat(i) + (e(i-1) + q(i))

e(i) = (1 - k(i)) * (e(i-1) + q(i))

其中；

var_v_hat(i) = max(alpha * var_v_hat(i-1) + (1-alpha) * z(i)^2, 1)

alpha = (1-chi)^(30/(1000 * f_max))

f_max = max {1/(T(j) - T(j-1))} for j in i-K+1,...,i 代表最近K組包的最大發送頻率。

（3.4）過載探測

用到達時間濾波模塊估計出的組間延遲m(i)與閾值del_var_th(i)進行比較，如果m(i) > del_var_th(i)則意味著過載，這一個條件還不能給速率控制系統發送過載信號，檢測的過載時間最少維持overuse_time_th毫秒，並且不能出現m(i) < m(i-1)的情況。相反的情況，如果m(i) < -del_var_th(i)則意味著網路使用不足，最後一種情況是正常狀態。

del_var_th對演算法的整體模擬和性能有很大的影響，另外如果del_var_th取一個固定的值，將會被當前的TCP流佔用帶寬導致飢餓的產生。這個飢餓可以通過將del_var_th設置成足夠大的值而避免。因而有必要動態調整del_var_th去獲取更好的性能，例如與基於丟包的流的競爭中。

del_var_th(i) = del_var_th(i-1) + (t(i)-t(i-1)) * K(i) * (|m(i)|-del_var_th(i-1))

另外，如果|m(i)| - del_var_th(i) > 15時不更新del_var_th(i)，並且del_var_th(i) 在[6, 600]區間內。

（3.5）速率控制器

當檢測到過載，延遲控制器估計的有效帶寬將會減少，通過這種方式獲得一個遞歸的自適應的有效帶寬估計。

速率控制子系統有3個狀態，Increase, Decrease 和Hold狀態。當沒有檢測出擁塞時是Increase狀態，檢測出擁塞時是Decrease狀態，Hold狀態表示等待隊列清空的過程。

增大當前有效帶寬將使用乘法或加法，取決於當前的狀態，如果當前估計的帶寬離擁塞較遠，則使用乘法，如果接近擁塞，則使用加法。如果當前的比特率R_hat(i)接近之前Decrease狀態的平均比特率則認為接近擁塞。

R_hat(i)是延遲控制器在T秒鍾的窗口中計算出來的接收比特率：

R_hat(i) = 1/T * sum(L(j)) for j from 1 to N(i)

其中N(i)是T秒鍾接收的包數，L(j)是第j個包的負載長度。窗口建議設置成0.5秒到1秒之間。

eta = 1.08^min(time_since_last_update_ms / 1000, 1.0)

A_hat(i) = eta * A_hat(i-1)

在加法增長階段，估計值在response_time最多增長半個包的長度。

response_time_ms = 100 + rtt_ms

alpha = 0.5 * min(time_since_last_update_ms / response_time_ms, 1.0)

A_hat(i) = A_hat(i-1) + max(1000, alpha * expected_packet_size_bits)

expected_packet_size_bits用於在低碼率時獲得一個緩慢的增長。它可以根據當前的碼率估算出來。

bits_per_frame = A_hat(i-1) / 30

packets_per_frame = ceil(bits_per_frame / (1200 * 8))

avg_packet_size_bits = bits_per_frame / packets_per_frame

之前的討論都是假設鏈路會出現擁塞，如果發送端產生不了足夠的比特流，估計的有效帶寬需要保持在一個給定的范圍內。

A_hat(i) < 1.5 * R_hat(i)

如果檢測到過載，則進入Decrease狀態，延遲控制器估計的有效帶寬會減少。

A_hat(i) = beta * R_hat(i)

beta一般選擇屬於[0.8, 0.95]，一般建議是0.85。

（4）丟包控制器

定義丟包控制器估計有效帶寬為As_hat。

延遲控制器估計的有效帶寬只在隊列足夠大時有效，如果隊列較小，就需要使用丟包率檢測過載。

As_hat(i) = As_hat(i - 1)      （2 < p < 10%）

As_hat(i) = As_hat(i-1)(1-0.5p） （p > 10%）

As_hat(i) = 1.05(As_hat(i-1))      (p < 2%)

真實的發送速率設置成丟包控制器估計值和延遲控制器估計值的較小的。

我們觀察到由於過載出現少量的丟包，如果不調整發送的比特率，丟包率會快速增長到達10%門限值然後調整發送比特率。然而，如果丟包率不增加，擁塞很可能不是自己造成的，因而不需要進行調整。

（5）互操作

如果發送端實現了這個演算法，但是接收端沒有實現RTCP消息和RTP頭擴展，建議發送端檢測RTCP的接收端報告，然後使用丟包率和rtt做為丟包控制器的輸入，關閉延遲控制器。

註：服務中的自適應流控也可以參考GCC，後面這個是BRPC的流控： BRPC自適應流控

5. 15個變態的谷歌面試問題的答案

十二題可是初三上學期的物理題啊,關於天平的!
答案是:把八個硬幣其中3個放左盤,在選另外3個放右盤,其餘兩個先不管,如果兩個盤一樣重,則重的硬幣在剩下的兩個硬幣中,在稱這兩個硬幣,ok.若其中一個盤較重,就把這個盤的三個硬幣,其中一個放左盤,另一個放右盤再測,如果相等,則重的是剩下的1個硬幣,如果天平不平衡,則重的硬幣在較重的盤上.
第五題則是關於數學幾何圖形,大概是初二初三接觸過的,要知道井蓋在路上,肯定是有東西在井蓋的邊緣托住他,井蓋才不會掉下去,而這個邊緣是很小的.那麼井蓋是圓的話,半徑相等,如果井蓋因某種原因而打側放的話由於直徑比邊緣要長,不至於令井蓋掉下去.如果井蓋是矩形的話,一打側他就會掉下去了,因為矩形由兩個直角三角形組成,而直角三角形的斜邊較長.如果照這樣說等邊三角形也應該可以啊,一些不規則圖形也可以,可能也有美觀這一因素在吧,又或者是井蓋作者先想到圓井蓋,後來全世界都圓井蓋了,就沒人在意去計較為什麼不用等邊三角形井蓋了...由於所學知識有限,當時我問老師為什麼不能用等邊三角形,老師沒答我.不能給你證明,抱歉.
第七題,首先思考一下,每一秒分針時針都在轉動,那麼在重合的時候的下一秒,時針分針會不會再重合一次?想深一層,我覺得應從圓的度數方面考慮,通過計算得知,分針每走一小格(一分鍾),走了6度,而時針走了0.5度.那麼,假如現在是十二點,時針分針都指在了"12"上,這時重合了一次,但每走一秒,分針都有微妙的轉動,而時針也是,那麼一秒分針轉動了6/60=0.1度,時針轉動了0.5/60=0.008333度,即是說,在重合時的下一秒,分針就已經超越了時針,所以一小時只重合一次!(個人認為,本人僅是初三學生,這可能不是正確答案).我覺得,一天24小時,自然是24次.
第十一題屬於推理題目,我不知道(呵呵),不過在網上有類似這道題的:海盜分金幣,有五個海盜,一號首先開始分金幣,如果他的分配方法得不到半數的同意就處死並讓下一位去分,這題已有詳細答案(很久前就看過了),答案是:逆向思維。
假設每一個海盜都是絕頂聰明而理性，他們都能夠進行嚴密的邏輯推理，並能很理智的判斷自身的得失，即能夠在保住性命的前提下得到最多的金幣。同時還假設每一輪表決後的結果都能順利得到執行，那麼抽到1號的海盜應該提出怎樣的分配方案才能使自己既不被扔進海里，又可以得到更多的金幣呢？
此題公認的標准答案是：1號海盜分給3號1枚金幣，4號或5號2枚金幣，自己則獨得97枚金幣，即分配方案為（97，0，1，2，0）或（97，0，1，0，2）。現來看如下各人的理性分析：
首先從5號海盜開始，因為他是最安全的，沒有被扔下大海的風險，因此他的策略也最為簡單，即最好前面的人全都死光光，那麼他就可以獨得這100枚金幣了。
接下來看4號，他的生存機會完全取決於前面還有人存活著，因為如果1號到3號的海盜全都餵了鯊魚，那麼在只剩4號與5號的情況下，不管4號提出怎樣的分配方案，5號一定都會投反對票來讓4號去喂鯊魚，以獨吞全部的金幣。哪怕4號為了保命而討好5號，提出（0，100）這樣的方案讓5號獨占金幣，但是5號還有可能覺得留著4號有危險，而投票反對以讓其喂鯊魚。因此理性的4號是不應該冒這樣的風險，把存活的希望寄託在5號的隨機選擇上的，他惟有支持3號才能絕對保證自身的性命。
再來看3號，他經過上述的邏輯推理之後，就會提出（100，0，0）這樣的分配方案，因為他知道4號哪怕一無所獲，也還是會無條件的支持他而投贊成票的，那麼再加上自己的1票就可以使他穩獲這100金幣了。
但是，2號也經過推理得知了3號的分配方案，那麼他就會提出（98，0，1，1）的方案。因為這個方案相對於3號的分配方案，4號和5號至少可以獲得1枚金幣，理性的4號和5號自然會覺得此方案對他們來說更有利而支持2號，不希望2號出局而由3號來進行分配。這樣，2號就可以屁顛屁顛的拿走98枚金幣了。
不幸的是，1號海盜更不是省油的燈，經過一番推理之後也洞悉了2號的分配方案。他將採取的策略是放棄2號，而給3號1枚金幣，同時給4號或5號2枚金幣，即提出（97，0，1，2，0）或（97，0，1，0，2）的分配方案。由於1號的分配方案對於3號與4號或5號來說，相比2號的方案可以獲得更多的利益，那麼他們將會投票支持1號，再加上1號自身的1票，97枚金幣就可輕松落入1號的腰包了 .但是google的這道題無明確條件,只說如果得不到同意就死,沒其他的了,如果船員不管三七二十一全讓你死,那你怎麼辦?或許這題不應用邏輯分析,而是從社會現實角度,例如巴結好熟人之類的呵呵~~
第十題好像在某本書上看過,不過沒有寫答案,我是這樣想的,既然要讓他不知道號碼,就不能夠在紙上寫,那麼就只能夠用手機確認了:讓鮑伯撥打我的手機號碼.
第十五題,我想出的答案有很多,這種腦筋急轉彎式的題在大家眼中有無數答案,但出題人只看他手中的正確答案,所以我把我最雷的一個給你參考吧:如果只有硬幣這么小,從平面看攪拌器一般成接近四邊形五邊形的形狀,攪拌刀片轉動時是圓,嗎么就直接站在攪拌刀片切不到你的死角位置不就ok了?
第三題,生物學解釋,生男生女比例1比1,因為概率問題只是大概估算,並無准確答案,考方只想看你的解題思路罷了,我是這樣解的:既然是一比1,那麼就是要麼先生男,要麼先生女,由於是大概估算,那麼看作每生兩次就有一男一女(現實是不可能),即是:先生男的話就不再生,如果生女的話就會在生一個男,把他認作只有這兩種情況,且概率都是一比一,就是說兩男一女,所以比例就是二比一.
第八題,我不會,不過網上有網友的見解:對於一個軟體工程師來說，是要盡量避免在軟體中「死牛肉」出現。它不但對軟體本身沒有好處，還會給整個軟體帶來破壞。死牛肉不但不能吃還會引來許多倉蠅之類的害蟲。
其他題大多屬於主觀題,沒絕對答案,出題人只想看你的思路.不過我已經把能說的都給你說了,只看答案沒有用關鍵是分析,希望我用了1小時的長篇大論對你有幫助

參考資料： 網路大神,老師的諄諄教導

6. 如何用PyTorch實現遞歸神經網路

從 Siri 到谷歌翻譯，深度神經網路已經在機器理解自然語言方面取得了巨大突破。這些模型大多數將語言視為單調的單詞或字元序列，並使用一種稱為循環神經網路（recurrent neural network/RNN）的模型來處理該序列。但是許多語言學家認為語言最好被理解為具有樹形結構的層次化片語，一種被稱為遞歸神經網路（recursive neural network）的深度學習模型考慮到了這種結構，這方面已經有大量的研究。雖然這些模型非常難以實現且效率很低，但是一個全新的深度學習框架 PyTorch 能使它們和其它復雜的自然語言處理模型變得更加容易。

雖然遞歸神經網路很好地顯示了 PyTorch 的靈活性，但它也廣泛支持其它的各種深度學習框架，特別的是，它能夠對計算機視覺（computer vision）計算提供強大的支撐。PyTorch 是 Facebook AI Research 和其它幾個實驗室的開發人員的成果，該框架結合了 Torch7 高效靈活的 GPU 加速後端庫與直觀的 Python 前端，它的特點是快速成形、代碼可讀和支持最廣泛的深度學習模型。

開始 SPINN

鏈接中的文章（https://github.com/jekbradbury/examples/tree/spinn/snli）詳細介紹了一個遞歸神經網路的 PyTorch 實現，它具有一個循環跟蹤器（recurrent tracker）和 TreeLSTM 節點，也稱為 SPINN——SPINN 是深度學習模型用於自然語言處理的一個例子，它很難通過許多流行的框架構建。這里的模型實現部分運用了批處理（batch），所以它可以利用 GPU 加速，使得運行速度明顯快於不使用批處理的版本。

SPINN 的意思是堆棧增強的解析器-解釋器神經網路（Stack-augmented Parser-Interpreter Neural Network），由 Bowman 等人於 2016 年作為解決自然語言推理任務的一種方法引入，該論文中使用了斯坦福大學的 SNLI 數據集。

該任務是將語句對分為三類：假設語句 1 是一幅看不見的圖像的准確標題，那麼語句 2（a）肯定（b）可能還是（c）絕對不是一個准確的標題？（這些類分別被稱為蘊含（entailment）、中立（neutral）和矛盾（contradiction））。例如，假設一句話是「兩只狗正跑過一片場地」，蘊含可能會使這個語句對變成「戶外的動物」，中立可能會使這個語句對變成「一些小狗正在跑並試圖抓住一根棍子」，矛盾能會使這個語句對變成「寵物正坐在沙發上」。

特別地，研究 SPINN 的初始目標是在確定語句的關系之前將每個句子編碼（encoding）成固定長度的向量表示（也有其它方式，例如注意模型（attention model）中將每個句子的每個部分用一種柔焦（soft focus）的方法相互比較）。

數據集是用句法解析樹（syntactic parse tree）方法由機器生成的，句法解析樹將每個句子中的單詞分組成具有獨立意義的短語和子句，每個短語由兩個詞或子短語組成。許多語言學家認為，人類通過如上面所說的樹的分層方式來組合詞意並理解語言，所以用相同的方式嘗試構建一個神經網路是值得的。下面的例子是數據集中的一個句子，其解析樹由嵌套括弧表示：

( ( The church ) ( ( has ( cracks ( in ( the ceiling ) ) ) ) . ) )

這個句子進行編碼的一種方式是使用含有解析樹的神經網路構建一個神經網路層 Rece，這個神經網路層能夠組合詞語對（用詞嵌入（word embedding）表示，如 GloVe）、 和/或短語，然後遞歸地應用此層（函數），將最後一個 Rece 產生的結果作為句子的編碼：

X = Rece(「the」, 「ceiling」)
Y = Rece(「in」, X)
... etc.

但是，如果我希望網路以更類似人類的方式工作，從左到右閱讀並保留句子的語境，同時仍然使用解析樹組合短語？或者，如果我想訓練一個網路來構建自己的解析樹，讓解析樹根據它看到的單詞讀取句子？這是一個同樣的但方式略有不同的解析樹的寫法：

The church ) has cracks in the ceiling ) ) ) ) . ) )

或者用第 3 種方式表示，如下：

WORDS: The church has cracks in the ceiling .
PARSES: S S R S S S S S R R R R S R R

我所做的只是刪除開括弧，然後用「S」標記「shift」，並用「R」替換閉括弧用於「rece」。但是現在可以從左到右讀取信息作為一組指令來操作一個堆棧（stack）和一個類似堆棧的緩沖區（buffer），能得到與上述遞歸方法完全相同的結果：

1. 將單詞放入緩沖區。
2. 從緩沖區的前部彈出「The」，將其推送（push）到堆棧上層，緊接著是「church」。
3. 彈出前 2 個堆棧值，應用於 Rece，然後將結果推送回堆棧。
4. 從緩沖區彈出「has」，然後推送到堆棧，然後是「cracks」，然後是「in」，然後是「the」，然後是「ceiling」。
5. 重復四次：彈出 2 個堆棧值，應用於 Rece，然後推送結果。
6. 從緩沖區彈出「.」，然後推送到堆棧上層。
7. 重復兩次：彈出 2 個堆棧值，應用於 Rece，然後推送結果。
8. 彈出剩餘的堆棧值，並將其作為句子編碼返回。

我還想保留句子的語境，以便在對句子的後半部分應用 Rece 層時考慮系統已經讀取的句子部分的信息。所以我將用一個三參數函數替換雙參數的 Rece 函數，該函數的輸入值為一個左子句、一個右子句和當前句的上下文狀態。該狀態由神經網路的第二層（稱為循環跟蹤器（Tracker）的單元）創建。Tracker 在給定當前句子上下文狀態、緩沖區中的頂部條目 b 和堆棧中前兩個條目 s1\s2 時，在堆棧操作的每個步驟（即，讀取每個單詞或閉括弧）後生成一個新狀態：

context[t+1] = Tracker(context[t], b, s1, s2)

容易設想用你最喜歡的編程語言來編寫代碼做這些事情。對於要處理的每個句子，它將從緩沖區載入下一個單詞，運行跟蹤器，檢查是否將單詞推送入堆棧或執行 Rece 函數，執行該操作；然後重復，直到對整個句子完成處理。通過對單個句子的應用，該過程構成了一個大而復雜的深度神經網路，通過堆棧操作的方式一遍又一遍地應用它的兩個可訓練層。但是，如果你熟悉 TensorFlow 或 Theano 等傳統的深度學習框架，就知道它們很難實現這樣的動態過程。你值得花點時間回顧一下，探索為什麼 PyTorch 能有所不同。

圖論

圖 1：一個函數的圖結構表示

深度神經網路本質上是有大量參數的復雜函數。深度學習的目的是通過計算以損失函數（loss）度量的偏導數（梯度）來優化這些參數。如果函數表示為計算圖結構（圖 1），則向後遍歷該圖可實現這些梯度的計算，而無需冗餘工作。每個現代深度學習框架都是基於此反向傳播（backpropagation）的概念，因此每個框架都需要一個表示計算圖的方式。

在許多流行的框架中，包括 TensorFlow、Theano 和 Keras 以及 Torch7 的 nngraph 庫，計算圖是一個提前構建的靜態對象。該圖是用像數學表達式的代碼定義的，但其變數實際上是尚未保存任何數值的佔位符（placeholder）。圖中的佔位符變數被編譯進函數，然後可以在訓練集的批處理上重復運行該函數來產生輸出和梯度值。

這種靜態計算圖（static computation graph）方法對於固定結構的卷積神經網路效果很好。但是在許多其它應用中，有用的做法是令神經網路的圖結構根據數據而有所不同。在自然語言處理中，研究人員通常希望通過每個時間步驟中輸入的單詞來展開（確定）循環神經網路。上述 SPINN 模型中的堆棧操作很大程度上依賴於控制流程（如 for 和 if 語句）來定義特定句子的計算圖結構。在更復雜的情況下，你可能需要構建結構依賴於模型自身的子網路輸出的模型。

這些想法中的一些（雖然不是全部）可以被生搬硬套到靜態圖系統中，但幾乎總是以降低透明度和增加代碼的困惑度為代價。該框架必須在其計算圖中添加特殊的節點，這些節點代表如循環和條件的編程原語（programming primitive），而用戶必須學習和使用這些節點，而不僅僅是編程代碼語言中的 for 和 if 語句。這是因為程序員使用的任何控制流程語句將僅運行一次，當構建圖時程序員需要硬編碼（hard coding）單個計算路徑。

例如，通過詞向量（從初始狀態 h0 開始）運行循環神經網路單元（rnn_unit）需要 TensorFlow 中的特殊控制流節點 tf.while_loop。需要一個額外的特殊節點來獲取運行時的詞長度，因為在運行代碼時它只是一個佔位符。

# TensorFlow
# (this code runs once, ring model initialization)
# 「words」 is not a real list (it』s a placeholder variable) so
# I can』t use 「len」
cond = lambda i, h: i < tf.shape(words)[0]
cell = lambda i, h: rnn_unit(words[i], h)
i = 0
_, h = tf.while_loop(cond, cell, (i, h0))

基於動態計算圖（dynamic computation graph）的方法與之前的方法有根本性不同，它有幾十年的學術研究歷史，其中包括了哈佛的 Kayak、自動微分庫（autograd）以及以研究為中心的框架 Chainer和 DyNet。在這樣的框架（也稱為運行時定義（define-by-run））中，計算圖在運行時被建立和重建，使用相同的代碼為前向通過（forward pass）執行計算，同時也為反向傳播（backpropagation）建立所需的數據結構。這種方法能產生更直接的代碼，因為控制流程的編寫可以使用標準的 for 和 if。它還使調試更容易，因為運行時斷點（run-time breakpoint）或堆棧跟蹤（stack trace）將追蹤到實際編寫的代碼，而不是執行引擎中的編譯函數。可以在動態框架中使用簡單的 Python 的 for 循環來實現有相同變數長度的循環神經網路。

# PyTorch (also works in Chainer)
# (this code runs on every forward pass of the model)
# 「words」 is a Python list with actual values in it
h = h0
for word in words:
h = rnn_unit(word, h)

PyTorch 是第一個 define-by-run 的深度學習框架，它與靜態圖框架（如 TensorFlow）的功能和性能相匹配，使其能很好地適合從標准卷積神經網路（convolutional network）到最瘋狂的強化學習（reinforcement learning）等思想。所以讓我們來看看 SPINN 的實現。

代碼

在開始構建網路之前，我需要設置一個數據載入器（data loader）。通過深度學習，模型可以通過數據樣本的批處理進行操作，通過並行化（parallelism）加快訓練，並在每一步都有一個更平滑的梯度變化。我想在這里可以做到這一點（稍後我將解釋上述堆棧操作過程如何進行批處理）。以下 Python 代碼使用內置於 PyTorch 的文本庫的系統來載入數據，它可以通過連接相似長度的數據樣本自動生成批處理。運行此代碼之後，train_iter、dev_iter 和 test_itercontain 循環遍歷訓練集、驗證集和測試集分塊 SNLI 的批處理。

from torchtext import data, datasets
TEXT = datasets.snli.ParsedTextField(lower=True)
TRANSITIONS = datasets.snli.ShiftReceField()
LABELS = data.Field(sequential=False)train, dev, test = datasets.SNLI.splits(
TEXT, TRANSITIONS, LABELS, wv_type='glove.42B')TEXT.build_vocab(train, dev, test)
train_iter, dev_iter, test_iter = data.BucketIterator.splits(
(train, dev, test), batch_size=64)

你可以在 train.py中找到設置訓練循環和准確性（accuracy）測量的其餘代碼。讓我們繼續。如上所述，SPINN 編碼器包含參數化的 Rece 層和可選的循環跟蹤器來跟蹤句子上下文，以便在每次網路讀取單詞或應用 Rece 時更新隱藏狀態；以下代碼代表的是，創建一個 SPINN 只是意味著創建這兩個子模塊（我們將很快看到它們的代碼），並將它們放在一個容器中以供稍後使用。

import torchfrom torch import nn
# subclass the Mole class from PyTorch』s neural network package
class SPINN(nn.Mole):
def __init__(self, config):
super(SPINN, self).__init__()
self.config = config self.rece = Rece(config.d_hidden, config.d_tracker)
if config.d_tracker is not None:
self.tracker = Tracker(config.d_hidden, config.d_tracker)

當創建模型時，SPINN.__init__ 被調用了一次；它分配和初始化參數，但不執行任何神經網路操作或構建任何類型的計算圖。在每個新的批處理數據上運行的代碼由 SPINN.forward 方法定義，它是用戶實現的方法中用於定義模型向前過程的標准 PyTorch 名稱。上面描述的是堆棧操作演算法的一個有效實現，即在一般 Python 中，在一批緩沖區和堆棧上運行，每一個例子都對應一個緩沖區和堆棧。我使用轉移矩陣（transition）包含的「shift」和「rece」操作集合進行迭代，運行 Tracker（如果存在），並遍歷批處理中的每個樣本來應用「shift」操作（如果請求），或將其添加到需要「rece」操作的樣本列表中。然後在該列表中的所有樣本上運行 Rece 層，並將結果推送回到它們各自的堆棧。

def forward(self, buffers, transitions):
# The input comes in as a single tensor of word embeddings;
# I need it to be a list of stacks, one for each example in
# the batch, that we can pop from independently. The words in
# each example have already been reversed, so that they can
# be read from left to right by popping from the end of each
# list; they have also been prefixed with a null value.
buffers = [list(torch.split(b.squeeze(1), 1, 0))
for b in torch.split(buffers, 1, 1)]
# we also need two null values at the bottom of each stack,
# so we can from the nulls in the input; these nulls
# are all needed so that the tracker can run even if the
# buffer or stack is empty
stacks = [[buf[0], buf[0]] for buf in buffers]
if hasattr(self, 'tracker'):
self.tracker.reset_state()
for trans_batch in transitions:
if hasattr(self, 'tracker'):
# I described the Tracker earlier as taking 4
# arguments (context_t, b, s1, s2), but here I
# provide the stack contents as a single argument
# while storing the context inside the Tracker
# object itself.
tracker_states, _ = self.tracker(buffers, stacks)
else:
tracker_states = itertools.repeat(None)
lefts, rights, trackings = [], [], []
batch = zip(trans_batch, buffers, stacks, tracker_states)
for transition, buf, stack, tracking in batch:
if transition == SHIFT:
stack.append(buf.pop())
elif transition == REDUCE:
rights.append(stack.pop())
lefts.append(stack.pop())
trackings.append(tracking)
if rights:
reced = iter(self.rece(lefts, rights, trackings))
for transition, stack in zip(trans_batch, stacks):
if transition == REDUCE:
stack.append(next(reced))
return [stack.pop() for stack in stacks]

在調用 self.tracker 或 self.rece 時分別運行 Tracker 或 Rece 子模塊的向前方法，該方法需要在樣本列表上應用前向操作。在主函數的向前方法中，在不同的樣本上進行獨立的操作是有意義的，即為批處理中每個樣本提供分離的緩沖區和堆棧，因為所有受益於批處理執行的重度使用數學和需要 GPU 加速的操作都在 Tracker 和 Rece 中進行。為了更干凈地編寫這些函數，我將使用一些 helper（稍後將定義）將這些樣本列表轉化成批處理張量（tensor），反之亦然。

我希望 Rece 模塊自動批處理其參數以加速計算，然後解批處理（unbatch）它們，以便可以單獨推送和彈出。用於將每對左、右子短語表達組合成父短語（parent phrase）的實際組合函數是 TreeLSTM，它是普通循環神經網路單元 LSTM 的變型。該組合函數要求每個子短語的狀態實際上由兩個張量組成，一個隱藏狀態 h 和一個存儲單元（memory cell）狀態 c，而函數是使用在子短語的隱藏狀態操作的兩個線性層（nn.Linear）和將線性層的結果與子短語的存儲單元狀態相結合的非線性組合函數 tree_lstm。在 SPINN 中，這種方式通過添加在 Tracker 的隱藏狀態下運行的第 3 個線性層進行擴展。

圖 2：TreeLSTM 組合函數增加了第 3 個輸入（x，在這種情況下為 Tracker 狀態）。在下面所示的 PyTorch 實現中，5 組的三種線性變換（由藍色、黑色和紅色箭頭的三元組表示）組合為三個 nn.Linear 模塊，而 tree_lstm 函數執行位於框內的所有計算。圖來自 Chen et al. (2016)。

7. 怎樣用遞歸的方法遍歷棧

如何用棧實現遞歸與非遞歸的轉換
分類： C/C++2010-07-12 14:4012人閱讀評論(0)收藏舉報
如何用棧實現遞歸與非遞歸的轉換一.為什麼要學習遞歸與非遞歸的轉換的實現方法? 1)並不是每一門語言都支持遞歸的. 2)有助於理解遞歸的本質. 3)有助於理解棧,樹等數據結構.二.遞歸與非遞歸轉換的原理. 遞歸與非遞歸的轉換基於以下的原理:所有的遞歸程序都可以用樹結構表示出來.需要說明的是,這個"原理"並沒有經過嚴格的數學證明,只是我的一個猜想,不過在至少在我遇到的例子中是適用的. 學習過樹結構的人都知道,有三種方法可以遍歷樹:前序,中序,後序.理解這三種遍歷方式的遞歸和非遞歸的表達方式是能夠正確實現轉換的關鍵之處,所以我們先來談談這個.需要說明的是,這里以特殊的二叉樹來說明,不過大多數情況下二叉樹已經夠用,而且理解了二叉樹的遍歷,其它的樹遍歷方式就不難了. 1)前序遍歷 a)遞歸方式:
void preorder_recursive(Bitree T) /* 先序遍歷二叉樹的遞歸演算法 */
{
if (T) {
visit(T); /* 訪問當前結點 */
preorder_recursive(T->;lchild); /* 訪問左子樹 */
preorder_recursive(T->;rchild); /* 訪問右子樹 */
}
}
復制代碼
b)非遞歸方式
void preorder_nonrecursive(Bitree T) /* 先序遍歷二叉樹的非遞歸演算法 */
{
initstack(S);
push(S,T); /* 根指針進棧 */
while(!stackempty(S)) {
while(gettop(S,p)&&p) { /* 向左走到盡頭 */
visit(p); /* 每向前走一步都訪問當前結點 */
push(S,p->;lchild);
}
pop(S,p);
if(!stackempty(S)) { /* 向右走一步 */
pop(S,p);
push(S,p->;rchild);
}
}
}
復制代碼
2)中序遍歷 a)遞歸方式
void inorder_recursive(Bitree T) /* 中序遍歷二叉樹的遞歸演算法 */
{
if (T) {
inorder_recursive(T->;lchild); /* 訪問左子樹 */
visit(T); /* 訪問當前結點 */
inorder_recursive(T->;rchild); /* 訪問右子樹 */
}
}
復制代碼
b)非遞歸方式
void inorder_nonrecursive(Bitree T)
{
initstack(S); /* 初始化棧 */
push(S, T); /* 根指針入棧 */
while (!stackempty(S)) {
while (gettop(S, p) && p) /* 向左走到盡頭 */
push(S, p->;lchild);
pop(S, p); /* 空指針退棧 */
if (!stackempty(S)) {
pop(S, p);
visit(p); /* 訪問當前結點 */
push(S, p->;rchild); /* 向右走一步 */
}
}
}
復制代碼
3)後序遍歷 a)遞歸方式
void postorder_recursive(Bitree T) /* 中序遍歷二叉樹的遞歸演算法 */
{
if (T) {
postorder_recursive(T->;lchild); /* 訪問左子樹 */
postorder_recursive(T->;rchild); /* 訪問右子樹 */
visit(T); /* 訪問當前結點 */
}
}
復制代碼
b)非遞歸方式
typedef struct {
BTNode* ptr;
enum {0,1,2} mark;
} PMType; /* 有mark域的結點指針類型 */
void postorder_nonrecursive(BiTree T) /* 後續遍歷二叉樹的非遞歸演算法 */
{
PMType a;
initstack(S); /* S的元素為PMType類型 */
push (S,{T,0}); /* 根結點入棧 */
while(!stackempty(S)) {
pop(S,a);
switch(a.mark)
{
case 0:
push(S,{a.ptr,1}); /* 修改mark域 */
if(a.ptr->;lchild)
push(S,{a.ptr->;lchild,0}); /* 訪問左子樹 */
break;
case 1:
push(S,{a.ptr,2}); /* 修改mark域 */
if(a.ptr->;rchild)
push(S,{a.ptr->;rchild,0}); /* 訪問右子樹 */
break;
case 2:
visit(a.ptr); /* 訪問結點 */
}
}
}
復制代碼
4)如何實現遞歸與非遞歸的轉換 通常,一個函數在調用另一個函數之前,要作如下的事情:a)將實在參數,返回地址等信息傳遞 給被調用函數保存; b)為被調用函數的局部變數分配存儲區;c)將控制轉移到被調函數的入口. 從被調用函數返回調用函數之前,也要做三件事情:a)保存被調函數的計算結果;b)釋放被調 函數的數據區;c)依照被調函數保存的返回地址將控制轉移到調用函數. 所有的這些,不論是變數還是地址,本質上來說都是"數據",都是保存在系統所分配的棧中的. ok,到這里已經解決了第一個問題:遞歸調用時數據都是保存在棧中的,有多少個數據需要保存 就要設置多少個棧,而且最重要的一點是:控制所有這些棧的棧頂指針都是相同的,否則無法實現 同步. 下面來解決第二個問題:在非遞歸中,程序如何知道到底要轉移到哪個部分繼續執行?回到上 面說的樹的三種遍歷方式,抽象出來只有三種操作:訪問當前結點,訪問左子樹,訪問右子樹.這三 種操作的順序不同,遍歷方式也不同.如果我們再抽象一點,對這三種操作再進行一個概括,可以 得到:a)訪問當前結點:對目前的數據進行一些處理;b)訪問左子樹:變換當前的數據以進行下一次 處理;c)訪問右子樹:再次變換當前的數據以進行下一次處理(與訪問左子樹所不同的方式). 下面以先序遍歷來說明:
void preorder_recursive(Bitree T) /* 先序遍歷二叉樹的遞歸演算法 */
{
if (T) {
visit(T); /* 訪問當前結點 */
preorder_recursive(T->;lchild); /* 訪問左子樹 */
preorder_recursive(T->;rchild); /* 訪問右子樹 */
}
}
復制代碼
visit(T)這個操作就是對當前數據進行的處理, preorder_recursive(T->;lchild)就是把當前 數據變換為它的左子樹,訪問右子樹的操作可以同樣理解了. 現在回到我們提出的第二個問題:如何確定轉移到哪裡繼續執行?關鍵在於一下三個地方:a) 確定對當前數據的訪問順序,簡單一點說就是確定這個遞歸程序可以轉換為哪種方式遍歷的樹結 構;b)確定這個遞歸函數轉換為遞歸調用樹時的分支是如何劃分的,即確定什麼是這個遞歸調用 樹的"左子樹"和"右子樹"c)確定這個遞歸調用樹何時返回,即確定什麼結點是這個遞歸調用樹的 "葉子結點". 三.三個例子 好了上面的理論知識已經足夠了,下面讓我們看看幾個例子,結合例子加深我們對問題的認識 .即使上面的理論你沒有完全明白,不要氣餒,對事物的認識總是曲折的,多看多想你一定可以明 白(事實上我也是花了兩個星期的時間才弄得比較明白得). 1)例子一:
f(n) = n + 1; (n <2)
f[n/2] + f[n/4](n >;= 2);

這個例子相對簡單一些,遞歸程序如下:
int f_recursive(int n)
{
int u1, u2, f;
if (n < 2)
f = n + 1;
else {
u1 = f_recursive((int)(n/2));
u2 = f_recursive((int)(n/4));
f = u1 * u2;
}
return f;
}
復制代碼
下面按照我們上面說的,確定好遞歸調用樹的結構,這一步是最重要的.首先,什麼是葉子結點 ,我們看到當n < 2時f = n + 1,這就是返回的語句,有人問為什麼不是f = u1 * u2,這也是一個 返回的語句呀?答案是:這條語句是在u1 = exmp1((int)(n/2))和u2 = exmp1((int)(n/4))之後 執行的,是這兩條語句的父結點. 其次,什麼是當前結點,由上面的分析,f = u1 * u2即是父結點 .然後,順理成章的u1 = exmp1((int)(n/2))和u2 = exmp1((int)(n/4))就分別是左子樹和右子 樹了.最後,我們可以看到,這個遞歸函數可以表示成後序遍歷的二叉調用樹.好了,樹的情況分析 到這里,下面來分析一下棧的情況,看看我們要把什麼數據保存在棧中,在上面給出的後序遍歷的如果這個過程你沒 非遞歸程序中我們已經看到了要加入一個標志域,因此在棧中要保存這個標志域;另外,u1,u2和 每次調用遞歸函數時的n/2和n/4參數都要保存,這樣就要分別有三個棧分別保存:標志域,返回量 和參數,不過我們可以做一個優化,因為在向上一層返回的時候,參數已經沒有用了,而返回量也 只有在向上返回時才用到,因此可以把這兩個棧合為一個棧.如果對於上面的分析你沒有明白,建 議你根據這個遞歸函數寫出它的遞歸棧的變化情況以加深理解,再次重申一點:前期對樹結構和 棧的分析是最重要的,如果你的程序出錯,那麼請返回到這一步來再次分析,最好把遞歸調用樹和 棧的變化情況都畫出來,並且結合一些簡單的參數來人工分析你的演算法到底出錯在哪裡. ok,下面給出我花了兩天功夫想出來的非遞歸程序(再次提醒你不要氣餒,大家都是這么過來 的).
int f_nonrecursive(int n)
{
int stack[20], flag[20], cp;

/* 初始化棧和棧頂指針 */
cp = 0;
stack[0] = n;
flag[0] = 0;
while (cp >;= 0) {
switch(flag[cp]) {
case 0: /* 訪問的是根結點 */
if (stack[cp] >;= 2) { /* 左子樹入棧 */
flag[cp] = 1; /* 修改標志域 */
cp++;
stack[cp] = (int)(stack[cp - 1] / 2);
flag[cp] = 0;
} else { /* 否則為葉子結點 */
stack[cp] += 1;
flag[cp] = 2;
}
break;
case 1: /* 訪問的是左子樹 */
if (stack[cp] >;= 2) { /* 右子樹入棧 */
flag[cp] = 2; /* 修改標志域 */
cp += 2;
stack[cp] = (int)(stack[cp - 2] / 4);
flag[cp] = 1;
} else { /* 否則為葉子結點 */
stack[cp] += 1;
flag[cp] = 2;
}
break;
case 2: /* */
if (flag[cp - 1] == 2) { /* 當前是右子樹嗎? */
/*
* 如果是右子樹, 那麼對某一棵子樹的後序遍歷已經
* 結束,接下來就是對這棵子樹的根結點的訪問
*/
stack[cp - 2] = stack[cp] * stack[cp - 1];
flag[cp - 2] = 2;
cp = cp - 2;
} else
/* 否則退回到後序遍歷的上一個結點 */
cp--;
break;
}
}
return stack[0];
}
復制代碼
演算法分析:a)flag只有三個可能值:0表示第一次訪問該結點,1表示訪問的是左子樹,2表示 已經結束了對某一棵子樹的訪問,可能當前結點是這棵子樹的右子樹,也可能是葉子結點.b)每 遍歷到某個結點的時候,如果這個結點滿足葉子結點的條件,那麼把它的flag域設為2;否則根據 訪問的是根結點,左子樹或是右子樹來設置flag域,以便決定下一次訪問該節點時的程序轉向. 2)例子二 快速排序演算法 遞歸演算法如下:
void swap(int array[], int low, int high)
{
int temp;
temp = array[low];
array[low] = array[high];
array[high] = temp;
}
int partition(int array[], int low, int high)
{
int p;
p = array[low];
while (low < high) {
while (low < high && array[high] >;= p)
high--;
swap(array,low,high);
while (low < high && array[low] <= p)
low++;
swap(array,low,high);
}
return low;
}
void qsort_recursive(int array[], int low, int high)
{
int p;
if(low < high) {
p = partition(array, low, high);
qsort_recursive(array, low, p - 1);
qsort_recursive(array, p + 1, high);
}
}
復制代碼
需要說明一下快速排序的演算法: partition函數根據數組中的某一個數把數組劃分為兩個部分, 左邊的部分均不大於這個數,右邊的數均不小於這個數,然後再對左右兩邊的數組再進行劃分.這 里我們專注於遞歸與非遞歸的轉換,partition函數在非遞歸函數中同樣的可以調用(其實 partition函數就是對當前結點的訪問). 再次進行遞歸調用樹和棧的分析: 遞歸調用樹:a)對當前結點的訪問是調用partition函數;b)左子樹: qsort_recursive(array, low, p - 1);c)右子樹:qsort_recursive(array, p + 1, high); d)葉子結點:當low < high時;e)可以看出這是一個先序調用的二叉樹 棧:要保存的數據是兩個表示範圍的坐標.
void qsort_nonrecursive(int array[], int low, int high)
{
int m[50], n[50], cp, p;
/* 初始化棧和棧頂指針 */
cp = 0;
m[0] = low;
n[0] = high;
while (m[cp] < n[cp]) {
while (m[cp] < n[cp]) { /* 向左走到盡頭 */
p = partition(array, m[cp], n[cp]); /* 對當前結點的訪問 */
cp++;
m[cp] = m[cp - 1];
n[cp] = p - 1;
}
/* 向右走一步 */
m[cp + 1] = n[cp] + 2;
n[cp + 1] = n[cp - 1];
cp++;
}
}
復制代碼
3)例子三 阿克曼函數:
akm(m, n) = n + 1; (m = 0時)
akm(m - 1, 1); (n = 0時)
akm(m - 1, akm(m, n - 1)); (m != 0且n != 0時)
復制代碼
遞歸演算法如下:
int akm_recursive(int m, int n)
{
int temp;
if (m == 0)
return (n + 1);
else if (n == 0)
return akm_recursive(m - 1, 1);
else {
temp = akm_recursive(m, n - 1);
return akm_recursive(m - 1, temp);
}
}

8. 遞歸主方法

遞歸的主要方法是什麼？

一、遞歸演算法
遞歸演算法（英語：recursion algorithm）在計算機科學中是指一種通過重復將問題分解為同類的子問題而解決問題的方法。遞歸式方法可以被用於解決很多的計算機科學問題，因此它是計算機科學中十分重要的一個概念。絕大多數編程語言支持函數的自調用，在這些語言中函數可以通過調用自身來進行遞歸。計算理論可以證明遞歸的作用可以完全取代循環，因此在很多函數編程語言（如Scheme）中習慣用遞歸來實現循環。
二、遞歸程序
在支持自調的編程語言中，遞歸可以通過簡單的函數調用來完成，如計算階乘的程序在數學上可以定義為：

這一程序在Scheme語言中可以寫作：
1
(define (factorial n) (if (= n 0) 1 (* n (factorial (- n 1)))))
不動點組合子
即使一個編程語言不支持自調用，如果在這語言中函數是第一類對象（即可以在運行期創建並作為變數處理），遞歸可以通過不動點組合子（英語：Fixed-point combinator）來產生。以下Scheme程序沒有用到自調用，但是利用了一個叫做Z 運算元（英語：Z combinator）的不動點組合子，因此同樣能達到遞歸的目的。
1
(define Z (lambda (f) ((lambda (recur) (f (lambda arg (apply (recur recur) arg)))) (lambda (recur) (f (lambda arg (apply (recur recur) arg)))))))(define fact (Z (lambda (f) (lambda (n) (if (<= n 0) 1 (* n (f (- n 1))))))))
這一程序思路是，既然在這里函數不能調用其自身，我們可以用 Z 組合子應用(application)這個函數後得到的函數再應用需計算的參數。
尾部遞歸
尾部遞歸是指遞歸函數在調用自身後直接傳回其值，而不對其再加運算。尾部遞歸與循環是等價的，而且在一些語言（如Scheme中）可以被優化為循環指令。 因此，在這些語言中尾部遞歸不會佔用調用堆棧空間。以下Scheme程序同樣計算一個數字的階乘，但是使用尾部遞歸：
1
(define (factorial n) (define (iter proct counter) (if (> counter n) proct (iter (* counter proct) (+ counter 1)))) (iter 1 1))
三、能夠解決的問題
數據的定義是按遞歸定義的。如Fibonacci函數。
問題解法按遞歸演算法實現。如Hanoi問題。
數據的結構形式是按遞歸定義的。如二叉樹、廣義表等。
四、遞歸數據
數據類型可以通過遞歸來進行定義，比如一個簡單的遞歸定義為自然數的定義：「一個自然數或等於0，或等於另一個自然數加上1」。Haskell中可以定義鏈表為：
1
data ListOfStrings = EmptyList | Cons String ListOfStrings
這一定義相當於宣告「一個鏈表或是空串列，或是一個鏈表之前加上一個字元串」。可以看出所有鏈表都可以通過這一遞歸定義來達到。