Is WITH RECURSIVE the right tool for my task?
Simpler and faster (and correct) with window functions and a subquery:

SELECT id, group_id, count(step) OVER (ORDER BY id) AS i
FROM  (
   SELECT id, group_id
        , lag(group_id, 1, group_id) OVER (ORDER BY id) &lt;&gt; group_id OR NULL AS step
   FROM   users
   ) sub;



id|group_id| i
--+--------+--
 1|       1| 0
 2|       1| 0
 3|       2| 1
 4|       1| 2
 5|       3| 3
 6|       3| 3



It's the same basic logic as discussed and explained in depth here (just simpler, without aggregation of rows):


Grouping or Window


There are also working solutions with a recursive CTE like you tried under the linked question, but those are substantially slower and more complex.

Andthere is also a plpgsql solution. Also more complex, but fastest.
Here is an optimized variant for your simple case without aggregation:

CREATE OR REPLACE FUNCTION f_users_i()
  RETURNS TABLE (id bigint, group_id bigint, i bigint) AS
$func$
DECLARE
   _last_group_id bigint;                 -- aux var to remember last group
BEGIN
   i := 0;                                -- init to 0

   FOR id, group_id IN
      SELECT u.id, u.group_id FROM users u ORDER BY u.id
   LOOP
      IF group_id &lt;&gt; _last_group_id THEN  -- next group starts
         i := i + 1;
      END IF;

      _last_group_id := group_id;         -- remember last group
      RETURN NEXT;
   END LOOP;
END
$func$  LANGUAGE plpgsql;


Call:

SELECT * FROM f_users_i();


Same result.

dbfiddle here (Postgres 9.6).
SQL Fiddle (the same, based on your fiddle on Postgres 9.3).

Aside: I doubt you need bigint for users and groups. Can probably all be just integer.