Hi, sorry if this has been talked about in the stream, but I'm quite behind in the episodes.
Some years ago, I had a course of intro to programming in C, where we had to do an assignment without using iteration, in order to practice another skill we had been taught. It just ocurred to me that I could do what I wanted by calling main() withing itself, something which we hadn't covered in the classes. So later, the teacher assistant told me that using recursion was a very dangerous thing, because you could burn your RAM by using it. The reason for that, he explained in sort of simple terms as we were just starting to program, with no prior knowledge, but he basically said that you piled up the function lots of times in memory, and then when the loop breaks, it very rapidly goes through all of the functions, and it can heat up and burn the memory.
So, my question is, firstly, can your really burn your memory by using recursion?
And, most importantly, is there ever any reason to use recursion over iteration? Does it have any uses that can only be done by using recursion? Again, sorry if this has been covered in stream, but my schedule isn't currently allowing me to catch up...
thanks!
Some years ago, I had a course of intro to programming in C, where we had to do an assignment without using iteration, in order to practice another skill we had been taught. It just ocurred to me that I could do what I wanted by calling main() withing itself, something which we hadn't covered in the classes. So later, the teacher assistant told me that using recursion was a very dangerous thing, because you could burn your RAM by using it. The reason for that, he explained in sort of simple terms as we were just starting to program, with no prior knowledge, but he basically said that you piled up the function lots of times in memory, and then when the loop breaks, it very rapidly goes through all of the functions, and it can heat up and burn the memory.
So, my question is, firstly, can your really burn your memory by using recursion?
And, most importantly, is there ever any reason to use recursion over iteration? Does it have any uses that can only be done by using recursion? Again, sorry if this has been covered in stream, but my schedule isn't currently allowing me to catch up...
thanks!
You really can not damage memory by executing any code including recursion on any modern machine. And by "modern" I mean anything that is build in last 20 or more years. Unless, of course, your motherboard is defective (but that is different story). Maybe on some very old machines this was possible, but not anymore.
Recursion from perspective of CPU is just calling a lot of functions and returning from them. If that would burn memory, then any decent AAA+ game would burn everyone's memory :) Because they created by large game engines, which call a lot of functions.
Any recursion can be rewritten using iterative algorithm. Sometimes you'll need to use additional memory for that, but it is always possible. In simple cases like calculating factorial or Fibonacci numbers it is trivial to change recursion to iteration. But if you are using recursion that requires to store a lot of state like walking complex graph structure, or some weird sorting then often you'll need to allocate some memory.
Advantage of using recursion is that current programming languages offer to do that will less code, your code looks simpler if you use recursion and you don't need to write much of it. If you need to manage additional memory for your state using iterative algorithm, that's a bit more code (but usually not a lot).
There is one advantage for iterative algorithm that recursive one doesn't have - you can control how much memory you actually use, and can return failure or display error to user if you start using too much of memory. For native code that uses recursion, once you run out of stack space, your code will crash - operating system will throw exception/signal you could catch it, but it is not safe to handle it. Here's a post from Raymond Chen on this topic. Managed languages (Java, C#, etc..) can handle out of stack space exceptions more safely.
Recursion from perspective of CPU is just calling a lot of functions and returning from them. If that would burn memory, then any decent AAA+ game would burn everyone's memory :) Because they created by large game engines, which call a lot of functions.
Any recursion can be rewritten using iterative algorithm. Sometimes you'll need to use additional memory for that, but it is always possible. In simple cases like calculating factorial or Fibonacci numbers it is trivial to change recursion to iteration. But if you are using recursion that requires to store a lot of state like walking complex graph structure, or some weird sorting then often you'll need to allocate some memory.
Advantage of using recursion is that current programming languages offer to do that will less code, your code looks simpler if you use recursion and you don't need to write much of it. If you need to manage additional memory for your state using iterative algorithm, that's a bit more code (but usually not a lot).
There is one advantage for iterative algorithm that recursive one doesn't have - you can control how much memory you actually use, and can return failure or display error to user if you start using too much of memory. For native code that uses recursion, once you run out of stack space, your code will crash - operating system will throw exception/signal you could catch it, but it is not safe to handle it. Here's a post from Raymond Chen on this topic. Managed languages (Java, C#, etc..) can handle out of stack space exceptions more safely.
Edited by Mārtiņš Možeiko
on
Huitzilopochtli
The reason for that, he explained in sort of simple terms as we were just starting to program, with no prior knowledge, but he basically said that you piled up the function lots of times in memory, and then when the loop breaks, it very rapidly goes through all of the functions, and it can heat up and burn the memory.
That is utter rubbish. Is it possible that this is a metaphor? We do speak in terms of "burning through RAM", meaning using it up quickly.
In a multi-threaded environment, stacks can be quite small, and you may want to avoid recursion there. Also, limiting the use of recursion can be more cache-efficient; as your call hierarchy gets deeper, stack frames can be ejected from cache.
Huitzilopochtli
And, most importantly, is there ever any reason to use recursion over iteration? Does it have any uses that can only be done by using recursion?
You can always simulate recursion by using an explicit stack, however it's not always convenient. Some graph traversal algorithms, for example, are naturally recursive, and turning them into an "iteration with explicit stack" implementation is nontrivial.
There's really no difference between recursion and non-recursion other than the fact that stack management for locals is built into the language, and stack management for non-locals isn't. Making a recursive function non-recursive is just an exercise in explicitly writing the stack management code that the compiler was writing for you.
- Casey
- Casey
Aah, okay, I understand. Thanks for all your answers!