Agreed about recursion being taught the wrong way. Recursion is implicitly fundamental to learning basic arithmetic (what is 5? it's just (1 + (1 + (1 + (1 + (1 + 0))))). Reasoning by induction is just recursion. I think children have a recursive intuition for counting (at least from watching my 3 year old) that quickly gets squashed when they start learning 'math' in school.