Personal computing discussed
Moderators: renee, SecretSquirrel, just brew it!
Igor_Kavinski wrote:Even though I don't understand recursion (how the computer does it), I heard someone say that it helps to visualize a problem in terms of stuff being pushed onto a stack and once the base condition is reached, the computer will automatically start popping stuff out of the stack in LIFO order and doing whatever needs to be done with that output (treating it as an input for some other function for instance). I could be wrong though. Corrections are welcome.
just brew it! wrote:I actually dislike using Fibonacci (and factorial) examples to illustrate recursion. Not because they don't illustrate recursion, but because in the real world, they tend to result in excessively deep recursion which will typically cause a stack overflow error unless the inputs are small. In the real world, these would be implemented with an explicit loop rather than recursion, to avoid this issue.
just brew it! wrote:I actually dislike using Fibonacci (and factorial) examples to illustrate recursion. Not because they don't illustrate recursion, but because in the real world, they tend to result in excessively deep recursion which will typically cause a stack overflow error unless the inputs are small.
Igor_Kavinski wrote:just brew it! wrote:I actually dislike using Fibonacci (and factorial) examples to illustrate recursion. Not because they don't illustrate recursion, but because in the real world, they tend to result in excessively deep recursion which will typically cause a stack overflow error unless the inputs are small.
I have always wanted to know this. How does directory recursion work without overflowing the stack, as the directory can have n levels of depth?
dragontamer5788 wrote:The OS does a bit of virtual-memory magic to move the stack around physically, while the programmer only has to think of logical code addresses. But ultimately, the OS can move the stack around (even to the hard drive temporarily with "swap"). And the OS is very good at moving memory around and using it efficiently, be it Linux or Windows.
Igor_Kavinski wrote:dragontamer5788 wrote:The OS does a bit of virtual-memory magic to move the stack around physically, while the programmer only has to think of logical code addresses. But ultimately, the OS can move the stack around (even to the hard drive temporarily with "swap"). And the OS is very good at moving memory around and using it efficiently, be it Linux or Windows.
The stack in a function is the register space and the stack outside the function (global variables) is the heap, correct?
dragontamer5788 wrote:No. C doesn't have registers. Registers are an assembly thing and you can almost completely ignore them in higher level languages. (Exceptions: volatile memory locations, obscure threading issues, memory barriers. The stuff of experts. Beginners simply will not come across these situations).
--------
Virtual memory in C / Windows / Linux is just a giant array that you can access in the program. The stack is somewhere in memory, you don't care where it is exactly. The C compiler works the stack to create local variables inside of a function.
The heap is completely different (and has lots of meanings). I assume you're talking about the malloc / free heap, which is just... the memory locations where malloc and free operate. When you request malloc(), you get data from the so called "heap". And when you say "free", you tell the memory-manager that you aren't using that memory location anymore and that they can recycle it into another malloc() call later.
Igor_Kavinski wrote:dragontamer5788 wrote:No. C doesn't have registers. Registers are an assembly thing and you can almost completely ignore them in higher level languages. (Exceptions: volatile memory locations, obscure threading issues, memory barriers. The stuff of experts. Beginners simply will not come across these situations).
--------
Virtual memory in C / Windows / Linux is just a giant array that you can access in the program. The stack is somewhere in memory, you don't care where it is exactly. The C compiler works the stack to create local variables inside of a function.
The heap is completely different (and has lots of meanings). I assume you're talking about the malloc / free heap, which is just... the memory locations where malloc and free operate. When you request malloc(), you get data from the so called "heap". And when you say "free", you tell the memory-manager that you aren't using that memory location anymore and that they can recycle it into another malloc() call later.
I was under the impression that local variables meant faster access to data and global variables meant higher latencies.
I've made a lot of global variables in my C programs for the ease of accessing them from any function without having to pass values but if my code were reviewed, it would be declared a big heap of stink coz you are not supposed to go global unless absolutely necessary.
dragontamer5788 wrote:Igor_Kavinski wrote:I have always wanted to know this. How does directory recursion work without overflowing the stack, as the directory can have n levels of depth?
Because we have 8GB of RAM on most machines these days, the stack won't really run out of memory until you fill that up.
The OS does a bit of virtual-memory magic to move the stack around physically, while the programmer only has to think of logical code addresses. But ultimately, the OS can move the stack around (even to the hard drive temporarily with "swap"). And the OS is very good at moving memory around and using it efficiently, be it Linux or Windows.
Igor_Kavinski wrote:The stack in a function is the register space and the stack outside the function (global variables) is the heap, correct?
Redocbew wrote:It depends on the language also. In C, that sounds correct. Variables declared within a function are stored on the stack while globals are stored on the heap. Additional memory you request from the OS typically comes from the heap as well. On what device that data is physically being stored(main memory vs hard drives vs toaster ovens) is an implementation detail. Compare that to a language like Python which does memory management for you and things may be different. In all of the Python apps I've written over the past few months my data could be on the stack, or the heap, or some combination of both. I've got no idea.
That's not to say the inner workings of a high level language like Python are unimportant. It may be required of you to know that stuff in order for your application to behave as expected, but it's not necessarily required by the language just to get things up and running.
Igor_Kavinski wrote:I was under the impression that local variables meant faster access to data and global variables meant higher latencies. I've made a lot of global variables in my C programs for the ease of accessing them from any function without having to pass values but if my code were reviewed, it would be declared a big heap of stink coz you are not supposed to go global unless absolutely necessary.