Python中如何實現遞歸函數

這篇文章主要介紹Python中如何實現遞歸函數，文中介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們一定要看完！

1、什么是遞歸函數

之前介紹了如何創建和調用函數。你知道，函數可調用其他函數，但可能讓你感到驚訝的是，函數還可調用自己。如果你以前沒有遇到這種情況，可能想知道遞歸是什么意思。簡單地說，遞歸意味著引用（這里是調用）自身。

2、python遞歸函數

下面是一個遞歸式函數定義：

def recursion():

    return recursion()

這個定義顯然什么都沒有做，與剛才的“遞歸”定義一樣傻。如果你運行它，結果將如何呢？你將發現運行一段時間后，這個程序崩潰了（引發異常）。從理論上說，這個程序將不斷運行下去，但每次調用函數時，都將消耗一些內存。因此函數調用次數達到一定的程度（且之前的函數調用未返回）后，將耗盡所有的內存空間，導致程序終止并顯示錯誤消息“超過大遞歸深度”

你想要的是能對你有所幫助的遞歸函 數，這樣的遞歸函數通常包含下面兩部分。

• 基線條件（針對小的問題）：滿足這種條件時函數將直接返回一個值。 

• 遞歸條件：包含一個或多個調用，這些調用旨在解決問題的一部分。

這里的關鍵是，通過將問題分解為較小的部分，可避免遞歸沒完沒了，因為問題終將被分解成基線條件可以解決的小問題。

3、python遞歸函數

那么如何讓函數調用自身呢？這沒有看起來那么難懂。前面說過，每次調用函數時，都將為此創建一個新的命名空間。這意味著函數調用自身時，是兩個不同的函數［更準確地說，是不同版本（即命名空間不同）的同一個函數］在交流。

經典案例1，計算數字n的階乘。n的階乘為n × (n-1)× (n-2) ×… × 1，在數學領域的用途非常廣泛。

可使用循環。這種實現可行，而且直截了當。

deffactorial(n):

    result = n

for i in range(1, n):

     result *= i

return result

下面來考慮如何使用函數來實現這個定義。理解這個定義后，實現起來其實非常簡單。 def factorial(n):

if n == 1:

    return 1

else:

    return n * factorial(n -1)

這是前述定義的直接實現，只是別忘了函數調用factorial(n)和factorial(n–1)是不同的 實體。

經典案例2、計算一個數冪，就像內置函數pow和運算符**所做的那樣。要定義一個數字的整數次冪，有多種方式，但先來看一個簡單的定義：power(x, n)（x的n次冪）是將數字x自乘n - 1次的結果，即將n個x相乘的結果。換而言之，power(2, 3)是2自乘兩次的結果，即2 × 2 × 2 = 8。

這實現起來很容易。

def power(x, n):

    result = 1

  for i in range(n):

     result *= x

return result 這是一個非常簡單的小型函數，但也可將定義修改成遞歸式的。

對于任何數字x，power(x, 0)都為1。n>0時，power(x, n)為power(x,n-1)與x的乘積。這種定義提供的結果與更簡單的迭代定義完全相同。理解定義是難的，而實現起來很容易。

 def power(x, n):

    if n == 0:

        return1

    else: 

       return x* power(x, n - 1)

4、為什么要使用遞歸函數

    大多數情況下，使用循環的效率可能更高。然而，在很多情況下，使用遞歸的可讀性更高，且有時要高得多，在你理解了函數的遞歸式定義時尤其如此。另外，雖然你完全能夠避免編寫遞歸函數，但作為程序員，你必須能夠讀懂其他人編寫的遞歸算法和函數。

以上是“Python中如何實現遞歸函數”這篇文章的所有內容，感謝各位的閱讀！希望分享的內容對大家有幫助，更多相關知識，歡迎關注億速云行業資訊頻道！