Summary: In a graph \(G\), a \(k\)-container \(C_k(u,v)\) is a set of \(k\) disjoint paths joining \(u\) and \(v\). A \(k\)-container \(C_k(u,v)\) is \(k^{*}\)-container if every vertex of \(G\) is passed by some path in \(C_k(u,v)\). A graph \(G\) is \(k^{*}\)-connected if there exists a \(k^{*}\)-container between any two vertices. An \(m\)-regular graph \(G\) is super-connected if \(G\) is \(k^{*}\)-connected for any \(k\) with \(1 \leqslant k \leqslant m\). In this paper, we prove that the recursive circulant graphs \(G(2^m,4)\), proposed by J.-H. Park and K.-Y. Chwa [Theor. Comput. Sci. 244, No. 1–2, 35–62 (2000; Zbl 0945.68003)], are super-connected if and only if \(m\neq 2\).