How to avoid prohibited outer join in recursive CTE?

I have a table which represents acyclic dependencies between objects:

CREATE TEMPORARY TABLE dependencies
(
    obj_id        bigint,
    depended_upon bigint NULL
);
INSERT INTO dependencies
VALUES
    (1, NULL), -- 1 is not depended upon by any other object
    (2, 1),    -- 1 depends on 2
    (3, 4),    -- 4 depends on 3
    (3, 2),    -- ... and so does 2
    (4, NULL); -- 4 also is not depended upon by any other object

I'd like to determine the order in which I would have to prune objects so that no dependencies are violated, starting from the leaves. For this example, that result would look like this:

Each object is pruned in the first step in which no other object depends on it.

I've tried to do this with a recursive CTE:

WITH RECURSIVE deletion_order(obj_id, step) AS (
    SELECT obj_id, 0
    FROM dependencies
    GROUP BY obj_id
    HAVING COUNT(depended_upon) = 0
    UNION ALL
    SELECT dependencies.obj_id, step + 1
    FROM dependencies
             LEFT JOIN deletion_order ON dependencies.depended_upon = deletion_order.obj_id
    WHERE deletion_order.obj_id IS NULL
)
SELECT *
FROM deletion_order
ORDER BY step;

But Postgres complains:

> [42P19] ERROR: recursive reference to query "deletion_order" must not appear within an outer join

How can I accomplish this without an outer join? Note that the format of dependencies is flexible, if it needs to change to accommodate the solution.

If I understood what you are trying to achieve: you have most of the recursive queries figured out but somehow failed where it was the easiest:

1. The initialization of your CTE could be easier with WHERE depended_upon IS NULL.
2. I did not understand why you had put WHERE deletion_order.obj_id IS NULL in the recursive part of the CTE.
3. The JOIN should be an inner join, I did not understand why you thought you needed an outer join (I guess it is linked with the previous point but that did not help me understand).

Resulting query:

WITH RECURSIVE deletion_order(obj_id, step) AS (
    SELECT obj_id, 0
    FROM dependencies
    WHERE depended_upon IS NULL
    UNION ALL
    SELECT dependencies.obj_id, step + 1
    FROM dependencies
    JOIN deletion_order ON dependencies.depended_upon = deletion_order.obj_id
)
SELECT obj_id, MAX(step) AS MaxStep /*, MIN(step) AS MinStep (optional, see comment below)*/
FROM deletion_order
ORDER BY MaxStep;

So I do not know how to answer your question (How to avoid outer join) because you should not have felt the need to use an outer join in the first place.

I have answered a previous question as how to build a recursive CTE here. Maybe it is worth checking.