Well, the Brookline Schools experiment with LOGO (some 40 or so years ago) demonstrated that people can learn and understand recursion. The big deal is to show the distinction between the text of the procedure and the process of evaluating it (known in those days as the `Little Man' model). When I used to teach with that, we'd actually have students acting out the role of the Little Man (`I need f(2), can someone do that for me? I'll wait for the answer').