Move the Turtle http://itunes.apple.com/us/app/move-turtle.-programming-for/... ($2.99)
Similar to the Logo programming language another commenter mentions. Starts simple, but goes into loop solutions a little too quick.
Cargo Bot (free!) http://itunes.apple.com/us/app/cargo-bot/id519690804?mt=8
Cargo Bot is much more visual, little or no text, but I think they dive into recursion much too fast (for 3 star solutions that is).
Bee Bot (free!) http://itunes.apple.com/us/app/bee-bot/id500131639?mt=8
Just discovered, also for the really little ones. No comments yet.