如何在 Python 中建立遞迴函式？

---

遞迴是一種程式設計技巧，其中函式在其主體中呼叫自身一次或多次。通常，它會返回此函式呼叫的返回值。如果函式定義遵循遞迴，我們稱此函式為遞迴函式。

一個遞迴函式必須在程式中使用之前終止。如果每次遞迴呼叫，問題的解決都變得更小並朝著基本情況發展，則它會終止，在基本情況中，可以無需進一步遞迴即可解決問題。如果在呼叫中不滿足基本情況，遞迴會導致無限迴圈。

我們使用 Python 中的遞迴函式來解決現實世界的數學問題。

前 n 個自然數之和

以下程式碼使用遞迴 Python 函式返回前 n 個自然數之和。

示例

這將列印前 100 個自然數和前 500 個自然數的和

def sum_n(n):
   if n== 0:
       return 0 
   else:
      return n + sum_n(n-1)
print(sum_n(100)) 
print(sum_n(500))

輸出

5050
125250

使用遞迴的階乘函式

遞迴函式是指重複呼叫自身直到達到停止遞迴的基本情況的函式。讓我們考慮一個 Python 中簡單遞迴函式的示例，該函式計算給定數字的階乘

在這裡，階乘函式採用正整數 n 作為引數，並返回該數字的階乘。如果 n 等於 0，則函式返回 1，這是基本情況。否則，函式會遞迴呼叫自身，引數為 n-1，並將結果乘以 n。遞迴將持續進行，直到達到基本情況。

示例

這將呼叫階乘函式，引數為 5，它將返回 5 * 4 * 3 * 2 * 1 = 120。

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

輸出

120

使用遞迴的斐波那契數列

在此示例中，斐波那契函式採用非負整數 n 作為引數，並返回斐波那契數列中的第 n 個數。如果 n 等於 0，則函式返回 0。如果 n 等於 1，則函式返回 1。否則，函式會遞迴呼叫自身，引數為 n-1 和 n-2，並返回結果之和。遞迴將持續進行，直到達到基本情況。

示例

這將呼叫斐波那契函式，引數為 6，它將返回斐波那契數列中的第 6 個數，即 8。

def fibonacci(n):
   if n == 0:
      return 0 
   elif n == 1:
      return 1
   else:
      return fibonacci(n-1) + fibonacci(n-2)
print(fibonacci(6))

輸出

8

如何查詢數字的最大公約數

Python 中另一個查詢兩個正整數的最大公約數 (GCD) 的遞迴函式示例如下

在此示例中，gcd 函式採用兩個正整數 a 和 b 作為引數，並返回它們的最大公約數。如果 b 等於 0，則函式返回 a，這是基本情況。否則，函式會遞迴呼叫自身，引數為 b 和 a % b，其中 % 是模運算子，並返回結果。遞迴將持續進行，直到達到基本情況。

示例

這將呼叫 gcd 函式，引數為 24 和 36，它將返回它們的最大公約數，即 12。

def gcd(a, b):
   if b == 0:
      return a 
   else:
       return gcd(b, a % b) 
print(gcd(24, 36))

輸出

12

計算正整數的數字之和

在此示例中，sum_digits 函式採用正整數 n 作為引數，並返回其數字之和。如果 n 小於 10，則函式返回 n，這是基本情況。否則，函式將 n 的最後一位數字新增到使用整數除法 (// 運算子) 將 n 除以 10 得到的數字之和中，並使用結果遞迴呼叫自身。遞迴將持續進行，直到達到基本情況。

示例

這將呼叫 sum_digits 函式，引數為 12345，它將返回其數字之和，即 1 + 2 + 3 + 4 + 5 = 15。

def sum_digits(n):
   if n < 10:
      return n
   else:
      return n % 10 + sum_digits(n // 10) 
print(sum_digits(12345))

輸出

15

查詢字串的長度

在此示例中，string_length 函式採用字串 s 作為引數，並返回其長度。如果 s 是空字串 (''), 則函式返回 0，這是基本情況。否則，函式將 1 新增到透過切片第一個字元 (s[0]) 並使用剩餘字串 (s[1:]) 遞迴呼叫 string_length 函式獲得的字串長度中。遞迴將持續進行，直到達到基本情況。

示例

def string_length(s):
   if s == '':
      return 0
   else:
      return 1 + string_length(s[1:])
print(string_length('hello world'))

輸出

11

這將呼叫 string_length 函式，引數為 'hello world'，它將返回其長度，即 11。

遞迴函式可以為某些型別的問題提供強大而優雅的解決方案，但如果設計不當，它們也可能導致無限遞迴。務必仔細考慮基本情況並確保函式最終會達到它。