python遞歸演算法教程

① python 遞歸演算法算最大公約數

設計的邏輯就有問題,find就該做find的事,不要在find里有輸出

#yourcodegoeshere
defGCD():
b=input("pleaseenterthefirstnumber")
c=input("pleaseenterthesecondnumber")
printfind(b,c)
deffind(b,c):
ifb>c:
d=b%c
b=c
ifd==0:
returnb
c=d
find(b,c)
else:
e=c%b
c=b
ife==0:
returnc
b=e
find(b,c)
#printfind(b,c)

defsimp_find(b,c):
ifb%c!=0:
returnsimp_find(c,b%c)
returnc

GCD()

② 如何用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)。

③ Python遞歸

用遞歸

④ Python基於遞歸演算法實現的走迷宮問題

Python基於遞歸演算法實現的走迷宮問題
本文實例講述了Python基於遞歸演算法實現的走迷宮問題。分享給大家供大家參考，具體如下：
什麼是遞歸?
簡單地理解就是函數調用自身的過程就稱之為遞歸。
什麼時候用到遞歸？
如果一個問題可以表示為更小規模的迭代運算，就可以使用遞歸演算法。
迷宮問題：一個由0或1構成的二維數組中，假設1是可以移動到的點，0是不能移動到的點，如何從數組中間一個值為1的點出發，每一隻能朝上下左右四個方向移動一個單位，當移動到二維數組的邊緣，即可得到問題的解，類似的問題都可以稱為迷宮問題。
在python中可以使用list嵌套表示二維數組。假設一個6*6的迷宮,問題時從該數組坐標[3][3]出發，判斷能不能成功的走出迷宮。
maze=[[1,0,0,1,0,1],
[1,1,1,0,1,0],
[0,0,1,0,1,0],
[0,1,1,1,0,0],
[0,0,0,1,0,0],
[1,0,0,0,0,0]]
針對這個迷宮問題，我們可以使用遞歸的思想很好的解決。對於數組中的一個點，該點的四個方向可以通過橫縱坐標的加減輕松的表示，每當移動的一個可移動的點時候，整個問題又變為和初始狀態一樣的問題，繼續搜索四個方向找可以移動的點，知道移動到數組的邊緣。
所以我們可以這樣編碼：
# 判斷坐標的有效性，如果超出數組邊界或是不滿足值為1的條件，說明該點無效返回False，否則返回True。
def valid(maze,x,y):
if (x>=0 and x<len(maze) and y>=0 and y<len(maze[0]) and maze[x][y]==1):
return True
else:
return False
# 移步函數實現
def walk(maze,x,y):
# 如果位置是迷宮的出口，說明成功走出迷宮
if(x==0 and y==0):
print("successful!")
return True
# 遞歸主體實現
if valid(maze,x,y):
# print(x,y)
maze[x][y]=2 # 做標記，防止折回
# 針對四個方向依次試探，如果失敗，撤銷一步
if not walk(maze,x-1,y):
maze[x][y]=1
elif not walk(maze,x,y-1):
maze[x][y]=1
elif not walk(maze,x+1,y):
maze[x][y]=1
elif not walk(maze,x,y+1):
maze[x][y]=1
else:
return False # 無路可走說明，沒有解
return True
walk(maze,3,3)
遞歸是個好東西呀！

⑤ python里如何用遞歸法列出一個tree里所有的枝幹

您好：perm函數輸出的是參數list從參數k位置開始，到參數m位置結束的全排列
def perm(list,k,m):
if k==m:
for i in range(m+1): # 遞歸的結束條件是k==m，在整個遞歸過程中參數m（即結束位置沒有改變），而參數k則每次遞歸+1
print list[i], # 輸出遞歸結束時的list狀態
print
else:
for i in range(k,m+1): # 該循環用來負責生成遞歸的下一個狀態
list[k],list[i]=list[i],list[k] # 將list的k位置與每一個位置i分別交換
perm(list,k+1,m) # 由於k位置與每一個位置i交換，也即k位置所有可能選值都已被窮舉，此時只需要繼續計算k+1之後的職位即可，因此以k+1為開始位置，結束位置m不變進入下一層遞歸
list[k],list[i]=list[i],list[k] # 由於list是引用傳遞，因此需要在位置交換之後重新交換，以保證list不變。

⑥ python請用遞歸演算法編程解決漢諾塔問題 在線等

這是Python3系統自帶的一個例子，估計就是這個意思，本來他是6個盤子，按照你要求改成4個了。遞歸演算法沒問題，描述也非常詳細 ；）

#!/usr/bin/envpython3
fromturtleimport*
classDisc(Turtle):
def__init__(self,n):
Turtle.__init__(self,shape="square",visible=False)
self.pu()
self.shapesize(1.5,n*1.5,2)#square-->rectangle
self.fillcolor(n/6.,0,1-n/6.)
self.st()
classTower(list):
"Hanoitower,asubclassofbuilt-intypelist"
def__init__(self,x):
"createanemptytower.xisx-positionofpeg"
self.x=x
defpush(self,d):
d.setx(self.x)
d.sety(-150+34*len(self))
self.append(d)
defpop(self):
d=list.pop(self)
d.sety(150)
returnd
defhanoi(n,from_,with_,to_):
ifn>0:
hanoi(n-1,from_,to_,with_)
to_.push(from_.pop())
hanoi(n-1,with_,from_,to_)
defplay():
onkey(None,"space")
clear()
try:
hanoi(6,t1,t2,t3)
write("pressSTOPbuttontoexit",
align="center",font=("Courier",16,"bold"))
exceptTerminator:
pass#turtledemouserpressedSTOP
defmain():
globalt1,t2,t3
ht();penup();goto(0,-225)#writerturtle
t1=Tower(-250)
t2=Tower(0)
t3=Tower(250)
#maketowerof6discs
foriinrange(4,0,-1):
t1.push(Disc(i))
#preparespartanicuserinterface;-)
write("pressspacebartostartgame",
align="center",font=("Courier",16,"bold"))
onkey(play,"space")
listen()
return"EVENTLOOP"
if__name__=="__main__":
msg=main()
print(msg)
mainloop()

⑦ python，怎麼使用遞歸的方法，提取括弧中的字串符

當遞歸調用是整個函數體中最後執行的語句且它的返回值不屬於表達式的一部分時，這個遞歸調用就是尾遞歸。
尾遞歸函數的特點是在回歸過程中不用做任何操作，這個特性很重要，因為大多數現代的編譯器會利用這種特點自動生成優化的代碼。

⑧ python如何用遞歸函數求1+2+3+4+5的值

python用遞歸函數求1+2+3+4+5的值的方法：
1、寫出臨界條件
2、找這一次和上一次的關系
3、假設當前函數已經能用，調用自身計算上一次的結果，再求出本次的結果
代碼實現如下：

⑨ Python3：怎麼通過遞歸函數

函數的遞歸調用
遞歸問題是一個說簡單也簡單，說難也有點難理解的問題.我想非常有必要對其做一個總結.
首先理解一下遞歸的定義，遞歸就是直接或間接的調用自身.而至於什麼時候要用到遞歸，遞歸和非遞歸又有那些區別？又是一個不太容易掌握的問題，更難的是對於遞歸調用的理解.下面我們就從程序+圖形的角度對遞歸做一個全面的闡述.
我們從常見到的遞歸問題開始:
1 階層函數
#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;
}
這是一個遞歸求階層函數的實現。很多朋友只是知道該這么實現的，也清楚它是通過不斷的遞歸調用求出的結果.但他們有些不清楚中間發生了些什麼.下面我們用圖對此做一個清楚的流程:
根據上面這個圖，大家可以很清楚的看出來這個函數的執行流程。我們的階層函數factorial被調用了4次.並且我們可以看出在調用後面的調用中，前面的調用並不退出。他們同時存在內存中。可見這是一件很浪費資源的事情。我們該次的參數是3.如果我們傳遞10000呢。那結果就可想而知了.肯定是溢出了.就用int型來接收結果別說10000，100就會產生溢出.即使不溢出我想那肯定也是見很浪費資源的事情.我們可以做一個粗略的估計:每次函數調用就單變數所需的內存為:兩個int型變數.n和result.在32位機器上佔8B.那麼10000就需要10001次函數調用.共需10001*8/1024 = 78KB.這只是變數所需的內存空間.其它的函數調用時函數入口地址等仍也需要佔用內存空間。可見遞歸調用產生了一個不小的開銷.
2 斐波那契數列
int Fib(int n)
{
if (n <= 1)
{
return n;
}
else
{
return Fib(n-1) + Fib(n-2);
}
}
這個函數遞歸與上面的那個有些不同.每次調用函數都會引起另外兩次的調用.最後將結果逐級返回.
我們可以看出這個遞歸函數同樣在調用後買的函數時，前面的不退出而是在等待後面的結果，最後求出總結果。這就是遞歸.
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;
}
運行結果:
0
1
2
3
4
4
3
2
1
0
該程序中有兩個遞歸函數。傳遞同樣的參數，但他們的輸出結果剛好相反。理解這兩個函數的調用過程可以很好的幫助我們理解遞歸:
我想能夠把上面三個函數的遞歸調用過程理解了，你已經把遞歸調用理解的差不多了.並且從上面的遞歸調用中我們可以總結出遞歸的一個規律：他是逐級的調用，而在函數結束的時候是從最後面往前反序的結束.這種方式是很佔用資源，也很費時的。但是有的時候使用遞歸寫出來的程序很容易理解，很易讀.
為什麼使用遞歸:
1 有時候使用遞歸寫出來的程序很容易理解，很易讀.
2 有些問題只有遞歸能夠解決.非遞歸的方法無法實現.如:漢諾塔.
遞歸的條件:
並不是說所有的問題都可以使用遞歸解決，他必須的滿足一定的條件。即有一個出口點.也就是說當滿足一定條件時，程序可以結束，從而完成遞歸調用，否則就陷入了無限的遞歸調用之中了.並且這個條件還要是可達到的.
遞歸有哪些優點:
易讀，容易理解，代碼一般比較短.
遞歸有哪些缺點:
佔用內存資源多，費時，效率低下.
因此在我們寫程序的時候不要輕易的使用遞歸，雖然他有他的優點，但是我們要在易讀性和空間，效率上多做權衡.一般情況下我們還是使用非遞歸的方法解決問題.若一個演算法非遞歸解法非常難於理解。我們使用遞歸也未嘗不可.如:二叉樹的遍歷演算法.非遞歸的演算法很難與理解.而相比遞歸演算法就容易理解很多.
對於遞歸調用的問題，我們在前一段時間寫圖形學程序時，其中有一個四連同填充演算法就是使用遞歸的方法。結果當要填充的圖形稍微大一些時，程序就自動關閉了.這不是一個人的問題，所有人寫出來的都是這個問題.當時我們給與的解釋就是堆棧溢出。就多次遞歸調用佔用太多的內存資源致使堆棧溢出，程序沒有內存資源執行下去，從而被操作系統強制關閉了.這是一個真真切切的例子。所以我們在使用遞歸的時候需要權衡再三.

⑩ python用遞歸的方法求1+2+3+...+n

#m=n = 10
m=n=int(input("Please enter n :"))

def recursion(n,v):
v = v+n
n = n-1;
if n==0:
#''' 當n=0時，停止
print("1+2+3+...+%d = "%m,v)
return v
v = recursion(n,v) # 遞歸調用，函數內自己調用自己

recursion(n,v=0)# 函數調用