Recognition and binding of specific sites on DNA by proteins is central for many cellular functions such as transcription, replication, and recombination. In the process of recognition, a protein rapidly searches for its specific site on a long DNA molecule and then strongly binds this site. Here we aim to find a mechanism that can provide both a fast search (1-10 sec) and high stability of the specific protein-DNA complex ($K_d=10^{-15}-10^{-8}$ M). Earlier studies have suggested that rapid search involves the sliding of a protein along the DNA. We consider sliding as a one-dimensional diffusion in rough (random) energy landscape formed by the energy of binding to consecutive sites on the DNA. Our analytical results and computer simulations demonstrate that, in spite of the landscape's roughness, rapid search can be achieved by a combination of 1D and 3D diffusion. We estimate the range of the specific and non-specific DNA-binding energy required for rapid search. We also establish that, paradoxically, realistic energy functions cannot provide both rapid search and strong binding. To reconcile these two fundamental requirements we propose a search-and-recognition mechanism that involves the coupling of protein binding and protein folding. Our mechanism is supported by experimental evidence and known structures of protein-DNA complexes.