The problem is most introductions to recursion teach the syntax and implementation, not the conceptual structure.
The syntax is (usually) "a function calls itself, and there's a stack which can cause problems, except in some languages, probably."
The conceptual structure is "Solve a complicated problem by finding a single algo that successfully attacks the problem repeatedly, making the unsolved/unprocessed part smaller and smaller. Repeat until there is no unsolved/unprocessed part left."
Then illustrate with examples like Hanoi that demonstrate how simple logic applied over and over solves a complex puzzle.
Of course it's easy to introduce recursion with factorials, but factorials (etc) don't really explain why recursion is powerful.
They make it look like "Work out this simple math problem (which would be even easier with a for-loop, but whatever) with this one neat trick."
The syntax is (usually) "a function calls itself, and there's a stack which can cause problems, except in some languages, probably."
The conceptual structure is "Solve a complicated problem by finding a single algo that successfully attacks the problem repeatedly, making the unsolved/unprocessed part smaller and smaller. Repeat until there is no unsolved/unprocessed part left."
Then illustrate with examples like Hanoi that demonstrate how simple logic applied over and over solves a complex puzzle.
Of course it's easy to introduce recursion with factorials, but factorials (etc) don't really explain why recursion is powerful.
They make it look like "Work out this simple math problem (which would be even easier with a for-loop, but whatever) with this one neat trick."