r/computerscience • • May 03 '21

When to use recursion?

So I am getting a little bit ahead of myself here, I'm still in high school and I'm entering (hopefully) AP Java next year (or computer science A). One of the topic there is recursion, and I've done a little digging, and I find recursion really interesting, but what I was wondering was when do programmers use recursion? Like, can a for loop just do the job or does it help with computer memory and processing, when is the best time to use recursion?

141 Upvotes

80 comments sorted by

View all comments

Show parent comments

1

u/[deleted] May 04 '21

https://en.wikipedia.org/wiki/Subroutine#Jump_to_subroutine

This is what I mean. I learned assembly on the 8086. My professor expounded upon how monumental this invention was. Before the specialized "Subroutine" instructions, they were literally just divisions in your code separated by regular jumps.

1

u/RobotJonesDad May 04 '21

If you go up to the history section of that page, you will see that the concept was conceived during work on ENIAC. And Turing had discussed subroutines in a 1945 paper, including the concept of a return stack.

That's why I said there wasn't a before in the practical sense. The concept is the key thing ingredient. The implementation details are device specific. Probably the key feature is that you can call the code from multiple places and be able to return back to where you come from.

I think your professor must have been making a subtle point. The structure of the code is orthogonal to the subroutine concept. For example, many RISC CPUs don't bother with a jump instruction that manipulates the stack. They leave that 100% up to the code.

The key in the above discussion of loops vs recursive code comes down to the concept of calling a subroutine from inside itself - ie, an operation with its own execution context that you can return from. In a loop, you execute code repeatedly, but in the same context with no context stacking.