遞歸算法的幾個用例

1. 遞歸逆序列印字元串

void reverse(char *s)

{

     if(*s != )

    {

        reverse(++s);

        putchar(*(s-1));  // 巧妙的利用棧的先進後出的特點

    }

}

2. 遞歸方式将連結清單逆序

// p 為指向非空單連結清單中第一個結點的指針，本算法逆轉連結清單并傳回逆轉後的頭指針。基本思路是：如果連結清單中隻有一個結點，則空操作，否則先逆轉a2開始的連結清單，然後将 a1聯接到逆轉後的連結清單的表尾(即a2)之後。

LinkList reverse(LinkList p)

    if(p->next == NULL) return p;   // 連結清單中隻有一個結點，逆轉後的頭指針不變

    else

    {

        q = p->next;          // q為連結清單(a2,...an)的頭指針

        h = reverse(q);       // 逆轉連結清單(a2,...an)，并傳回逆轉後的頭指針

        q->next = p;          // 将a1聯接在a2之後

        p->next = NULL;

        return h;               // (a2,...,an)逆轉表的頭指針即為(a1,a2,...,an)

    }

3. 遞歸方式合并兩個連結清單

Node *MergeRecursive(Node *head1, Node *head2)

    if(head1 == NULL)

       return head2;

    if(head2 == NULL)

       return head1;

    Node *head = NULL;

    if(head1->data < head2->data)

       head = head1;

       head->next = MergeRecursive(head1->next, head2);

       head = head2;

       head->next = MergeRecursive(head1, head2->next);

    return head;