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

慎用递归！

2024-07-06 18:40:24   228人阅读

其一，所有的递归实现都可以 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;
    }

 


联系
我们