Question

Call stack question! Long one...

The call stack is part of main memory that is reserved for function calling. Like all r memory it is finite, so can be exhausted resulting in a stack overflow. Recursive functions allocate space on the stack for each recursive call: if there are many such recursive calls a stack overflow can result. The questions that follow ask you to investigate recursive functions and stack overflows. Note that when running programs in the Linux terminal a stack overflow results in a segmentation fault. Using C code write a recursive function that is equivalent to the iterative function shown below that prints the numbers from 1 to the largest possible integer value. Note that the constant INT_MAX is contained in the limits. Your recursive function should have a single integer parameter, and you should initially call the function by passing 1 to its parameter. Write a main function and run your solution to part (a) given above. The function will cause a stack overflow. When this has occurred take a screenshot of the terminal and include that in your submission. Your screenshot should show the segmentation fault and (at least) the last value that was printed. Run each of the two functions shown below in turn, initially passing each function the value 1 to its parameter. Again, take screenshots of the terminal showing the segmentation fault and the last value that was printed. Explain why or why not the segmentation fault occurred at different times for the two functions that you ran in part (c). Assume that a computer system has a heap of 2GB and that the size of the call stack for an application is 1MB. Quicksort is used to sort an array that is stored on the heap (i.e. it is stored in the computer's internal memory not on a file). Assume that each recursive call to quicksort requires 256 bytes to be allocated to the call stack. Explain why the call to quicksort will not result in a stack overflow regardless of the size of the array being sorted. You should assume that the call to quicksort results in the average case O Notation running time for the algorithm.

Answer 1

a)

void overflow(int i){
   printf("%d\n", i);

   if (i <= INT_MAX)
       overflow(i+1);
}

b)

#include<stdio.h>
#include<limits.h>

void overflow(int i){
   printf("%d\n", i);

   if (i <= INT_MAX)
       overflow(i+1);
}

void main() {
   overflow(1);
}

c)

for function foo:

for function bar:

d)

Segmentation fauslt should occur in general case because each recursive call causes program stack overflow. Ever function call pushes return address into the stack along with other params. Even in every recursive call the function variables also gets allocated which can be a large overhead. So after limited number of function call the stack gets exhausted causing segmentation fault.

(Cygwin provides certain protection, that does not cause segmentation fault!)