The generalized Fibonacci cube Q_h(f) is the graph obtained from the h-cube Q_h by removing all vertices that contain a given binary string f as a substring. In particular, the vertex set of the 3rd order generalized Fibonacci cube Q_h(111) is the set of all binary strings b₁b₂ …b_h containing no three consecutive 1's. We present a new characterization of the 3rd order generalized Fibonacci cubes based on their recursive structure. The characterization is the basis for an algorithm which recognizes these graphs in linear time.