瞭解階乘遞歸

我正在查看遞歸的階乘示例，並且只想確保我正確理解它！瞭解階乘遞歸

def factorial(n): 
    if(n == 0): 
     return 1 
    else: 
     return n * factorial(n-1)

，我會是正確地說：

階乘（4）=階乘（4-1）* 4 =階乘（3-1）* 3 * 4 =階乘（2-1）* 2 * 3 * 4 =階乘（1-1）* 1 * 2 * 3 * 4 = 24

因爲階乘（1-1）=階乘（0），作爲基礎情況顯示= 1，由2，然後3然後4.

是正確的方式來看待它？

在此先感謝！

來源

2014-04-23 heather

這的確是正確的想法。 – chrk

查看遞歸的正確方法，但您認爲乘法是可交換的。它應該是'4 * 3 * 2 * 1 *階乘（1-1）'或甚至是4 *（3 *（2 *（1 *階乘（1-1））））' –

是的。但是因爲它是遞歸的，所以它的工作方式相反。我曾經有一個面試官解釋給我這個樣子：

說，對於事實（5）：

- fact(5) = 5 * fact(4) 
      - fact(4) = 4 * fact(3) 
        - fact(3) = 3 * fact(2) 
           - fact(2) = 2 * fact(1) 
             - fact(1) = 1 * fact(0) 
                - fact(0) = 1 
                // This is where your condition returns 1.

現在，想象一下，上面的-號代表了一回。你基本上會返回-之後的任何符號。所以從最低行開始，返回1。然後，你有1實際上返回（1）即1 * 1，因此，它發生在像REVERSE級聯：

= 120 
- fact(5) = 5 * 24 
      - fact(4) = 4 * 6 = 24 
        - fact(3) = 3 * 2 = 6 
           - fact(2) = 2 * 1 = 2 
             - fact(1) = 1 * 1 = 1 
                - fact(0) = 1

請記住，只要在遞歸工作，一切實際工作中的相反。這應該真的幫助你打破任何遞歸問題。

這實際上是爲什麼尾遞歸和相關優化如此重要。在內存中，每個這些調用都會被延遲，直到它上面的調用（圖中下方）完成並返回時才能返回。因此，一個非常深的遞歸調用可能導致堆棧溢出，除非編譯器/解釋器通過將其轉換爲OP中的版本來優化這種情況，以便部分結果立即進行評估，而不是延遲。 Python不會執行此優化，因此您必須小心遞歸調用。

來源

2014-04-23 19:05:03

是的，你描述的方式是怎麼回事。

需要注意的一點是，如果您輸入n的非整數值或值小於0的值爲n，則看起來您會陷入無限循環。

這可能是值得添加代碼中的支票本：

if not isinstance(n, int): 
     return None 

elif n < 0: 
     return None

來源

2014-04-23 18:49:51 Pash101

瞭解階乘遞歸

回答

相關問題