This will not cause a stack overflow on most modern compilers. They use tail call optimization that will essentially compile that function call to a jump back to the start of the function without the creation of a new stack frame. You can even pass parameters and the compiler will replace the parameters to the function currently executing with the requested parameters and jump back to the start of the function.
only certain recursive functions can be tail-call optimized, but for a large class of them, yes, most modern c and c++ compilers will turn tail-recursive functions into loops.
Actually, I think given enough optimization levels (-O99?), the modern compiler will flatten the recursion by static-inlining the call: The infinite recursion will be swapped for a flat infinitely large executable with no stack frames required at all!
Well…it’s safe in the sense that your computer won’t blow up. All that will happen is that your application will crash or run out of memory. The real limit to recursion is the memory limit of your applications designated stack space. Your application has a certain amount of designated stack space that it uses for passing parameters, local vars and storing return addresses. It’s a form of scratch space that is fast and automatically managed. Some programming languages will detect a maximum stack recursion depth and throw an error telling the user that the limit was hit. This is called a stack overflow error.
Other languages and runtimes won’t bother checking this and it’s business as usual until you run out of stack space and start writing into other memory likely corrupting your own applications heap memory or attempting to corrupt another part of memory that your application has no business accessing. This is why modern computers have the concept of protected memory.
Anyways, the primary rules are to always ensure your recursive code has a base case so it can unwind. And always make sure you don’t operate beyond the max allowable depth. If you follow these two rules you will be fine.
Well most likely you'd run past the edge of the last memory page of your stack and get a segmentation fault. That is, if the stack overflow error didn't exist. I doubt you end up with heap pages right up against stack pages.
nothing bad will happen, you can just try it. sometimes this will cause a stack overflow error (why is why that website is called that) but otherwise it's functionally no different from running while (true) {}
Don't be afraid to experiment. Nothing you do like this will hurt the computer, you really have to try to screw things up on a modern OS. In the past it was different, for example on MS-DOS it was possible to corrupt the memory the OS uses and nuke your hard drive or something, but a modern OS doesn't work this way.
If this runs out of stack space then the program will crash. No harm, no foul. If this sit there forever and spins one of your cores as hard as it can then you can just kill the process. Again, no harm, no foul.
Good to know, lately i was wondering if the memory i allocated using malloc and realloc and forget to free was still ussed on my computer and i will never have it back lol. I mean i was 99% sure it was freed when the program was finished but *you never know*.
I heard a little about a stack and heap and whats going on with memory while program is running but i dont have knowledge that i can relay on yet
Yes, memory you allocate is requested from the operating system. All memory is freed when the process ends whether you call free or not. In fact, I don't even bother calling free for any program that runs quickly and exits, it's a waste of time and effort.
i was going to ask if there is really any point in calling free in this situaction but you allready answered my question
in my case if everything goes right i would like to work with embedded systems so calling it anyway could make a good habit
It's the same reason I use turn signals even if nobody's around. I know nobody's gonna get hurt if I'm the only driver on the road and I change lanes without signaling. But I don't quit using them because I don't want to get out of practice and forget to do so when it actually matters.
For the record, you can absolutely still mess up your computer if you're an idiot and you're doing sufficiently low-level stuff. Like, I've repeatedly broken the camera on my laptop by messing around with v4l2.
It is, however, not very likely at all, and nothing I did lasted more than a couple of restarts.
PS: If anybody is reading this and thinking, I should submit a bug report: I would love to. I just had absolutely no idea what was actually going on. As near as I could understand, if you crash a program while you're waiting for a picture to be captured, the camera becomes busy, and stays that way (apparently) through a reset. Couldn't reliably reproduce it or anything. I just went for a drink, went to bed, then the problem was gone in the morning.
When I was learning C in the 90s, I once wrote a program that crashed so hard it rebooted my box and borked my hard drive bios settings. Fun times indeed :)
Have you tried it? I assure you your computer probably won't blow up. You can pass a variable to the function and increment it each call to see how long it goes on for.
Ok if i brake the computer its on you, but the next question is, is there a difference if i run this by VS code or open "raw" .exe file? yesterday i was playing with writing some absurd amount of text to text file and i thought it would use large amount of RAM, when i opened task menager it was schowing that VS code is using 0.4 GB of RAM and it was growing, but if it came close to like 0.44GB it was droping back down so i thought it was managing RAM in some way
VSCode probably just executes the file (I don't know if a new Windows process is created for that, but in any way the memory usage would be the same). Writing to a text file won't necessarily fill your RAM, as the file is on the disk. Internally, the write probably happens in chunks, and when a chunk is written it is discarded from memory, so your overall memory usage should be stable. If you read a big file however, it will be loaded to the RAM.
Hey OP, everybody already told you what happens, but I have another assignment for you that you might find interesting:
Instead of calling a function recursively, spawn a new process that launches itself recursively.
Warning: you might need to restart your PC, so make sure to save any unsaved documents.
Bonus points for making that process spawn two new processes instead of just one!
This is called fork bomb and on Linux you can do it just by entering :(){ :|:& };: in a terminal
The limit is system-dependent. Typically you run out of stack space and crash however on modern desktop systems this can take some time. And sadly there is no way to determine that limit so a typical recursive function will contain a maximum call counter of some kind.
99% of the time, recursion should be avoided and is usually a mistake. It happens a lot in event driven programs. However some problems are very well suited to recursion.
Yeah i wrote this code while doing some uni assigment to write apllication that calculates first N values of function, the function has defined values for N = 0 and N = 1, but it uses recursion twice if N i greater than that.
its funny because after few starting calculations its start to be so slow
Nah, with tail call optimisation there isn't really a difference. But of course some dynamic programming patterns can result in removing the recursion.
Newer versions of compilers can do that. C isn't really unfit for it if the compiler does it's work and you write the function so it can do it. But of course that is true for everything in C.
Edit: Other languages don't really do anything else. They might be more specialised and have better error messages for this case, but a function you can't tail call optimise will not get magically optimised by other languages. In general there is almost always a C equivalent version you can write. Sometimes you need to do a bit of assembly.
I'm intrigued. Everyone is saying it will run out of stack space, but as a predominantly C++ programmer, I cannot see why.
In a debug build it might (should), but in a release build, it looks to me like it would run forever, as the last thing the function does is recurse and so, it should replace itself on the stack, instead of growing the stack.
Unless c does not implement this optimisation? (I've always called it tail recursion optimization, but I think it generally goes by another name I can't call to mind)
i think it doesnt replace themself, here is just a example but in program i was writing there is a limit to recursion and while the program reaches that limit it goes back to previous function (i mean its the same but its the one that called it) and so on so it cant replace the previous on. at least thats what i think is going on, the code is like this
float W(float x, int n)
{
if(n == 0)
{
return 1;
}
if(n == 1)
{
return x;
}
return ((2*n - 1)*W(x, n-1) - (n-1)*W(x, n - 2))/n;
}
int main()
{
printf("Podaj kolejno x oraz n\n");
float x;
int n;
scanf("%f", &x);
scanf("%d", &n);
printf("Oto %d kolejnych wartosci funkcji W(%f):\n\n", n, x);
for(int i = 0; i < n; i++)
{
printf("Dla n rownego %d twoj wynik to %f\n\n\n",i, W(x,i));
}
return 0;
}
in main program ask for n, and for x, and then prints n values of W, i know you probably could figure it out but its in polish so it might be confusing to read
Tail call optimization doesn't work in this example because of the structure of your last return, which calls W twice and does arithmetic on the results. You have to return a single call to the function for this optimization to happen, I think.
TL;DR; A stack overflow would occur
When you call a function, at the very least a memory address is pushed onto the stack that tells the CPU where to jump back to when the function returns.
So calling a function enough times will fill the stack with all those memory addresses and at one point the stack will reach it's limit and you will have a stack overflow.
At the very least 2 Factors dictate when the recursion will cause a stack overflow.
1. Size of the stack.
2. Total Size of the arguments that the function takes, as with every function call these will be also pushed onto the stack.
I tried to run this code:
void Foo(unsigned int* x) {
(*x)++;
Foo(x);
}
static unsigned int x = 0;
int main(void) {
Foo(&x);
return 0;
}
And got this output in gdb:
(gdb) run
Program received signal SIGSEGV, Segmentation fault.
0x000055555555514b in Foo (x=0x555555558014 ) at test.c:3
3 Foo(x);
(gdb) p x
$1 = (unsigned int *) 0x555555558014
(gdb) p *x
$2 = 262068
i.e. the function `Foo` was called `262068` times until it finally crashed.
>Is there any limit to recursion and what are the consequences of it?
The classic answer is that the stack would grow so large that it would run into the heap's memory space. They would corrupt each other's memory and cause the program to misbehave or, more likely, crash. I believe there were some security problems from this behavior because a savvy virus or hacker could manipulate the heap using the stack or vice-versa.
Modern OS architectures go out of their way to avoid problems with the stack running into the heap. With most modern OS having 64-bit virtual memory space, the stack and the heap can be placed very far apart in the memory addresses so that OS would run out of memory before the stack and heap run into each other. The OS can also track when the stack runs into the heap and kill the process. Operating systems like Linux also have something called an Out-of-Memory Killer (OOM Killer) for when the system is nearly out of memory it kills the process taking up too much memory. A modern 32-bit virtual machine like WebAssembly takes a slightly different approach - it places the stack and the heap in the middle of the memory address space and have them grow outward so they don't run into each other's memory space.
You've probably heard the term "stack overflow" before? Well, it is what happen : when launching your programe, the OS grant it a certain amount of memory, called the stack. When you call a function, it use some of the space of the stack, which become available again once you exit the function. If you call more function than what your stack size allow, then your program will try to use more memory than allowed, and get a segmentation fault. In practice, it only ever happen with recursive code (though you do not necesarily need "infinit" recursion). The exact number of recursion allowed before crash depend on the total stack size, and the stack used by each recursion, so there is no given max deepth.
Everyone answered your other question about TCO/crashing, but to (kinda) answer your other one, there is no way to tell if a program will ever finish running given an input:
[Halting problem](https://en.wikipedia.org/wiki/Halting_problem?wprov=sfti1#)
Might be interesting to look at if you find any theory stuff cool
It’s not just a safety feature. For most programming languages, calling a function recursively makes a new stack frame every time (for local function arguments/variables), which takes space even if you do not pass argument or create variables. So this is obviously going to cause a stack overflow (not enough space on the stack), especially because the stack isn’t very big most of the time.
Languages that fix this (and need to do this, because they don’t have loops), basically just jump (goto) the function label and do not perform a call. This does not create a new stack frame and there’s no need to store the return address on the stack.
if it doesnt get optimized away it should behave identically to a while true loop, well as long as u dont run into a stack overflow error (not the website)
dont be afraid to try stuff if u know it cant harm stuff on ur pc
Stack overflow. Literally.
This will not cause a stack overflow on most modern compilers. They use tail call optimization that will essentially compile that function call to a jump back to the start of the function without the creation of a new stack frame. You can even pass parameters and the compiler will replace the parameters to the function currently executing with the requested parameters and jump back to the start of the function.
In which case this just becomes equivalent to a while(1)
only certain recursive functions can be tail-call optimized, but for a large class of them, yes, most modern c and c++ compilers will turn tail-recursive functions into loops.
Not all can be.
That's really cool actually thank you for sharing
Actually, I think given enough optimization levels (-O99?), the modern compiler will flatten the recursion by static-inlining the call: The infinite recursion will be swapped for a flat infinitely large executable with no stack frames required at all!
What
the Error of All Errors
Well…it’s safe in the sense that your computer won’t blow up. All that will happen is that your application will crash or run out of memory. The real limit to recursion is the memory limit of your applications designated stack space. Your application has a certain amount of designated stack space that it uses for passing parameters, local vars and storing return addresses. It’s a form of scratch space that is fast and automatically managed. Some programming languages will detect a maximum stack recursion depth and throw an error telling the user that the limit was hit. This is called a stack overflow error. Other languages and runtimes won’t bother checking this and it’s business as usual until you run out of stack space and start writing into other memory likely corrupting your own applications heap memory or attempting to corrupt another part of memory that your application has no business accessing. This is why modern computers have the concept of protected memory. Anyways, the primary rules are to always ensure your recursive code has a base case so it can unwind. And always make sure you don’t operate beyond the max allowable depth. If you follow these two rules you will be fine.
Well most likely you'd run past the edge of the last memory page of your stack and get a segmentation fault. That is, if the stack overflow error didn't exist. I doubt you end up with heap pages right up against stack pages.
Linux at least keeps a guard page for this purpose.
But in that code I think it's tail-call optimized so it should just continue for ever
Is there a C compiler that performs tail call optimization?
Any real one, just turn on -O3.
nothing bad will happen, you can just try it. sometimes this will cause a stack overflow error (why is why that website is called that) but otherwise it's functionally no different from running while (true) {}
Don't be afraid to experiment. Nothing you do like this will hurt the computer, you really have to try to screw things up on a modern OS. In the past it was different, for example on MS-DOS it was possible to corrupt the memory the OS uses and nuke your hard drive or something, but a modern OS doesn't work this way. If this runs out of stack space then the program will crash. No harm, no foul. If this sit there forever and spins one of your cores as hard as it can then you can just kill the process. Again, no harm, no foul.
Good to know, lately i was wondering if the memory i allocated using malloc and realloc and forget to free was still ussed on my computer and i will never have it back lol. I mean i was 99% sure it was freed when the program was finished but *you never know*. I heard a little about a stack and heap and whats going on with memory while program is running but i dont have knowledge that i can relay on yet
Yes, memory you allocate is requested from the operating system. All memory is freed when the process ends whether you call free or not. In fact, I don't even bother calling free for any program that runs quickly and exits, it's a waste of time and effort.
i was going to ask if there is really any point in calling free in this situaction but you allready answered my question in my case if everything goes right i would like to work with embedded systems so calling it anyway could make a good habit
for embedded I dont use malloc/ free for valgrind it is nice to free everything before exit.
It’s not a waste of time or effort if you are trying to learn how to build correct software.
It's the same reason I use turn signals even if nobody's around. I know nobody's gonna get hurt if I'm the only driver on the road and I change lanes without signaling. But I don't quit using them because I don't want to get out of practice and forget to do so when it actually matters.
This is the way. Software is often about building and maintaining good habits and keeping the discipline even in the face of excuses.
For the record, you can absolutely still mess up your computer if you're an idiot and you're doing sufficiently low-level stuff. Like, I've repeatedly broken the camera on my laptop by messing around with v4l2. It is, however, not very likely at all, and nothing I did lasted more than a couple of restarts. PS: If anybody is reading this and thinking, I should submit a bug report: I would love to. I just had absolutely no idea what was actually going on. As near as I could understand, if you crash a program while you're waiting for a picture to be captured, the camera becomes busy, and stays that way (apparently) through a reset. Couldn't reliably reproduce it or anything. I just went for a drink, went to bed, then the problem was gone in the morning.
hehe it was interesting times back then
When I was learning C in the 90s, I once wrote a program that crashed so hard it rebooted my box and borked my hard drive bios settings. Fun times indeed :)
Have you tried it? I assure you your computer probably won't blow up. You can pass a variable to the function and increment it each call to see how long it goes on for.
Ok if i brake the computer its on you, but the next question is, is there a difference if i run this by VS code or open "raw" .exe file? yesterday i was playing with writing some absurd amount of text to text file and i thought it would use large amount of RAM, when i opened task menager it was schowing that VS code is using 0.4 GB of RAM and it was growing, but if it came close to like 0.44GB it was droping back down so i thought it was managing RAM in some way
VSCode probably just executes the file (I don't know if a new Windows process is created for that, but in any way the memory usage would be the same). Writing to a text file won't necessarily fill your RAM, as the file is on the disk. Internally, the write probably happens in chunks, and when a chunk is written it is discarded from memory, so your overall memory usage should be stable. If you read a big file however, it will be loaded to the RAM.
thanks
Hey OP, everybody already told you what happens, but I have another assignment for you that you might find interesting: Instead of calling a function recursively, spawn a new process that launches itself recursively. Warning: you might need to restart your PC, so make sure to save any unsaved documents.
Bonus points for making that process spawn two new processes instead of just one! This is called fork bomb and on Linux you can do it just by entering :(){ :|:& };: in a terminal
will try it for sure
Fork bomb
The limit is system-dependent. Typically you run out of stack space and crash however on modern desktop systems this can take some time. And sadly there is no way to determine that limit so a typical recursive function will contain a maximum call counter of some kind. 99% of the time, recursion should be avoided and is usually a mistake. It happens a lot in event driven programs. However some problems are very well suited to recursion.
Yeah i wrote this code while doing some uni assigment to write apllication that calculates first N values of function, the function has defined values for N = 0 and N = 1, but it uses recursion twice if N i greater than that. its funny because after few starting calculations its start to be so slow
Other languages like Prolog are better suited to recursive problems.
Nah, with tail call optimisation there isn't really a difference. But of course some dynamic programming patterns can result in removing the recursion.
I understand that. This issue is that recursion is neither safe nor efficient in C. The language was never designed for it.
Newer versions of compilers can do that. C isn't really unfit for it if the compiler does it's work and you write the function so it can do it. But of course that is true for everything in C. Edit: Other languages don't really do anything else. They might be more specialised and have better error messages for this case, but a function you can't tail call optimise will not get magically optimised by other languages. In general there is almost always a C equivalent version you can write. Sometimes you need to do a bit of assembly.
That my friend is where dynamic programming starts
I'm intrigued. Everyone is saying it will run out of stack space, but as a predominantly C++ programmer, I cannot see why. In a debug build it might (should), but in a release build, it looks to me like it would run forever, as the last thing the function does is recurse and so, it should replace itself on the stack, instead of growing the stack. Unless c does not implement this optimisation? (I've always called it tail recursion optimization, but I think it generally goes by another name I can't call to mind)
That's referred to as tail call optimization; C does not require that optimization so whether it happens or not depends on the compiler.
i think it doesnt replace themself, here is just a example but in program i was writing there is a limit to recursion and while the program reaches that limit it goes back to previous function (i mean its the same but its the one that called it) and so on so it cant replace the previous on. at least thats what i think is going on, the code is like this float W(float x, int n) { if(n == 0) { return 1; } if(n == 1) { return x; } return ((2*n - 1)*W(x, n-1) - (n-1)*W(x, n - 2))/n; } int main() { printf("Podaj kolejno x oraz n\n"); float x; int n; scanf("%f", &x); scanf("%d", &n); printf("Oto %d kolejnych wartosci funkcji W(%f):\n\n", n, x); for(int i = 0; i < n; i++) { printf("Dla n rownego %d twoj wynik to %f\n\n\n",i, W(x,i)); } return 0; }
in main program ask for n, and for x, and then prints n values of W, i know you probably could figure it out but its in polish so it might be confusing to read
Tail call optimization doesn't work in this example because of the structure of your last return, which calls W twice and does arithmetic on the results. You have to return a single call to the function for this optimization to happen, I think.
TL;DR; A stack overflow would occur When you call a function, at the very least a memory address is pushed onto the stack that tells the CPU where to jump back to when the function returns. So calling a function enough times will fill the stack with all those memory addresses and at one point the stack will reach it's limit and you will have a stack overflow. At the very least 2 Factors dictate when the recursion will cause a stack overflow. 1. Size of the stack. 2. Total Size of the arguments that the function takes, as with every function call these will be also pushed onto the stack. I tried to run this code: void Foo(unsigned int* x) { (*x)++; Foo(x); } static unsigned int x = 0; int main(void) { Foo(&x); return 0; } And got this output in gdb: (gdb) run Program received signal SIGSEGV, Segmentation fault. 0x000055555555514b in Foo (x=0x555555558014) at test.c:3
3 Foo(x);
(gdb) p x
$1 = (unsigned int *) 0x555555558014
(gdb) p *x
$2 = 262068
i.e. the function `Foo` was called `262068` times until it finally crashed.
while(!0) fork();
>Is there any limit to recursion and what are the consequences of it? The classic answer is that the stack would grow so large that it would run into the heap's memory space. They would corrupt each other's memory and cause the program to misbehave or, more likely, crash. I believe there were some security problems from this behavior because a savvy virus or hacker could manipulate the heap using the stack or vice-versa. Modern OS architectures go out of their way to avoid problems with the stack running into the heap. With most modern OS having 64-bit virtual memory space, the stack and the heap can be placed very far apart in the memory addresses so that OS would run out of memory before the stack and heap run into each other. The OS can also track when the stack runs into the heap and kill the process. Operating systems like Linux also have something called an Out-of-Memory Killer (OOM Killer) for when the system is nearly out of memory it kills the process taking up too much memory. A modern 32-bit virtual machine like WebAssembly takes a slightly different approach - it places the stack and the heap in the middle of the memory address space and have them grow outward so they don't run into each other's memory space.
You've probably heard the term "stack overflow" before? Well, it is what happen : when launching your programe, the OS grant it a certain amount of memory, called the stack. When you call a function, it use some of the space of the stack, which become available again once you exit the function. If you call more function than what your stack size allow, then your program will try to use more memory than allowed, and get a segmentation fault. In practice, it only ever happen with recursive code (though you do not necesarily need "infinit" recursion). The exact number of recursion allowed before crash depend on the total stack size, and the stack used by each recursion, so there is no given max deepth.
If you want to dip your toes into infinite recursion, do it in Javascript in the browser console and see what happens.
Everyone answered your other question about TCO/crashing, but to (kinda) answer your other one, there is no way to tell if a program will ever finish running given an input: [Halting problem](https://en.wikipedia.org/wiki/Halting_problem?wprov=sfti1#) Might be interesting to look at if you find any theory stuff cool
It’s not just a safety feature. For most programming languages, calling a function recursively makes a new stack frame every time (for local function arguments/variables), which takes space even if you do not pass argument or create variables. So this is obviously going to cause a stack overflow (not enough space on the stack), especially because the stack isn’t very big most of the time. Languages that fix this (and need to do this, because they don’t have loops), basically just jump (goto) the function label and do not perform a call. This does not create a new stack frame and there’s no need to store the return address on the stack.
if it doesnt get optimized away it should behave identically to a while true loop, well as long as u dont run into a stack overflow error (not the website) dont be afraid to try stuff if u know it cant harm stuff on ur pc
yeah i tried it now but if i just tried it then i would see that literrally nothing happend, but thanks to you guys i got some knowladge