As an artist and a programmer I look to identify three principle aspects when I am observing recursion or considering the concept in use,
identify a rule which has self-reference (in programming an example is a named function containing the same named function),
producing a process of repetition with the requirement of a break case (to stop looping forever),
resulting in observable self-similar patterns.
The last rule will not be observable feature of the results of a program--you will not see the pattern but have the knowledge the same rule was applied multiple times. The beauty of recursion in programming is "observed" in the economical code. The reverse is the case in biological growth and natural ecological patterns where we observe number three and infer one (and maybe two).
Standing on the shoulders of giants, I hope I am correct in suggesting these three elements are, in these two combinations, required to distinguish recursion from iteration. If your project can teach students to make this distinction they will have learned recursion.
Its with this in mind my suggestion for teaching recursion is to observe nature. A most excellent primer on observing recursion is the Nova program Hunting the Hidden Dimension (and for the time being can be viewed at Youtube). I wish to point out this passage from the video describing recursion in trees:
5:15 "One of the most familiar examples of self similarity is a
tree. If we look at each of the nodes, the branching nodes of this
tree, what you will actually see is that the pattern of branching is
very similar throughout the tree."
What is more amazing is different trees have different patterns. The count of tree limbs from one compass point, twisting upward to the next tree limb at the same compass point with be a specific number. This makes for an interesting nature walk with so many points of observation from the trunk to the tips of the branches. The tree is the best example, but of course recursion doesn't stop there.
Going one step further, if you were teaching art, this knowledge is very useful in mapping what your mind says you're seeing to the true physical reality. This is because of the optical illusion of foreshortening when drawing objects which are arranged pointing toward the artist. Knowledge of recursion helps the artist understand what they are seeing when a branch is see from different angles. Again from the Nova episode, Mandelbrot said "think not of what you see, but what it took to produce what you see." Your natural drawings will be better because of it.