寫在前面

繼上篇博文裡介紹的C語言常見基礎演算法，本篇在於演算法的思路的整理和常見的演算法程式設計實現。

遞回的含義和常見應用

【定義】遞回具體用法其實就是讓你把一個問題分解成很多個類似的情況，雖然你要解決這個問題非常難，莫名其妙，要你想幾年，但是把他一直遞回分解，就變成很好理解的單種情況，而你整個問題又是跟這個單種情況類似，把整個問題通過遞回呼叫一層一層分解到最低階簡單的那種情況，就是你所需要理解的了。
一個函數在它的函數體內呼叫它自身稱爲遞回呼叫。這種函數稱爲遞回函數。C語言允許函數的遞回呼叫。在遞回呼叫中，主調函數又是被調函數。執行遞回函數將反覆反復呼叫其自身，每呼叫一次就進入新的一層。
常見的用法：1、斐波那契數列

// 計算fibonaci數列---2
int fibonaci_2(int n)
{
    if(n<=2)
    {
        return 1;
    }
    else
    {
        return fibonacci_2(n-1)+fibonacci_2(n-2);
    }
}
0 1 1 2 3 5 8....
或者定義一個公有的temp，返回該值。邊界條件可以是n=0\n=1

2、階乘

n!=1 (n=0,1)
n!=n*(n-1)! (n>1)
(n-1)!=(n-1)*(n-2)!
具體如下
long ff(int n)
{
	long f;
	if(n<0) printf("n<0,input error");
	else if(n==0||n==1) f=1;
	else f=ff(n-1)*n;
	return(f);
}
經過n次入棧後，剩下n=1的已知值，後續全部相乘，直接得到答案，返回結果，出棧一次

3、倒序輸出字串、數位轉字元等

void alpha_exchange_2(void)
{
    char temp;
    scanf("%c",&temp);
    if(temp != '\n') // 給出正確的退出條件
    {
        alpha_exchange_2();
        printf("%c",temp);
    }
}
void alpha_exchange_3(void)
{
    char temp;
    scanf("%c",&temp);//temp的值必須要先由輸入獲得
    if(temp == '\n') // 給出正確的退出條件
    {
        // printf("%c\n",temp);
        return temp;
    }
    alpha_exchange_3();
    printf("%c",temp);
}

void binary_to_ascii(unsigned int value)
{
    unsigned int quotient;
    quotient = value / 10;
    //將數據按照高位到地位逐漸變小
    if(quotient != 0)
    binary_to_ascii(quotient);
    //按照順序輸出每一位值
    putchar(value%10+'0');
}
該函數出棧了n次，將每一次傳入參數出棧計算，都是結果的一部分

4、翻轉鏈表，翻轉佇列

struct ListNode* reverseList(struct ListNode* head){
    if (head == NULL || head->next == NULL)
        return head;
    else
    {
        struct ListNode *newhead = reverseList(head->next);
        head->next->next = head;
        head->next = NULL;
        return newhead;
    }
}

//遞回實現
struct node * reverse(struct node *pHead)
{
    if (pHead == NULL || pHead -> pNext == NULL)
    {   
        return pHead;
    }   
    struct node *p = pHead -> pNext;
    struct node *pNewHead =  reverse(p);
    p -> pNext = pHead;
    pHead ->pNext = NULL;
    return pNewHead;
}

【優化方法介紹（尾遞回）】
從我給出的第一演算法可以看出，先進棧再出棧，遞回的效率是很低的。速度上完全比不上迭代（回圈）。但是尾遞回引入了一個新的函數參數，用這個新的函數參數來記錄中間值。普通遞回階乘fac(x),就1個x而已，尾遞回用2個參數fac(x,y),y存放階乘值。

int fac(int x, int y) {
	if (x == 1)
		return y;
	else return fac(x-1, y*x);
}

int ff(int x)
{
	if (x == 0)
		return 1;
	else return fac(x,1);
}

int fac(int x, int y)
{
	if(x == 0)
	return 1;
	if(x == 1)
	{
		return y;
	}
	else
	{
		return fac(x, x*y);
	}
}
對於這個程式我們先看函數ff，函數ff其實是對fac的一個封裝函數，
純粹是爲了輸入方便設計的，通過呼叫ff(x)來呼叫fac(x,1)，

這裏常數1就是當x=1的時候階乘值了，我通過走一遍當x=3時的值即爲3!來說明一下。首先ff(3)，x!=0，執行fac(3,1).第一次呼叫fac，x=3，y=1，x!=1，呼叫fac(x-1,yx)，新的x=2，y=3*1=3，這裏可以看到，y已經累計了一次階乘值了，你會發現這個遞回更類似於迭代了。事實上我們用了y記錄了普通遞回時候，出棧的乘積，所以減少了出棧後的步驟。

【推薦文章】
本博文詳細介紹了遞回的入棧和出棧的過程，需要特別強調的是遞回的結束條件以及選用遞回的傳入參數。
在呼叫函數之後的程式碼是在函數返回後執行的，因此會層次的呼叫出棧的變數。

C語言-遞回演算法思想

寫在前面

遞回的含義和常見應用