Getting error recursive reference to query must not appear within its non-recursive term in postgres

I am running this query:

WITH RECURSIVE base_record AS (
  -- Base case: start from the initial defined term
  SELECT 
    dt.id AS defined_term_id,
    dt.name AS term_name,
    1 AS depth,
    ARRAY[dt.id] AS path  -- Track visited terms in an array
  FROM 
    "DefinedTerm" dt
  WHERE 
    dt.id = 'cm1avefkf003pe5h46ntdclns'  -- Start with the initial defined term
), graph as (
  SELECT * FROM base_record
  -- Traverse to related defined terms through ConditionSegments
  UNION ALL
      
      SELECT 
        csdt.id AS defined_term_id,
        csdt.name AS term_name,
        dt.depth + 1 AS depth,
        dt.path || csdt.id 
      FROM 
        graph dt
      JOIN 
        "Condition" c ON c."definedTermId" = dt.defined_term_id
      JOIN 
        "ConditionSegment" cs ON cs."conditionId" = c.id
      JOIN 
        "DefinedTerm" csdt ON cs."referencedDefinedTermId" = csdt.id
      WHERE 
        NOT csdt.id = ANY(dt.path)  


  -- Traverse to related defined terms through FormulaSegments
  UNION all 
      
      SELECT 
        fsdt.id AS defined_term_id,
        fsdt.name AS term_name,
        dt.depth + 1 AS depth,
        dt.path || fsdt.id
      FROM 
        graph dt
      JOIN 
        "FormulaSegment" fs ON fs."definedTermId" = dt.defined_term_id
      JOIN 
        "DefinedTerm" fsdt ON fs."referencedDefinedTermId" = fsdt.id
      WHERE 
        NOT fsdt.id = ANY(dt.path)
)

-- Select the recursive traversal results
SELECT *
FROM 
  graph
ORDER BY 
  depth, defined_term_id;

This is always throwing the error:

ERROR: recursive reference to query "graph" must not appear within its non-recursive term

If i remove one of the UNION ALL, so running this query:

WITH RECURSIVE base_record AS (
  -- Base case: start from the initial defined term
  SELECT 
    dt.id AS defined_term_id,
    dt.name AS term_name,
    1 AS depth,
    ARRAY[dt.id] AS path  -- Track visited terms in an array
  FROM 
    "DefinedTerm" dt
  WHERE 
    dt.id = 'cm1avefkf003pe5h46ntdclns'  -- Start with the initial defined term
), graph as (
  SELECT * FROM base_record
  -- Traverse to related defined terms through ConditionSegments
  UNION ALL
      
      SELECT 
        csdt.id AS defined_term_id,
        csdt.name AS term_name,
        dt.depth + 1 AS depth,
        dt.path || csdt.id 
      FROM 
        graph dt
      JOIN 
        "Condition" c ON c."definedTermId" = dt.defined_term_id
      JOIN 
        "ConditionSegment" cs ON cs."conditionId" = c.id
      JOIN 
        "DefinedTerm" csdt ON cs."referencedDefinedTermId" = csdt.id
      WHERE 
        NOT csdt.id = ANY(dt.path)  

)

-- Select the recursive traversal results
SELECT *
FROM 
  graph
ORDER BY 
  depth, defined_term_id;

Then it functions as expected.

Am I missing some specific syntax to specify that it is still in the recursion? I've tried to restructure the query in multiple different ways but can't seem to find the correct way to write it.

Solution

You can use parentheses to group these, e.g.:
_{demo at db<>fiddle}

WITH RECURSIVE base_record AS (
  -- Base case: start from the initial defined term
), graph as ( 
   select*from base_record 
   union all 
   (--open the parentheses here
   select...
   union all 
   select...
   )--this clarifies that everything inside is the recursive term
)--you can no longer add `CYCLE` or `SEARCH` here
SELECT*FROM graph
ORDER BY depth
       , defined_term_id;

That costs you search and cycle clauses, but if you're not using them anyways (you better be sure there are no loops in the hierarchy), it'll let you use the double union in the recursive term. That side-steps this one limitation, but it does not let you use multiple recursive statements in one. If you try, you'll get

ERROR:  recursive reference to query "cte" must not appear more than once

To do things like traversing the hierarchy in two directions, you could split that between two recursive CTEs:
_{demo at db<>fiddle}

with recursive base_record as (
  select id,parent,child,1 as depth
  from the_hierarchy
  where id=21
  limit 1)
,go_up as(
  select id,parent,child,depth as height 
  from base_record
  union all
  select h.id,h.parent,h.child,cte.height+1
  from the_hierarchy h join go_up as cte
    on cte.parent=h.id
)CYCLE id SET is_cycle USING path
,go_down as(
  table base_record
  union all
  select h.id,h.parent,h.child,cte.depth+1
  from the_hierarchy h join go_down as cte
    on cte.child=h.id
)CYCLE id SET is_cycle USING path
(select * from go_up where height<20
union all
select * from go_down where depth<20) order by id;

There might also be a way to re-arrange conditions in your current recursive term so that it does in one operation what you're currently doing in two, but you'll have to test on your setup if that's a better idea than the split. In my example that would mean looking up on cte.child=h.id OR cte.parent=h.id, plus rearranging the select list. In yours, you'd probably need to merge the join lists, which complicates things.

If you plan to do a lot of graph-related work in PostgreSQL, you might want to take a look at pgrouting and Apache AGE extensions.