The easiest way to learn recursion imo is by limiting the domain. For example, we have a thing called a number: x how do we indicate the next number? Well we

The easiest way to learn recursion imo is by limiting the domain. For example, we have a thing called a number: x how do we indicate the next number? Well we need a new symbol to distinguish one number from another. Lets use a marker called prime: x, x` Great, now we have two numbers. But let's get a third number. How could we indicate that? Well we could introduce a totally new symbol, like a 'q'. x, x`, q. Well that works. but we seem to have just arbitrarily chosen q. There's no immediate obvious aspect of q that lets us know what the next symbol should be if someone asked us to add yet another number. We have three distinct number things but no clear unified way to proceed... But wait, before we took some number x and added a prime to it: x->x` which got us a separate symbol, aka a different number. What if we just do that again but this time with our second number: x`->x`` Great. Now we have three numbers, and we can always use the same rule "add a prime mark" to generate the next symbol, so long as we input the last symbol into our rule: x, x`, x`` We also wind up with neat little equivalences: x`` = x`, x = x, x, x or if our prime operation is a function: x`` = prime(prime(x)) = prime(x`) = x`` so x``, is just the result of prime of prime of x. So on and so forth until infinity. What makes recursion harder to work with in CS is that, unlike summation, you can't go to infinity--you need to terminate the operation eventually if you actually want it to do anything. Because of this and because of the fact that our inputs are not little units like numbers but are usually data structures which require more rules to recurse over, recursion in CS is tightly and innately coupled with pattern matching and the notion of defining bottoms or terminating cases which is not the case for operations in mathematics where we do not care about terminating because it just encodes the rule and isn't actually meant to do anything, and when we do need to do something with it we limit it by deciding when to stop (so I guess some neuron firing is the bottom/terminating case for human operations?). Recursion in CS is also additionally difficult because we have to worry about how the computer stores the results of each recursive application and feeds them back whereas, kind of like a high level language, our brain just manages all that for us when we do math. Also note that we take huge shortcuts with things like Arabic numerals--which are an incredible advance in efficiency but probably obfuscate the recursive roots of mathematics for most learners (e.g. you just learn that some symbol 2 and some symbol 2 is another symbol 4 and not that these are encapsulating successive applications of the same rule over a set of arbitrary symbols--I mean, your brain knows this deep down--that's why it works, but it makes it difficult to immediately comprehend that it is in fact recursive unless people have pointed this out to you--at least that was my experience; I may have just had bad teachers).