精巧的代码（一）

求最大公约数

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)

，对于动态规划的问题，后面会继续延伸。