In order to understand recursion, you must first understand recursion.
Nerdy Proverb
I’d been planning to do a little writeup on recursion and iteration to wrap up the mini series on Lambda Calculus, but the video below from John Philip Jones does a far better job than I could, with a lovely clear visual representation of why recursion can cause problems (i.e. stack-frames filling up).
Highly recommended if you’re new to this kind of thing.
If you don’t want to watch the video…
The short answer is that a recursive function is a function that calls itself. An example of this written (imperfectly) in sentence form might be “The sum of the numbers 1 to 5 is equal to 1 plus the sum of the remaining numbers.” To calclate the last part of this instruction we need to start again at the beginning of the instruction definition, replacing 1 and 5 with the numbers 2 to 5, and so on – the operation is calling itself within itself.
An iterative function repeatedly performs an operation on some information until a condition is met. You could think of your decision-making process in a running race as a kind of iteration: “Have you have passed the finish line? If so, stop and cheer. If not, run ten more steps. Repeat.”
These seem quite similar. One key difference is that in the iterative example you can forget what happened in previous iterations as long you know “position”, while in the recursive example you need to hold the results of every step in the chain open until you get to the final number, at which point all the previous numbers can be added together. This quickly comes to require more memory than iteration does. The point at which you run out of memory to hold new numbers is the moment of stack overflow.