I feel fairly confident that I've solved the problems of teaching functions (http://akkartik.name/post/mu ; particularly the last couple of sections) and recursion (http://akkartik.name/post/swamp). Tl;dr - It just requires first introducing these ideas in a statement-oriented language without recursive expressions. Allow learners to see the steps unfold explicitly, one by one.

(Comment deliberately phrased provocatively to hear push-back and feedback.)