Find all the countries I can visit by just crossing direct borders
You don't need to artificially limit number of iterations, according to PG manual using UNION without ALL is enough:


  Recursive Query Evaluation
  
  
  Evaluate the non-recursive term. For UNION (but not UNION ALL), discard duplicate rows. Include all remaining rows in the result of the recursive query, and also place them in a temporary working table.
  So long as the working table is not empty, repeat these steps:
  
  a) Evaluate the recursive term, substituting the current contents of the working table for the recursive self-reference. For UNION (but not UNION ALL), discard duplicate rows and rows that duplicate any previous result row. Include all remaining rows in the result of the recursive query, and also place them in a temporary intermediate table.
  
  b) Replace the contents of the working table with the contents of the intermediate table, then empty the intermediate table.
  


with recursive travel(country) as (
  select 'S'
  union
  select unnest(array[country1, country2]::text[])
    from travel
      join borders on (country = any(array[country1, country2]))
)
select country from travel where country &lt;&gt; 'S';


Btw, the problem is related to calculating transitive closure on a graph.