遞迴

(Recursion)

歡樂觀念題time

歡樂題目time

什麼是遞迴？

遞迴是一種函數調用自身的編程方法。

特點：

• 每次調用會處理一部分問題。
• 發生基礎情況（base case）就終止遞迴。

重複結構-講義

遞迴的結構

def recursive_function(parameters):
    if base_case_condition:
        return base_case_value
    else:
        return recursive_function(modified_parameters)

舉例#1
用迴圈&遞迴計算階乘

迴圈

def factorial_iterative(n):
    result = 1
    for i in range(1, n + 1):  # 從 1 到 n
        result *= i  # 累乘
    return result
 
# 使用迴圈計算階乘
result_iterative = factorial_iterative(int(input()))
print(result_iterative)  

遞迴

def factorial_recursive(n):
    if n == 0:  # 基礎情況
        return 1
    else:
        return n * factorial_recursive(n - 1)  # 遞迴調用
 
result_recursive = factorial_recursive(int(input()))
print(result_recursive)  

比較迴圈&遞迴

迴圈

def factorial_iterative(n):
    result = 1
    for i in range(1, n + 1):  # 從 1 到 n
        result *= i  # 累乘
    return result
 
# 使用迴圈計算 5 的階乘
result_iterative = factorial_iterative(5)
print(result_iterative)  # 輸出: 120

迴圈過程：

1. 初始化 \(\texttt{result}\) 為 1
2. 迴圈從 1 到 5：
3. 當 \(\texttt{i}\) = 1，\(\texttt{result}\) = \(1 * 1\)= 1
4. 當 \(\texttt{i}\) = 2，\(\texttt{result}\) = \(1 * 2\) = 2
5. 當 \(\texttt{i}\) = 3，\(\texttt{result}\) = \(2 * 3\) = 6
6. 當 \(\texttt{i}\) = 4，\(\texttt{result}\) = \(6 * 4\) = 24
7. 當 \(\texttt{i}\) = 5，\(\texttt{result}\) = \(24 * 5\) = 120
8. 最終返回 \(\texttt{result}\)，即 120

遞迴

def factorial_recursive(n):
    if n == 0:  # 基礎情況
        return 1
    else:
        return n * factorial_recursive(n - 1)  # 遞迴調用
 
# 使用遞迴計算 5 的階乘
result_recursive = factorial_recursive(5)
print(result_recursive)  # 輸出: 120

遞迴過程：

1. f(5) 調用 f(4)
2. f(4) 調用 f(3)
3. f(3) 調用 f(2)
4. f(2) 調用 f(1)
5. f(1) 調用 f(0)
6. f(0) 返回 1
   然後逐步返回計算結果：
   f(1) 返回 1、f(2) 返回 2、f(3) 返回 6、
   f(4) 返回 24、f(5) 返回 120

總結

遞迴：

• 代碼簡潔。
• 調用函數，直到基礎情況。
• 可能堆疊溢出，特別是大數字。

迴圈：

• 代碼較長，但效率較高。
• 使用變量來累計結果。
• 不會導致堆疊溢出。

題目區
作答區

例題#1