遞歸的思想主要是能夠重復某些動作，比如簡單的階乘，次方，回溯中的八皇后，數(shù)獨，還有漢諾塔，分形。
創(chuàng)新互聯(lián)專注于海林企業(yè)網(wǎng)站建設,成都響應式網(wǎng)站建設公司,商城網(wǎng)站定制開發(fā)。海林網(wǎng)站建設公司,為海林等地區(qū)提供建站服務。全流程按需設計網(wǎng)站，專業(yè)設計，全程項目跟蹤，創(chuàng)新互聯(lián)專業(yè)和態(tài)度為您提供的服務
由于堆棧的機制，一般的遞歸可以保留某些變量在歷史狀態(tài)中，比如你提到的return
x
*
power...,
但是某些或許龐大的問題或者是深度過大的問題就需要盡量避免遞歸，因為可能會棧溢出。還有一個問題是～python不支持尾遞歸優(yōu)化?。。。∷浴€是盡量避免遞歸的出現(xiàn)。
def
power(x,
n)
if
n
0:
return
1
return
x
*
power(x,
n
-
1)
power(3,
3)
3
*
power(3,
2)
3
*
(3
*
power(3,
1))
3
*
(3
*
(3
*
power(3,
0)))
3
*
(3
*
(3
*
1))
這里n
=
0,
return
1
3
*
(3
*
3)
3
*
9
27
當函數(shù)形參n=0的時候，開始回退～直到第一次調(diào)用power結(jié)束。
python不能無限的遞歸調(diào)用下去。并且當輸入的值太大，遞歸次數(shù)太多時，python 都會報錯
首先說結(jié)論，python解釋器這么會限制遞歸次數(shù)，這么做為了避免"無限"調(diào)用導致的堆棧溢出。
tail recursion 就是指在程序最后一步執(zhí)行遞歸。這種函數(shù)稱為 tail recursion function。舉個例子：
這個函數(shù)就是普通的遞歸函數(shù)，它在遞歸之后又進行了 乘 的操作。 這種普通遞歸，每一次遞歸調(diào)用都會重新推入一個調(diào)用堆棧。
把上述調(diào)用改成 tail recursion function
tail recursion 的好處是每一次都計算完，將結(jié)果傳遞給下一次調(diào)用，然后本次調(diào)用任務就結(jié)束了，不會參與到下一次的遞歸調(diào)用。這種情況下，只重復用到了一個堆棧。因此可以優(yōu)化結(jié)構(gòu)。就算是多次循環(huán)，也不會出現(xiàn)棧溢出的情況。這就是 tail recursion optimization 。
c和c++都有這種優(yōu)化， python沒有，所以限制了調(diào)用次數(shù)，就是為了防止無限遞歸造成的棧溢出。
如果遞歸次數(shù)過多，導致了開頭的報錯，可以使用 sys 包手動設置recursion的limit
手動放大 recursionlimit 限制：
可以看出來的是，該題可以用斐波那契數(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)
這是遞歸寫法，但是會導致棧溢出。在計算機中，函數(shù)的調(diào)用是通過棧進行實現(xiàn)的，如果遞歸調(diào)用的次數(shù)過多，就會導致棧溢出。
針對這種情況就要使用方法二，改成非遞歸函數(shù)。
將遞歸進行改寫，實現(xiàn)循環(huán)就不會導致棧溢出
??遞歸算法常用來解決結(jié)構(gòu)相似的問題。
??所謂結(jié)構(gòu)相似，是指構(gòu)成原問題的子問題與原問題在結(jié)構(gòu)上相似，可以用類似的方法解決。具體地，整個問題的解決，可以分為兩部分：第一部分是一些特殊情況，有直接的解法；第二部分與原問題相似，但比原問題的規(guī)模小，并且依賴第一部分的結(jié)果。
??本質(zhì)上，遞歸是把一個不能或不好解決的大問題轉(zhuǎn)化成一個或幾個小問題，再把這些小問題進一步分解成更小的問題，直至每個小問題都可以直接解決。
??實際上，遞歸會將前面所有調(diào)用的函數(shù)暫時掛起，直到遞歸終止條件給出明確的結(jié)果后，才會將所有掛起的內(nèi)容進行反向計算。其實，遞歸也可以看作是一種反向計算的過程，前面調(diào)用遞歸的過程只是將表達式羅列出來，待終止條件出現(xiàn)后，才依次從后向前倒序計算前面掛起的內(nèi)容，最后將所有的結(jié)果一起返回。
重慶分公司
重慶分公司
