Python - 遞迴

上一頁
下一頁

遞迴是程式設計中一個基本的概念，它指的是一個函式在函式體內呼叫自身。這種技術可以將一個複雜的問題分解成多個相同型別但規模更小的子問題。在 Python 中，遞迴是透過定義一個函式並在其函式體內呼叫自身來實現的。

遞迴的組成部分

正如我們之前討論的，遞迴是一種函式呼叫自身的技巧。為了理解遞迴，我們需要了解其關鍵組成部分。以下是遞迴的主要組成部分：

  • 基本情況
  • 遞迴情況

基本情況

基本情況是遞迴中的一個基本概念，它充當遞迴函式停止呼叫自身的條件。它是防止無限遞迴和隨之而來的堆疊溢位錯誤的關鍵。

基本情況為問題的最簡單例項提供了直接的解決方案，確保每次遞迴呼叫都更接近此終止條件。

遞迴最常見的例子是計算階乘。從數學上講，階乘定義為：

n! = n × (n-1)!

可以看出，我們使用階乘本身來定義階乘。因此，這是一個適合編寫遞迴函式的情況。讓我們展開以上定義，計算 5 的階乘值。

5! = 5 × 4!
   5 × 4 × 3!
   5 × 4 × 3 × 2!
   5 × 4 × 3 × 2 × 1!
   5 × 4 × 3 × 2 × 1
= 120

雖然我們可以使用迴圈執行此計算，但其遞迴函式涉及透過遞減數字連續呼叫自身，直到達到 1。

示例

以下示例演示瞭如何使用遞迴函式計算階乘：

def factorial(n):

   if n == 1:
      print (n)
      return 1 #base case
   else:
      print (n,'*', end=' ')
      return n * factorial(n-1) #Recursive case
      
print ('factorial of 5=', factorial(5))

上述程式生成以下輸出：

5 * 4 * 3 * 2 * 1
factorial of 5= 120

遞迴情況

遞迴情況是遞迴函式的一部分，其中函式呼叫自身以解決同一問題的規模更小或更簡單的例項。此機制允許將複雜問題分解成更易於管理的子問題，其中每個子問題都是原始問題的較小版本。

遞迴情況對於朝著基本情況發展至關重要，確保遞迴最終會終止。

示例

以下是遞迴情況的示例。在此示例中，我們生成斐波那契數列，其中遞迴情況對前兩個斐波那契數的結果求和：

def fibonacci(n):
    if n <= 0:
        return 0  # Base case for n = 0
    elif n == 1:
        return 1  # Base case for n = 1
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)  # Recursive case
        
fib_series = [fibonacci(i) for i in range(6)]
print(fib_series)

上述程式生成以下輸出：

[0, 1, 1, 2, 3, 5]

使用遞迴進行二分查詢

二分查詢是一種強大的演算法，可以快速在排序列表中查詢元素，具有對數時間複雜度，使其效率極高。

讓我們再看一個例子來了解遞迴是如何工作的。手頭的問題是檢查給定數字是否存在於列表中。

雖然我們可以使用 for 迴圈並比較每個數字來對列表中的某個數字進行順序搜尋，但順序搜尋效率不高，尤其是在列表過大的情況下。二分查詢演算法檢查索引“high”是否大於索引“low”。根據“mid”變數中存在的值，該函式再次被呼叫以搜尋元素。

我們有一個按升序排列的數字列表。然後我們找到列表的中點，並根據所需數字是否小於或大於中點處的數字，將檢查限制到中點的左側或右側。

下圖顯示了二分查詢的工作原理：

Python Recursion

示例

以下程式碼實現了遞迴二分查詢技術：

def bsearch(my_list, low, high, elem):
   if high >= low:
      mid = (high + low) // 2
      if my_list[mid] == elem:
         return mid
      elif my_list[mid] > elem:
         return bsearch(my_list, low, mid - 1, elem)
      else:
         return bsearch(my_list, mid + 1, high, elem)
   else:
      return -1

my_list = [5,12,23, 45, 49, 67, 71, 77, 82]
num = 67
print("The list is")
print(my_list)
print ("Check for number:", num)
my_result = bsearch(my_list,0,len(my_list)-1,num)

if my_result != -1:
   print("Element found at index ", str(my_result))
else:
   print("Element not found!")

輸出

The list is
[5, 12, 23, 45, 49, 67, 71, 77, 82]
Check for number: 67
Element found at index 5
列印頁面

上一頁
下一頁
廣告