We review a method of the construction of cubic off-shell interaction vertices for Higher Spin fields. This method is based on the BRST approach and is valid both for flat and AdS backgrounds. As a particular illustration of this method we construct an off-shell extension of the vertices which are related to perturbative bosonic string theory. We discus a generalization of this method for higher order vertices and examine whether BCFW recursion relations are applicable for interacting Higher Spin gage theories.