What I personally see in academic setting is that when recursion is taught, it's taught using examples where you would not want to use recursion.

It's easy to understand why recursion is useful when you are tasked with traversing a file system. It's not when the first example you are given is calculating Fibonacci sequence.

I like the way SICP handles this, actually. They state clearly (in the text, haven't watched the videos) that the naive recursive form for Fibonacci is only illustrative, then they proceed to provide the iterative form. Following that they have this paragraph:

> One should not conclude from this that tree-recursive processes are useless. When we consider processes that operate on hierarchically structured data rather than numbers, we will find that tree recursion is a natural and powerful tool. But even in numerical operations, tree-recursive processes can be useful in helping us to understand and design programs. For instance, although the first fib procedure is much less efficient than the second one, it is more straightforward, being little more than a translation into Lisp of the definition of the Fibonacci sequence. To formulate the iterative algorithm required noticing that the computation could be recast as an iteration with three state variables.

Hopefully a professor in a course would make similar statements (I know mine did, repeatedly). And, at least in my early programming courses, we quickly (within a week or two) went on to those other problems where recursion was a natural and useful solution. The professors [0] introduced problems where recursion was either necessary (using for/while loops would be a non-trivial transformation with no performance gain) or, like naive Fibonacci, natural expressions of the problem.

[0] I transferred universities, not all courses lined up so I got to see the second school's introduction to this topic even though I was past that point academically. I was an unpaid TA (technically I guess I was paying to be the TA).

This is like complaining that when piano teachers teach students how to hold their hands they teach it with scales where it doesn't really matter. The importance of hand position is obvious when you are tasked with playing chords in a real song.

The very first exercise should be as simple as possible. Explicitly because you're introducing a new concept and so want as little else in the way as you can arrange.

I disagree to an extent. Sure file system traversal is great motivating example (or any tree traversal example for that matter).

However, the Fibonacci sequence provides good end to end example of recursion, then tail recursion/dynamic programming.

A great way to let someone understand recursion is to let them learn how the principle of mathematical induction works. It gets rid of all the noise related to the programming language.

That's because in order to understand recursion you must first understand recursion.

I thought it was a dark art before I worked my way through a few chapters of the Little Lisper. Then the spell was broken