如何在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（其中%是模運算子），並返回結果。遞迴將持續到達到基本情況為止。

示例

這將呼叫引數為24和36的gcd函式，這將返回它們的最大公約數，即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得到的數字之和，並使用結果遞迴地呼叫自身。遞迴將持續到達到基本情況為止。

示例

這將呼叫引數為12345的sum_digits函式，這將返回其數字之和，即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

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

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