quarry: Infinite loop without using for , while, do-while

[Tinku]

I am sorry for asking this silly question, but i don't understand why
it is happening please suggest me
=================================
#include <stdio.h>
int main()
{
static int i=1;
printf("function call: %d time \n", i);
i++;
main();
}
=================================
this is a infinite loop, I ran this program 5-6 times , This program
gives segmentation fault (core dump) while main() function call at
523477, 523486, 523791... times. why this program give segmentation
fault after calling main() this much of time... what happens when the
main() calls at the last time before SF(CD).
Thanks .

 

[Antoninus Twink]

#include <stdio.h>
int main()
{
static int i=1;
printf("function call: %d time \n", i);
i++;
main();
}

this is a infinite loop, I ran this program 5-6 times , This program
gives segmentation fault (core dump) while main() function call at
523477, 523486, 523791... times. why this program give segmentation
fault after calling main() this much of time... what happens when the
main() calls at the last time before SF(CD).

In C, function calls are implemented using the stack. When your process
starts up, it is given a virtual address space, with the stack at the
highest addresses growing downwards towards the heap (and beyond it the
data and text sections).

Each time a function is called, a "stack frame" (local variables, return
address parameters) gets pushed onto the stack, and the stack pointer is
moved down in memory. If you call a function with a sufficiently high
level of recursion, eventually the stack will break through into
non-writable blocks of memory in your address space, and the OS will
trigger a SIGSEGV, as you've discovered.

 

[Chris Dollin]

Tinku said:


It's infinite recursion.

I ran this program 5-6 times , This program

What you are asking the computer to do is provide infinite capacity for
recursion. The computer can't do that because it must, at each stage,
remember where it came from, so to speak, and that cannot be done in zero
memory.

In this case, it can; it's a tail-call, so the call to main can return
to wherever /this/ main was called from. A little stack-bashing will
do the trick nicely. Noting that the called function is /this very
function/ allows the stack-bashing to be replaced by a branch back
to the start of the function ... result, an infinite loop that doesn't
run out of store.

Yes, Virginia, compilers will do this. GCC does.

Tail-calls rule!

 

[Jens Thoms Toerring]

In C, function calls are implemented using the stack. When your process
starts up, it is given a virtual address space, with the stack at the
highest addresses growing downwards towards the heap (and beyond it the
data and text sections).

Each time a function is called, a "stack frame" (local variables, return
address parameters) gets pushed onto the stack, and the stack pointer is
moved down in memory. If you call a function with a sufficiently high
level of recursion, eventually the stack will break through into
non-writable blocks of memory in your address space, and the OS will
trigger a SIGSEGV, as you've discovered.

If you would write "On my implementation, function calls are..."
or "I guess on your implementation,... " it would be ok. But the
moment you make a sweeping statement like "In C,..." this becomes
simply wrong. A stack is one way to implement it, but it's not
mandated by the C standard. And not all systems use virtual ad-
dress space, e.g. DOS does not. The stack pointer starts at a
high address and the stack grows downward on some systems, on
others it's exactly the other way round (and if the heap is above
or below the stack area or if they are neighbors at all is another
implementation detail that isn't mandated by C). Finally, you don't
need to get a segmentation fault, there's nothing in C that would
forbid an implementation to check the stack pointer for bounds and
abort the program with a nice error message about an attempt of
the program to overflow the stack area.

Regards, Jens

 

[rahul]

In this case, it can; it's a tail-call, so the call to main can return
to wherever /this/ main was called from. A little stack-bashing will
do the trick nicely. Noting that the called function is /this very
function/ allows the stack-bashing to be replaced by a branch back
to the start of the function ... result, an infinite loop that doesn't
run out of store.

I don't think that the standard mandates transforming tail recursion
calls to
branching instructions. Its up to the compiler which may or may not
chose to
convert the tail calls.

 

[Chris Dollin]

I don't think that the standard mandates transforming tail recursion
calls to branching instructions.

It doesn't. I didn't suggest it did. (I might wish otherwise, of
course.)

Its up to the compiler which may or may not chose to convert the tail
calls.

I didn't mean to imply otherwise, but I see that

Yes, Virginia, compilers will do this.

in my post was ill-written; it should have been "some compilers will
do this" or "compilers can [are allowed to] do this".