To be on this list the book must satisfy the following conditions:
Here are my two contributions to the list:
On
I am quite prepared to be down-voted on this one, but here goes ...
I would have to include Andre Weil's book "Basic Number Theory", since:
All the mathematicians I know regard basic number theory as fun and recreational.
The author states in the preface: "No knowledge of number theory is pre-supposed in this book, except for the most elementary facts about rational integers".
On
I'd like to add "A Budget of Trisectors" by Underwood Dudley. It's the author's experiences with false constructions of an angle trisection with compass and straightedge, and has some very interesting debates about what proofs are and how to explain them to the layperson.
On
To my opinion Polya, G. "Mathematics and Plausible Reasoning" would go here as philosophy of math and a recreational book as well with many problems and examples, illustrating some well-known mathematical discoveries of past.
On
This is a topic that has been hit pretty well at MO in a few ways.
The most related question would be favorite popular math book, which has 60 answers and many (more than 60) books mentioned, along with their author(s) and a short description.
The question how to write popular mathematics well has some related bits, too. And on a not-so-recreational-level, there is the question Examples of great mathematical writing, which includes everything by Serre and the analysis series by Stein and Shakarchi.
On
A whole lot of books by Raymond Smullyan, but To Mock a Mockingbird, which presents combinatory logic is definitely on the list, as is one of the several books in which he presents Gödel's first incompleteness theorem as a knights-and-knaves puzzle.
On
It is interesting that no one has mentioned these two so far.
Journey through Genius: The Great Theorems of Mathematics by William Dunham
The Music of the Primes: Searching to Solve the Greatest Mystery in Mathematics by Marcus du Sautoy
On
Most introductory Dover books are pretty cheap and don't require too much background.
For example, Pinter's A Book of Modern Algebra is, in my opinion, quite well written and rich with exercises. (it lacks answers to all but a few questions, though).
The Number Devil: A Mathematical Adventure by Hans Enzensberger is a fun survey of elementary number theory. It's structured similarly to the series of children's books 'Diary of a Wimpy Kid.'
On
Gödel, Escher, Bach: An Eternal Golden Braid, by Douglas Hofstadter. Very interesting read - details Gödel's Incompleteness Theorem, and manages to touch on a wide variety of topics, including genetics, reductionism/holism, programming, art, music, brains, zen, language, etc. The central idea is that a special kind of self-reference (which Hofstadter calls a strange loop) seems to pop up everywhere, and is perhaps at the heart of intelligence and the appearance of meaning in a structure made up of meaningless parts.
On
On
The book that inspired me to change majors from chemistry to mathematics and kept me going through the dark times during my father's cancer: I Want To Be A Mathematician by Paul Halmos. It is an addicting read with so much that is wise about mathematics, mathematicians and the entire culture surrounding them.It should be required reading for any new mathematics student.
On
I really enjoyed Fermat's Enigma by Simon Singh. This definitely falls more under the heading "philosophy of math", but it's great in conveying to laypersons (like me) what an interesting and thrilling field mathematics is.
On
One Minute Mysteries: 65 Short Mysteries You Solve With Math!
simply for the sheer whimsy of reading a book written by a 9-year-old.
Also because you can e-borrow it for free:
On
Unfortunately, they are priced quite expensively, but the four volumes of Winning Ways for your Mathematical Plays are simply wonderful. It can be fairly heavy reading (I've only skimmed parts of the various volumes), but it provides directly accessible mathematics without any prerequisite requirements.
On
Both of the following books are really interesting and very accessible.
Stewart, Ian - Math Hysteria This book covers the math behind many famous games and puzzles and requires very little math to be able to grasp. Very light hearted and fun.
Bellos, Ales - Alex's Adventures in Numberland This book is about maths in society and everyday life, from monkeys doing arithmetics to odds in Las Vegas.
On
Does God Play Dice? The New Mathematics of Chaos by Ian Stewart
This book explains very nicely about a very complicated topic. I liked simple calculator example which shows chaos with a basic equation like $x^2$
http://www.amazon.com/Does-Play-Dice-Mathematics-Chaos/dp/0631232516
How to Cut a Cake: And Other Mathematical Conundrums by Ian Stewart
This one is pure fun.
So, my favorite recreational math book growing up was Mathematical Mysteries, by Calvin Clawson. It's light on rigor, but it contains a lot of interesting mathematical concepts.
Also, I think it's important to list Herbert Robbins as an author when talking about What is Mathematics?, seeing how he was the one doing the actual writing.