演算法筆記：迴圈與遞迴的等價轉換三部曲

前言

迴圈與遞迴是程式設計的兩大控制流基石。本文透過三個經典範例——累加求和、陣列搜尋、鏈表遍歷——展示如何將迴圈改寫為遞迴，並分析兩者差異。

1. 累加求和：1 + 2 + ... + m

迴圈版

int sum_loop(int m)
{
    if (m < 0) return -1;
    int total = 0;
    for (int i = 0; i <= m; ++i) total += i;
    return total;
}

遞迴版

int sum_rec(int m)
{
    if (m == 0) return 0;
    return m + sum_rec(m - 1);
}

差異分析

2. 陣列線性搜尋

迴圈版

int find_loop(const int a[], int n, int val)
{
    for (int i = 0; i < n; ++i)
        if (a[i] == val) return i;
    return -1;
}

遞迴版（尾端遞迴）

int find_rec_helper(const int a[], int n, int val, int idx)
{
    if (idx == n) return -1;
    if (a[idx] == val) return idx;
    return find_rec_helper(a, n, val, idx + 1);
}

int find_rec(const int a[], int n, int val)
{
    if (a == NULL || n == 0) return -1;
    return find_rec_helper(a, n, val, 0);
}

此為尾端遞迴，編譯器最佳化可自動轉為迴圈，消除堆疊增長。

3. 鏈表列印

typedef struct Node { int data; struct Node *next; } Node;

/* 迴圈 */
void print_loop(const Node *head)
{
    for (const Node *p = head; p; p = p->next)
        printf("%d\n", p->data);
}

/* 遞迴 */
void print_rec(const Node *head)
{
    if (!head) return;
    printf("%d\n", head->data);
    print_rec(head->next);
}

遞迴版極度簡潔，但長鏈表恐爆堆疊。

核心觀點總結

1. 迴圈是特殊的遞迴：尾端遞迴 ≡ 迴圈。
2. 遞迴 ≡ 顯式堆疊 + 迴圈：所有遞迴皆可手動模擬堆疊轉為迴圈。
3. 選擇原則：
   　　• 簡單、深度可控、可讀性優先 → 遞迴
   　　• 高效能、深度大/未知、嵌入式 → 迴圈
4. 掌握堆疊機制是寫好遞迴與非遞迴轉換的關鍵。