stack overflow
-
Hello, I have two questions about the stack. 1st)In MS visual studio the stack is 1MB as far as I now. I found that using a recursive function the stack overflows at depth ~4900. Why does this happen? 2nd)If someone has a linked list with thousand of elements how he can reach the whole list using a recursive function? thanks.
-
Hello, I have two questions about the stack. 1st)In MS visual studio the stack is 1MB as far as I now. I found that using a recursive function the stack overflows at depth ~4900. Why does this happen? 2nd)If someone has a linked list with thousand of elements how he can reach the whole list using a recursive function? thanks.
Lord_Vader wrote:
1st)In MS visual studio the stack is 1MB as far as I now.
Lord_Vader wrote:
Why does this happen?
When you reach the limit, regardless of what that is, you get the overflow error. What is so hard to understand about that?
Lord_Vader wrote:
2nd)If someone has a linked list with thousand of elements how he can reach the whole list using a recursive function?
Why would you want to do that?
-
Lord_Vader wrote:
1st)In MS visual studio the stack is 1MB as far as I now.
Lord_Vader wrote:
Why does this happen?
When you reach the limit, regardless of what that is, you get the overflow error. What is so hard to understand about that?
Lord_Vader wrote:
2nd)If someone has a linked list with thousand of elements how he can reach the whole list using a recursive function?
Why would you want to do that?
1st)Its not hard to understand that. But I want someone to explain specifically what happens, for example how much stack memory one function call consumes why... 2nd)Because I have a linked list with thousand elements and I wondering if it is possible to go through it using recursive functions.
-
1st)Its not hard to understand that. But I want someone to explain specifically what happens, for example how much stack memory one function call consumes why... 2nd)Because I have a linked list with thousand elements and I wondering if it is possible to go through it using recursive functions.
Why would you iterate through a linked list with a recursive function? You already figured out the answer to your question: it is not possible unless you increase the stack size, since you seem to top at around 4900. Just call the next pointer until you reach the end of the list. It only takes a single function.
-
Hello, I have two questions about the stack. 1st)In MS visual studio the stack is 1MB as far as I now. I found that using a recursive function the stack overflows at depth ~4900. Why does this happen? 2nd)If someone has a linked list with thousand of elements how he can reach the whole list using a recursive function? thanks.
In general, using recursion in pure imperative languages such as C++ is a bad idea - it can lead to stack overflows and also tends to be slower than iteration. Functional languages such as OCaml are able to internaly convert recursion (at least tail recursion) to iteration and then it is OK to use recursion.
-
Why would you iterate through a linked list with a recursive function? You already figured out the answer to your question: it is not possible unless you increase the stack size, since you seem to top at around 4900. Just call the next pointer until you reach the end of the list. It only takes a single function.
Ok thanks,I was going to do that, but I posted mainly to learn the details behind a functions call..
-
1st)Its not hard to understand that. But I want someone to explain specifically what happens, for example how much stack memory one function call consumes why... 2nd)Because I have a linked list with thousand elements and I wondering if it is possible to go through it using recursive functions.
Stack memory is generally required for the function call information (return values and return address), as well as for the automatic variables in the function being called. One function may consume only 32 bytes of stack while another consumes more than 8KB of stack. It is possible to recursively iterate over any size list... Given you have enough stack space and your environment supports it. Realistically, this depends on (1) how much stack is consumed by the recursive function, (2) how many elements are in the list, and (3) how much free stack space you have remaining at the time you start recursion (just because you have 1MB of stack by default in Win32, that does not mean that by the time your function is first called that you will have much of it left). Iteration is generally better done using loops instead of recursion. It is also easier to debug, because you can more easily break at a certain loop counter than a certain recursion depth. Peace!
-=- James
Please rate this message - let me know if I helped or not! * * *If you think it costs a lot to do it right, just wait until you find out how much it costs to do it wrong!
Avoid driving a vehicle taller than you and remember that Professional Driver on Closed Course does not mean your Dumb Ass on a Public Road!
See DeleteFXPFiles -
In general, using recursion in pure imperative languages such as C++ is a bad idea - it can lead to stack overflows and also tends to be slower than iteration. Functional languages such as OCaml are able to internaly convert recursion (at least tail recursion) to iteration and then it is OK to use recursion.
Well, I think there are definitely some very good uses of recursion in C++ such as generically printing out the data in an XML DOM tree, where there is no absolutely defined node structure. I'm not sure how you'd go about doing that otherwise. That said, DOM tree hierarchies typically don't go down that many levels -- that would be both a memory usage and usability nightmare.
-
Stack memory is generally required for the function call information (return values and return address), as well as for the automatic variables in the function being called. One function may consume only 32 bytes of stack while another consumes more than 8KB of stack. It is possible to recursively iterate over any size list... Given you have enough stack space and your environment supports it. Realistically, this depends on (1) how much stack is consumed by the recursive function, (2) how many elements are in the list, and (3) how much free stack space you have remaining at the time you start recursion (just because you have 1MB of stack by default in Win32, that does not mean that by the time your function is first called that you will have much of it left). Iteration is generally better done using loops instead of recursion. It is also easier to debug, because you can more easily break at a certain loop counter than a certain recursion depth. Peace!
-=- James
Please rate this message - let me know if I helped or not! * * *If you think it costs a lot to do it right, just wait until you find out how much it costs to do it wrong!
Avoid driving a vehicle taller than you and remember that Professional Driver on Closed Course does not mean your Dumb Ass on a Public Road!
See DeleteFXPFilesThanks, Here is another one. I additionally have a bin tree with many thousands of elements. I use recursive functions to walk through the leafs because its more intuitive. Will it be faster if I use loops instead?
-
Thanks, Here is another one. I additionally have a bin tree with many thousands of elements. I use recursive functions to walk through the leafs because its more intuitive. Will it be faster if I use loops instead?
It may be faster to use loops, depending on the setup required for the recursive function call (stack frame setup, construction/destruction of any local objects, exception handling setup if used, etc.). If your function uses poor coding habits, like using a
CStringinstead of a local buffer for simple formatting, using the loop will very likely be faster than recursion, because you can eliminate the overhead of allocating/deallocating the memory for the string. (You may not notice a difference when only calling the function 100 or so times, but when you start hitting the 1000+ ranges, you may.) A (well-balanced) binary tree is likely to have less recursive demand, whereas a list is a linear structure so your recursion level would be equal to the number of items in the list. Trees tend to have less depth when used/populated correctly. Peace!-=- James
Please rate this message - let me know if I helped or not! * * *If you think it costs a lot to do it right, just wait until you find out how much it costs to do it wrong!
Avoid driving a vehicle taller than you and remember that Professional Driver on Closed Course does not mean your Dumb Ass on a Public Road!
See DeleteFXPFiles -
Stack memory is generally required for the function call information (return values and return address), as well as for the automatic variables in the function being called. One function may consume only 32 bytes of stack while another consumes more than 8KB of stack. It is possible to recursively iterate over any size list... Given you have enough stack space and your environment supports it. Realistically, this depends on (1) how much stack is consumed by the recursive function, (2) how many elements are in the list, and (3) how much free stack space you have remaining at the time you start recursion (just because you have 1MB of stack by default in Win32, that does not mean that by the time your function is first called that you will have much of it left). Iteration is generally better done using loops instead of recursion. It is also easier to debug, because you can more easily break at a certain loop counter than a certain recursion depth. Peace!
-=- James
Please rate this message - let me know if I helped or not! * * *If you think it costs a lot to do it right, just wait until you find out how much it costs to do it wrong!
Avoid driving a vehicle taller than you and remember that Professional Driver on Closed Course does not mean your Dumb Ass on a Public Road!
See DeleteFXPFilesEach function call in a recursive loop consumes stack space. If you're passing parameters, that consumes even more stack space. I thought the max stack space for a given app was limited to 64k... Of course, I'm old, so it may have changed since I last checked it out. :)
"Why don't you tie a kerosene-soaked rag around your ankles so the ants won't climb up and eat your candy ass..." - Dale Earnhardt, 1997
-----
"...the staggering layers of obscenity in your statement make it a work of art on so many levels." - Jason Jystad, 10/26/2001 -
It may be faster to use loops, depending on the setup required for the recursive function call (stack frame setup, construction/destruction of any local objects, exception handling setup if used, etc.). If your function uses poor coding habits, like using a
CStringinstead of a local buffer for simple formatting, using the loop will very likely be faster than recursion, because you can eliminate the overhead of allocating/deallocating the memory for the string. (You may not notice a difference when only calling the function 100 or so times, but when you start hitting the 1000+ ranges, you may.) A (well-balanced) binary tree is likely to have less recursive demand, whereas a list is a linear structure so your recursion level would be equal to the number of items in the list. Trees tend to have less depth when used/populated correctly. Peace!-=- James
Please rate this message - let me know if I helped or not! * * *If you think it costs a lot to do it right, just wait until you find out how much it costs to do it wrong!
Avoid driving a vehicle taller than you and remember that Professional Driver on Closed Course does not mean your Dumb Ass on a Public Road!
See DeleteFXPFilesThanks,Specifically I am working on a graphics algorithm which uses a binary tree to draw triangles(which are the leafs) on the screen. Now if you consider that I would like to have ~60000 leafs displayed every frame using a recursive function, this is quite cumbersome.Additionally the tree may not be so balanced, but the maximum depth of the tree wont be larger than ~14.Thats why I asked.
