_(Disclaimer: I'm not a computer scientist. I wish more people would address this interesting question.)_

There are many options out there. A few of them have titles in the lines of _"Introduction to Computer Science"_, _"Fundamentals of Computing"_, etc.

For example, I enjoyed reading _CS for All: An Introduction to Computer Science Using Python_ last year, although I did not work on its introduction to objects because I had a bit of trouble with the Python graphics library of their choice, so I just glanced the contents since objects were already a familiar topic.

I was satisfied with its treatment of Python, functions and recursion, as well as other subjects I wanted to dive into a bit more, so it was a generally enjoyable read.

I've found it relatively short and now I'm looking for complementary texts. Titles whose TOC (Table of Contents) caught my attention (in no particular order):

* _Introduction to Computation and Programming Using Python_
* _Computer Science Illuminated_
* _Python Programming: An Introduction to Computer Science_
* _Explorations in Computer Science_

And there are certainly many others available and more or less up-to-date.

BTW, regarding being up-to-date, this is probably bad advice (and possibly worth a separate question), but I once misread the introduction from _Simply Scheme_ (which is also an introductory CS book, and is known as a prequel to _Structure and Interpretation of Computer Programs_) as stating that CS books have a ten-year-or-so lifespan in terms of how well they address the ever-changing trends from the field (certainly a terrible misread, and people would throw _SICP_ at me as a counterexample - BTW, there is a JavaScript edition of SICP now). But it stuck with me, and now I personally tend to favor more recent introductory CS books such as the ones I mentioned.

So this is just something to consider. You are probably okay reading any book or edition that is not terribly old or adopts an unfavorable language to teach its concepts. Python is a popular language choice now, Java had its heyday, languages such as Scheme are considered good for teaching CS concepts, and you certainly can find more or less up-to-date choices for C and other reasonably popular languages you might be familiar with, or even language-agnostic options (such as the _Computer Science Illuminated_ one that I mentioned earlier, with which you are free to adopt any language you prefer).