When I first learned Assembly Language, I had a fear of blowing up the stack. Remember, back in the 8-bit microcomputer era that memory space was tight, maybe only part of 64K. A stack would have 1K of storage, if that. I think the stack size on my TRS-80 was 256 bytes. (An address was only two bytes wide.) This limitation meant that pushing too much data on the stack would blow up the computer.
\n
\nNothing would explode, of course; I love hyperbole. Even so, I was leery of pushing too much data on the stack. So, while I understood the concept of recursion, I remained fearful that if a function called itself too often the stack would explode and I’d be sweeping up bits from the floor behind the computer.<\/p>\n
That never happened.<\/p>\n
It never happened because I was careful. But when I obtained my first 16-bit computer, I harbored no fear of blowing up the stack. In fact, I must have at some point coded a program like the following just to test how robust the stack can be:<\/p>\n
\r\n#include <stdio.h>\r\n\r\nvoid recurse(int i)\r\n{\r\n printf(\"%d\\n\",i);\r\n recurse(i+1);\r\n}\r\n\r\nint main()\r\n{\r\n recurse(0);\r\n\r\n return 0;\r\n}<\/pre>\nThis code provides an example of recursion. A poor example. The problem is that recursion doesn’t ever unwind: The function keeps calling itself until no more return addresses can be pushed onto the stack. Boom.<\/p>\n
The code compiles cleanly under gcc<\/em>, but clang<\/em> issues an “infinite recursion” warning. Regardless, a program is built.<\/p>\nHere is the tail end of output from a sample run:<\/p>\n
261834\r\n261835\r\n261836\r\n261837\r\n261838\r\nSegmentation fault (core dumped)<\/pre>\nOn my test computer, the function called itself 261,838 times before the stack could hold no more values. The “Segmentation fault” means that an attempt was made to access memory outside of the program’s allocated space (the “segment”). The core is dumped. The program stops.<\/p>\n
Other computers show different final values in the output, based on allocated stack space.<\/p>\n
So how much stack space is there? To find out in Linux, use the ulimit -s<\/em> command at the terminal:<\/p>\n$ ulimit -s\r\n8192<\/pre>\nThe -s<\/code> option outputs the stack size in kilobytes. (Use ulimit -a<\/code> to see all limits set for the current terminal configuration.)<\/p>\nAccording to the output, the current terminal has a stack size of 8192K, or 8,388,608 bytes, which is a lot of storage.<\/p>\n
It’s possible to use ulimit<\/em> to change the stack size. For example:<\/p>\nulimit -s 16384<\/pre>\nWhen I made this change and ran the program again, here are the last few lines of output:<\/p>\n
524090\r\n524091\r\n524092\r\n524093\r\nSegmentation fault (core dumped)<\/pre>\nObviously, the result is larger because the stack is larger and it took longer for recursion to explode.<\/p>\n
By the way, changing the stack size affects only the current terminal configuration and its programs or “children.” Permanent changes to the stack size are made in the \/etc\/security\/limits.conf<\/code> file.<\/p>\nRecursion is something you can safely employ in your code — as long as it successfully unwinds itself. If necessary, you can allocate more stack storage, but I would be interested in see what type of program would merit such an increase.<\/p>\n","protected":false},"excerpt":{"rendered":"
How many times can a function call itself before implosion? Continue reading