Phenotypic switching has been observed in laboratory studies of yeast and bacteria, in which the rate of such switching appears to adjust to match the frequency of environmental changes. Among possible mechanisms of switching are epigenetic influences on gene expression and variation in levels of methylation; thus environmental and/or genetic factors may contribute to the rate of switching. Most previous analyses of the evolution of phenotypic switching have compared exponential growth rates of noninteracting populations, and recombination has been ignored. Our genetic model of the evolution of switching rates is framed in terms of a mutation-modifying gene, environments that cause periodic changes in fitness, and recombination between the mutation modifier and the gene under selection. Exact results are obtained for all recombination rates and symmetric fitnesses that strongly generalize earlier results obtained under complete linkage and strong constraints on the relation between fitness and period of switching. Our analytical and numerical results suggest a general principle that recombination reduces the stable rate of switching in symmetric and asymmetric fitness regimes and when the period of switching is random. As the recombination rate increases, it becomes less likely that there is a stable nonzero rate of switching.