一个面试题-ListView加载斐波那契数列

公式

F(0)=0,F(1)=1,F(n)=F(n-1)+F(n-2)  
即一个位置的值为前两个值的和
0，1，1，2，3，5，8，13，21...

• 是不是想用递归写法？

public class FibonacciAdapter extends BaseAdapter {
    ...
    @Override
    public Object getItem(int position) {
        if (position < 2)
            return position;
        return (int)getItem(position - 1) + (int)getItem(position - 2);
    }
    ...
}

如果这么写，加载20个应该问题不大，递归的深度比较浅，CPU可以很快运算完成，界面会略有卡顿
但如果加载35个以上，由于递归比较深，CPU会长时间处于高负荷状态，界面直接卡死
例如加载40个：

递归计算.JPG
PS:如果图片看不清楚，可以点击图片后【查看原图】

• 正确的写法是这样的

public class FibonacciAdapter extends BaseAdapter {
    ...
    @Override
    public Object getItem(int position) {
        return computeFabo(postion);
    }

    //F(0)=0,F(1)=1,F(n)=F(n-1)+F(n-2)
    public long computeFabo(int position) {
        if (position < 2)
            return position;
        long preV = 0;
        long currentV = 1;
        long newV = 0;
        for (int i = 2; i <= position; i++) {
            newV = preV + currentV;
            preV = currentV;
            currentV = newV;
        }
        return newV;
    }
    ...
}

cache.JPG

对比可以看到，性能差距简直不是一星半点，所以不要看到递归就傻傻的递归，递归的深度越深，CPU运算起来越困难！