Comment by arcturus17
4 years ago
In what sense is recursion a form of looping?
I'm thinking of the memory model for each - one mutates some variables (at least some sort of index, unless you're doing an infinite loop) in a single frame, while the other accumulates function calls and stack frames until you bottom out, then return values are "folded" back up.
Semantically, from a caller's perspective, they can achieve the exact same thing, but aside from that they seem radically different to me - is there anything else that could lead us to say that recursion is a form of looping?
> In computer science, a loop is a programming structure that repeats a sequence of instructions until a specific condition is met.
That's the general definition at least I've always been most aware of. I don't want to claim it is the most common one, cause I don't really have numbers and who is the authority on comp-sci definitons? But I do feel it is at least a somewhat common academic definition for looping.
That would mean that recursion is a form of looping. The distinction between recursion and imperative loops would then be a matter of implementation and exposed programmer interface. Similarly like others have said, goto's can also be used to implement similar loops.
And in that regard, there are variants of recursion as well, such as tail-call recursion which has a similar memory model as what you described and differs only to an imperative loop in the programming interface it exposes.
There's no denying that from that definition they are the same. It's just after you've debugged enough loops and recursions you can't help but think they are quite different!
Well, I don't mean they are the same, they're just different kinds of looping constructs.
Like what you call a loop isn't a loop, its actually a for-loop, or its a while-loop, or a for-each loop, or its an iterator loop, and similarly recursion is just a recursive loop.
At least that's the common taxonomy I know off. So all these are loops, and the ones that involve mutation for the condition to kick in are further grouped as imperative loops.