You're right, Python isn't beautifully minimal. But the Scheme version is boring ;)

Rather than asking the interview candidate to use recursion for a problem that shouldn't be solved using recursion (unless in a language where recursion is the idiomatic iteration method), it would be better to ask about a problem that is best solved using recursion rather than printing "Hello world" -- perhaps something from Project Euler (http://projecteuler.net/).