首页 > 代码库 > 慎用递归!

慎用递归!

其一,所有的递归实现都可以 iteratively 实现,虽然很多时候递归的代码更简洁。

其二,递归会产生多余的开销,包括空间和时间。

其三,如果一定要递归,不要在一个递归函数里做多件事,最好只做一件。

像下面的代码(未完成,因为写不下去了),试图在递归函数里做三件事,

(1) 检测路径是否存在

(2) 构造路径

(3) 处理cache

所以写到这个地步逻辑已经非常混乱了。

public boolean getPath(int x, int y, ArrayList<Point> path,
            HashMap<Point, Boolean> cache){
        
        if(!isFree(x, y)){
            return false;
        }

        // in the code below,
        // we are guaranteed point (x, y) is free
        
        Point p = new Point(x, y);
        
        if(x == 0 && y == 0){
            path.add(p);
            return true;
        }
        
        if(x >= 1 && getPath(x -1, y, path) ){
            path.add(p);
            return true;
        }
        
        if(y >= 1 && getPath(x, y-1, path)){
            path.add(p);
            return true;
        }
        return false;
    }