[Aozora7]

It was counterproductive for me when recursion was taught with Fibonacci and factorials. They were literally the opposite of easy to understand for me, I had absolutely no idea why those examples actually worked, so I just gave up and treated them like magic.

I think recursion should be taught with examples that would be easier for a student to write with recursion than without it. For example, listing all files in a directory.

[lupire]

Why would you think enumerating a directory is not magic?

Walking a tree / BFS is quite easy to implement iteratively, using a search queue. It's a common example for teaching Lisp.

Recursion is most natural in problems like implementing evaluation of an abstract syntax trer:

    eval(tree) = 
      apply(node(tree), 
            map(eval, leaves(tree))
           )

[DeathArrow]

And since a tree is a graph, you can just use adjacency matrix and two loops. :)

O(n^2) but very simple.

[usrn]

That would require OS specific APIs which are distracting.