Actually, you're talking about clipless pedals. They use a cleat on the pedal and on the shoe. They're called clipless because the alternative (their predecessor, so to speak) are pedals using a cage around the foot known as a toe clip.
Anywho, yes, I use SPD (Shimano's "standard") clipless pedals and shoes on my recumbent. I've heard some say that with recumbents, you put your foot further forward on the pedal (between the ball of your foot and your heel) compared to a "wedgie", but I find the ball-of-the-foot position to be quite natural.