After 147 recursive invoke, segmentation fault happens. (in C)

Question

I invoke a function 147 times in recursive and when it invokes for 147. times, program exe stops(codeblocks).

Before invokin function again, it assigned 1 int global variable to local, 1 int 2 dimensional global array to local and 1 string global variable to local variable. So, 146 of those maybe became a very huge load for program?

The function is:

Carefully read the name of this website [StackOverflow](http://en.wikipedia.org/wiki/Stack_overflow) and try to google the meaning of this word. — Mohit Jain, Jun 10 '14 at 09:21
I added but i have to delete later some of those code. @Codor — user3721298, Jun 10 '14 at 09:26
Actually this function is being called more than millions in normal but here only 211 times called after the segmentatation error. counter became 147, i was wrong. — user3721298, Jun 10 '14 at 09:29
Calling recursively a function with a 12k buffer on the stack might not be the best idea ever. — toasted_flakes, Jun 10 '14 at 09:31
I cant even do debugging, i have to go ten thousands step to pass. — user3721298, Jun 10 '14 at 09:35
You can do debugging. You just need a more sophisticated breakpoint definition. Find out on what line the segfault occurs. — slim, Jun 10 '14 at 09:37
As i told, 'path' and 'visited ' are globals.In beginnning 'char path[4500]= {}; int visited[2416]= {0};' — user3721298, Jun 10 '14 at 09:37
I made path and paths size 45 from 4500 but still they could have more than 45. And this time, more than 211 times invoked. — user3721298, Jun 10 '14 at 10:14

score 2 · Accepted Answer · edited May 23 '17 at 12:27

It seems your stack is overflowing by recursive calls. Quoting from above wiki page

In software, a stack overflow occurs when the stack pointer exceeds the stack bound. The call stack may consist of a limited amount of address space, often determined at the start of the program. The size of the call stack depends on many factors, including the programming language, machine architecture, multi-threading, and amount of available memory. When a program attempts to use more space than is available on the call stack (that is, when it attempts to access memory beyond the call stack's bounds, which is essentially a buffer overflow), the stack is said to overflow, typically resulting in a program crash

Very deep recursion and large stack variables along with recursion are some easy to fall reasons of stack overflow.

You may want to write a smarter code to get away from recursions.

Below links may help you get there.

I don't think this is the answer. 147 iterations isn't enough to overflow the stack. Refactoring recursion into an iterative style isn't necessary unless you're hitting much deeper recursion than 147. — slim, Jun 10 '14 at 09:54
Refactoring along with some smarter code. For ex: deferring the formatted array for path creation, cutting on memory, using least amount dynamic memory usign `realoc` that is required. And for further details we have (+1) your answer. — Mohit Jain, Jun 10 '14 at 10:04

score 2 · Answer 2 · answered Jun 10 '14 at 10:00

Each time you invoke your function, you allocate:

int visitedS[2416] = 2416 * 32 bits = 9.4KB
char pathS[4500] = 4500 * 8 bits = 4.4KB

So that's almost 14KB that gets placed on the stack every time you recurse.

After 147 recursions, you've put 1.98MB on the stack. That's not so huge - a typical Linux stack limit is 8MB.

I would check - through using a debugger or even adding debug print statements - your assumption that this is truly happening after 147 recursions. Perhaps there is a bug causing more invocations than you believed.

Even so, it may well be worth thinking about ways to reduce the memory footprint of each invocation. You seem to be creating local arrays which are copies of a global. Why not just use the data in the global. If your function must make changes to that data, keep a small set of deltas locally.

Local array because i use them stack. After invoking, i can return the previous state of them. I am making deep first so if there is no way, i shhould copy data in locals, previous way. — user3721298, Jun 10 '14 at 10:03

After 147 recursive invoke, segmentation fault happens. (in C)

2 Answers2