When I was a kid, my father bribed and coerced me into playing with LOGO (really showing my age here). I ended up spending a fair amount of time playing with it, (I guess) learning a lot of basic programming concepts along the way. I have memories of my grade-school self struggling to grok recursion.

There were a few aspects of LOGO that made it nice to learn on: most notable was immediate visual feedback and the "telling the turtle what to do" approach to imperative thinking.

When my wife was pregnant, I was overcome with nostalgia about LOGO and hacked together an in-browser collaborative playground (http://turtology.herokuapp.com), which seems like a total dead end at this point. LOGO was genius in it's time, but it seems terribly dated now, even to my fanboy eyes.

Apart from Scratch (which has a bunch of mentions already), the nicest thing I've seen is Cubetto: https://www.primotoys.com The combination of rapid feedback, simple interface and a real-world "avatar" for your instructions seem to make it really easy to figure out, as well as engaging. Also, now that I have a toddler, I can also appreciate the genius of the simple, physical interface. My 2-year old is still a long way from reading or writing, but is quite capable of recognising that a symbol can represent an action or concept.

Now I just need to figure out how to get one shipped to me (not trivial if you live in Africa).