精巧的代碼（一）

求最大公約數

int gcd(int a, int b)
{
    return b ? gcd(b, b % a) : a;
}
           

這一行代碼實作了著名的輾轉相除法求兩個數的最大公約數，具體的數學原理可檢視相關書籍，本文主要讨論代碼。

這行代碼使用了遞歸的思想，而遞歸則是基于代碼運作壓棧和彈棧的機制在很對設計精巧的代碼都使用了遞歸這種思想，如二叉樹的周遊。

二叉樹周遊

void preOrder(Tree *root)
{
    if (root != NULL)
    {
        preOrder(root->right);
        preOrder(root->left);
    }
}
           

這幾行代碼實作了二叉樹的前序周遊，二叉樹的周遊還有中序周遊，後續周遊等，也是基于遞歸的思想。

但是遞歸算法并不滿足所有的應用場景，在一些情況下還會嚴重降低代碼的性能，下面幾個例子就是錯誤使用遞歸的範例。

斐波那契數列

int fbi(int n)
{
    if (n == )
        return ;
    if (n == )
        return ;
    reuturn fbi(n - ) + fbi(n - );
}
           

使用遞歸實作斐波那契數列看似輕巧，帶所帶來的計算複雜度确難以承受，是以在一些問題通常使用動态規劃的思想來解決問題。使用動态規劃實作斐波那契數列如下。

int fbi(int n)
{
    int array[];
    array[] = ;
    array[] = ;

    for (int i = ; i < n; i++)
        array[i] = array[i - ] + array[i - ];

    return array[n-];
}
           

使用動态規劃來提升算法效率的思想是使用空間換時間。在某些需要多次使用中間計算結果的情況下，開辟空間去記錄這個結果是很有必要的。動态規劃關注的重點是算法的狀态轉移方程，而此問題的狀态轉移方程非常明了

a(n+2) = a(n) + a(n+1)

，對于動态規劃的問題，後面會繼續延伸。