I'll share why I struggled with recursion (as best as I remember):
Most programming I learned was imperative. As I wrote the code, I imagined the execution in my head. This led to a problem where when I was halfway through a function, and it referred to itself, my brain would segfault. How could something I was not yet done writing refer to itself? I hadn't finished yet, so my brain could not comprehend what such a reference would mean.
It was also difficult because I wanted to think of functions as nice neat pieces of code that would take some data, do it's thing, and return a value. I could mentally inline a function call without much effort.
But when recursion is introduced, the floor drops out of my mental inlining. Suddenly my mental effort for such things becomes huge. For me anyway. My brain doesn't like to float around in abstraction land for long, it needs to periodically be anchored in the concrete. Otherwise I quickly lose my sense of direction and orientation... I lose my context.
Declarative languages actually make these easier, for me, because I'm not mentally executing a recipe as I write. I am giving a piece-wise description of what something is. So there is no mental tracing.
I expect the a-ha moment for recursion is different for everyone. But just showing recursion in many different forms would probably help. For example, show fib sequence generation where instead of the function calling itself, each function calls a uniquely named function... such that you concretely demonstrate building the first 5 or so numbers in the sequence...
Then show the similarity of the functions, show what the computer has to keep track of with the nested function calls, and step by step work your way to straight recursion.
Show it in BASIC with GOTO statements.
Finding as many different ways to concretely demonstrate an abstract concept will help reach more people.
As someone who enjoys teaching programming[1], your comment was my favorite of the day[2]. My learning experience was similar to yours, starting with imperative languages, so you got me to think about how I think about recursion today, given our shared baggage:
1. I do still inline recursive functions, but I've learned to selectively inline just the base case when I first implement recursion. Paradoxically, experience with lisp helped me with recursion in C, particularly Common Lisp's trace facility which taught me to visualize stacks of multiple function calls (whether recursive or not) rather than a single one at a time.
2. I've learned to think declaratively even when I program in C. When writing a C function I might start out with a crisp definition in my head ("this function saves the reverse of the list seen so far in its second argument") so that I can rely on that definition even when the implementation isn't yet complete.
That should happen naturally, if you implement a compiler to native code. A "call" instruction is just a "goto/branch/jump" with some extra stack fiddling.
Also, I don't think pure functions are so easy mentally either. Try to understand "call with current continuation". ;)
Most programming I learned was imperative. As I wrote the code, I imagined the execution in my head. This led to a problem where when I was halfway through a function, and it referred to itself, my brain would segfault. How could something I was not yet done writing refer to itself? I hadn't finished yet, so my brain could not comprehend what such a reference would mean.
It was also difficult because I wanted to think of functions as nice neat pieces of code that would take some data, do it's thing, and return a value. I could mentally inline a function call without much effort.
But when recursion is introduced, the floor drops out of my mental inlining. Suddenly my mental effort for such things becomes huge. For me anyway. My brain doesn't like to float around in abstraction land for long, it needs to periodically be anchored in the concrete. Otherwise I quickly lose my sense of direction and orientation... I lose my context.
Declarative languages actually make these easier, for me, because I'm not mentally executing a recipe as I write. I am giving a piece-wise description of what something is. So there is no mental tracing.
I expect the a-ha moment for recursion is different for everyone. But just showing recursion in many different forms would probably help. For example, show fib sequence generation where instead of the function calling itself, each function calls a uniquely named function... such that you concretely demonstrate building the first 5 or so numbers in the sequence...
Then show the similarity of the functions, show what the computer has to keep track of with the nested function calls, and step by step work your way to straight recursion.
Show it in BASIC with GOTO statements.
Finding as many different ways to concretely demonstrate an abstract concept will help reach more people.