fibonacci数列的递归和非递归算法

Fibonacci数列，我想有的人在大学甚至高中就已经接触过了，其数学表达如下：
给定一正整数x，
F(x) = 1 ( x=1 或 x=2)
F(x) = F(x-1) + F(x-2) ( x > 2 )
也就是说，前2个数是1， 后面的的数， 是前面2个数之和

如果用计算机来解决的话， 可有递归和非递归算法， 对于递归算法很好理解， 也很好实现，直接照着上面的公式来就行了， 下面是递归算法的c语言实现：

long fab(int n)
    {
        if ( n == 1 || n == 2 )
            return 1;
        else
            return fab(n-1) + fab(n-2);
    }    

可以看见，代码非常的简单，也很好理解，然而， 这个效率是极其低下， 我试图打印前50个数， 结果发现程序运行了近2分钟才返回，打印的越多， 运行的越慢， 所耗费的时间成级数增长。

下面是非递归算法， 虽然看起来复杂一些， 但是时间复杂度却是O(n)。而且同样打印前面50个数， 只用了1秒钟， 可见，这个差别是多么的巨大。 下面是非递归算法的c语言代码：

long fabx(int n)
    {
        if ( n == 1 || n == 2 )
            return 1;
        
        long xx = 1;
        long yy = 1;
        long res = 0;
        for ( int i = 0; i < n - 2 ; i++ )
        {
            res = xx + yy;
            xx = yy;
            yy = res;            
        }
        return res;
    }