Which books would you recommend about Recreational Mathematics?

By this I mean books with math puzzles and problems similar to the ones you would find in mathematical olympiads.

If you're after Olympiad-level books, get The IMO Compendium which is a collection of problems from the International Math Olympiad, 1959-2004. You can find similar books with national Olympiad problems by going to Amazon and searching for "mathematical Olympiad".

Two books that offer collections of techniques useful for olympiad-level contests are Paul Zeitz's The Art and Craft of Problem Solving and Arthur Engel's Problem Solving Strategies.

There are lots of other books with similar titles and descriptions. Just follow Google Books's suggestions.

Art of Problem Solving: http://www.artofproblemsolving.com/Store/index.php

Anything by Martin Gardner.

THE PENGUIN DICTIONARY OF CURIOUS AND INTERESTING NUMBERS, by David Wells.

Sample entry: $199: 199 + 210n$ for $n = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9$ provides the smallest $8, 9$ and $10$ primes in arithmetical progression.

Obviously you can reformulate any of the information given in the book as a problem to pose to someone else.