遞迴的概念

1.1 遞迴的定義與主要概念。

遞迴就是某東西自己不斷地重複。試想，你有個說明書，而這個說明書的一部分告訴你要遵循這個說明書。就像是給了你一個指令讓你重複這個指令。

現實生活的例子：

兩面鏡子互相對照：

想像一下你站在兩面鏡子之間。你會看到自己的倒影，而在倒影中也看到自己的倒影，這樣反反覆覆。這就是一個遞迴的例子，因為每個鏡子都顯示另一個鏡子的反射。

俄羅斯娃娃：

俄羅斯娃娃是一個裡面有另一個娃娃，而那個娃娃裡面又有另一個，如此重複下去。當你到達最小的娃娃時，就沒有什麼可以再打開的了。這就像 遞迴中的基本情況—停止的時刻.

分披薩：

想像你把披薩切成兩半。然後拿起其中一半再切成兩半，這樣持續下去，直到切到的片段太小不能再切。切分這個過程就是遞迴，而 你不能再切的時刻，就是基本情況.

重要！ 遞迴不是命令的無限重複，而是把複雜問題分解成部分，解決這些部分的方法和解決整個問題的方法是類似的。

這是怎麼運作的？

理解遞迴需要掌握兩個主要概念：

• 基本情況: 這是停止遞迴的條件。例如，在俄羅斯娃娃的例子中基本情況就是當你打開最小娃娃時，裡面已經沒有東西。
• 遞迴情況: 就是當任務被更小的部分重複。在披薩的例子中，你會分割一個片段，然後分割一半，這樣下去。

為什麼這有用？

遞迴幫助解決複雜的問題，將其分解為更簡單的部分。與其一次解決整個問題，不如一次解決一小部份。

其它生活中的例子：

故事中的故事：

想像故事中的主角再講另一個故事，而那個故事的主角開始講另一個故事。當其中一個故事結束時，你會回到前一個故事。基本情況就是當最後一個故事結束時。

遞迴圖案：

你畫了一個大三角形，然後在這個三角形的每個角畫一個小三角形，這樣一直下去，直到三角形太小無法再畫。基本情況就是三角形太小，以至於無法畫下去。

1.2 基本情況：定義與例子。

基本情況—這是停止遞迴呼叫並使函數返回具體值的條件。通常這是對問題最簡單和最明顯的解決方案，它不需要進一步的遞迴。

基本情況的例子：

數字的階乘：

數字 n 的階乘表示為 F(n) == 1*2*3*…*n。同樣明顯地，F(n) == n* F(n-1)。

基本情況: 數字 0 或 1 的階乘等於 1. F(0) == F(1)==1

def factorial(n):
    if n == 0 or n == 1:
        return 1  # 基本情況
    else:
        return n * factorial(n - 1)
        

費波那契數列：

費波那契數列：1, 1, 2, 3, 5, 8, 13, … 每個後續數字是其前兩個數字的和。對於 F(n) == F(n-1) + F(n-2)

基本情況: 前兩個費波那契數為 1，所以 "零" 費波那契數是 0。或 F(0) = 0 和 F(1) = 1。

def fibonacci(n):
    if n == 0:
        return 0  # 基本情況
    elif n == 1:
        return 1  # 基本情況
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)
        

1.3 遞迴情況：定義與例子

遞迴情況—這是函數的一部分，通過使用新的參數來呼叫自己以解決任務，讓解決方案更接近基本情況。每次遞迴呼叫會減少或修改任務，以最終達到基本情況。

遞迴情況的例子：

數字的階乘：

遞迴情況：數字 n 的階乘等於 n 乘以數字 n-1 的階乘。

def factorial(n):
    if n == 0 or n == 1:
        return 1  # 基本情況
    else:
        return n * factorial(n - 1)  # 遞迴情況
        

費波那契數列：

遞迴情況：F(n) 是 F(n-1) 和 F(n-2) 的和。

def fibonacci(n):
    if n == 0:
        return 0  # 基本情況
    elif n == 1:
        return 1  # 基本情況
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)  # 遞迴情況
        

1.4 遞迴算法的例子

1. 二元樹遍歷：

中序遍歷的例子。

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        
def inorder_traversal(node):
    if node:
        inorder_traversal(node.left)
        print(node.value)
        inorder_traversal(node.right)
        
# 使用例子
root = Node(1)
root.left = Node(2)
root.right = Node(3)
inorder_traversal(root)
        

2. 查找列表中的最大元素：

def find_max(lst):
    if len(lst) == 1:
        return lst[0]  # 基本情況
    else:
        max_of_rest = find_max(lst[1:])  # 遞迴情況
        return max(lst[0], max_of_rest)
        
# 使用例子：
print(find_max([1, 5, 3, 9, 2]))  # 輸出: 9
        
        

3. 遞迴二元搜索：

def binary_search(arr, target, left, right):
    if left > right:
        return -1  # 基本情況: 元素未找到
    mid = (left + right) // 2
    if arr[mid] == target:
        return mid  # 基本情況: 元素找到
    elif arr[mid] < target:
        return binary_search(arr, target, mid + 1, right)  # 遞迴情況
    else:
        return binary_search(arr, target, left, mid - 1)  # 遞迴情況 
# 使用例子：
arr = [1, 2, 3, 4, 5, 6, 7]
print(binary_search(arr, 5, 0, len(arr) - 1))  # 輸出: 4