C Programming

GATE CS & UGC NET JRF Core Subject Exam Weightage: 2–3 Questions every year tracing recursive function calls with static variables, stack frame allocation, and function pointer signatures.

1. Technical Jargon & The Activation Record#

Every time a function is invoked in C, a contiguous block of memory called an Activation Record (Stack Frame) is pushed onto the runtime Call Stack.

Process Virtual Memory Map:
High Addresses (0xFFFF...)
┌────────────────────────────────────────────────────────┐
│                   Kernel Space                         │
├────────────────────────────────────────────────────────┤
│                   STACK (grows downward ↓)             │
│   ┌────────────────────────────────────────────────┐   │
│   │ [main's frame]                                 │   │
│   │   - Local vars                                 │   │
│   ├────────────────────────────────────────────────┤   │
│   │ [foo's frame]                                  │   │
│   │   - Parameters passed by caller                │   │
│   │   - Return Address (where to resume in caller) │   │
│   │   - Saved Frame Pointer (EBP/RBP)              │   │
│   │   - Local variables of foo                     │   │
│   └────────────────────────────────────────────────┘   │
│                            ↓                           │
│                     (Free Memory)                      │
│                            ↑                           │
│                   HEAP (grows upward ↑)                │
│                   (malloc / free)                      │
├────────────────────────────────────────────────────────┤
│                   BSS Segment (Uninitialized Static)   │
├────────────────────────────────────────────────────────┤
│                   Data Segment (Initialized Static)    │
├────────────────────────────────────────────────────────┤
│                   Text Segment (Machine Code Instructions│
└────────────────────────────────────────────────────────┘
Low Addresses (0x0000...)

1. Stack Frame / Activation Record: The private memory block containing function parameters, local automatic variables, temporary values, saved registers, and the return address.
2. Stack Pointer (SP / RSP): Register pointing to the current top of the stack.
3. Frame / Base Pointer (BP / RBP): Fixed reference register used to calculate offsets for parameters (positive offset) and local variables (negative offset).
4. Call by Value: In C, ALL arguments are passed strictly by value. The parameter receives a copy of the caller's argument. Modifying the formal parameter has zero effect on the caller.
5. Call by Reference Simulation: C has no native reference type (unlike C++). Simulated call-by-reference is achieved by passing the memory address (pointer) by value, enabling the callee to dereference and modify caller memory.
6. Tail Call: A function call performed as the final action within a function. A compiler can optimize tail recursion into a jump loop without allocating new stack frames (Tail Call Optimization).

2. Parameter Passing: Passing Values vs. Passing Pointers#

#include <stdio.h>

// 1. FAILS: Pass-by-value makes copies. Caller's variables are UNCHANGED.
void swap_wrong(int a, int b) {
    int temp = a;
    a = b;
    b = temp;
}

// 2. SUCCEEDS: Addresses are passed. Dereferencing modifies caller's variables directly.
void swap_correct(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

int main(void) {
    int x = 10, y = 20;
    swap_wrong(x, y);
    printf("%d %d\n", x, y); // Still 10 20

    swap_correct(&x, &y);
    printf("%d %d\n", x, y); // Now 20 10
    return 0;
}

3. Recursion Mechanics & Stack Unwinding#

Recursion consists of two phases:

1. Winding Phase: Successive stack frames are allocated on the stack until the Base Case condition is satisfied.
2. Unwinding Phase: Functions complete their work, return computed values to their callers, and have their stack frames deallocated.

Tracing factorial(3):
Winding:   main() --> push factorial(3) --> push factorial(2) --> push factorial(1) [Base case: returns 1]
Unwinding: factorial(2) receives 1, returns 2*1=2 --> factorial(3) receives 2, returns 3*2=6 --> main() receives 6

4. GATE Exam Focus: Recursion with static and Global State#

The #1 most frequent C programming question pattern in GATE CS involves recursive functions containing static variables.

The Critical Rule:#

• Normal local variables have independent copies in every stack frame.
• static variables have ONLY ONE COPY IN THE ENTIRE PROGRAM (stored in the data segment). Any modification in any frame permanently alters the value seen by ALL frames during both winding and unwinding!

#include <stdio.h>

int f(int n) {
    static int i = 1;
    if (n >= 5)
        return n;
    n = n + i;
    i++;
    return f(n);
}

int main(void) {
    printf("%d\n", f(1));
    return 0;
}

Step-by-Step Execution Trace:#

• Iteration 1: f(1)
  • static int i = 1
  • n >= 5 is false ($1 < 5$).
  • n = n + i $\implies n = 1 + 1 = 2$.
  • i++ $\implies i = 2$.
  • Calls f(2).
• Iteration 2: f(2)
  • n = 2, i = 2.
  • n >= 5 is false ($2 < 5$).
  • n = n + i $\implies n = 2 + 2 = 4$.
  • i++ $\implies i = 3$.
  • Calls f(4).
• Iteration 3: f(4)
  • n = 4, i = 3.
  • n >= 5 is false ($4 < 5$).
  • n = n + i $\implies n = 4 + 3 = 7$.
  • i++ $\implies i = 4$.
  • Calls f(7).
• Iteration 4: f(7)
  • n = 7, i = 4.
  • n >= 5 is true ($7 \ge 5$).
  • Returns 7.
• Output: 7.

5. Function Pointers: Syntax & Jump Tables#

A function in C resides in the text (code) segment and has a memory entry point address. A Function Pointer holds this code address.

5.1 Function Pointer Syntax#

// Declaration of a function pointer 'fp' that takes two ints and returns an int:
int (*fp)(int, int);

// Concrete functions:
int add(int a, int b) { return a + b; }
int mul(int a, int b) { return a * b; }

int main(void) {
    fp = add; // Or fp = &add (both are equivalent in C)
    printf("Add: %d\n", fp(10, 5)); // Prints 15 (or (*fp)(10, 5))

    fp = mul;
    printf("Mul: %d\n", fp(10, 5)); // Prints 50
    return 0;
}

5.2 Jump Tables (Array of Function Pointers)#

Instead of huge switch or chained if-else blocks, high-performance systems and OS kernels use Jump Tables:

typedef int (*Operation)(int, int);

int add(int a, int b) { return a + b; }
int sub(int a, int b) { return a - b; }
int mul(int a, int b) { return a * b; }

int main(void) {
    // Array of function pointers:
    Operation jump_table[] = {add, sub, mul};

    int op_code = 2; // 0=add, 1=sub, 2=mul
    int result = jump_table[op_code](10, 4); // Calls mul(10, 4) in O(1) time
    printf("Result = %d\n", result); // 40
    return 0;
}

6. Best Practices & Defensive Function Design#

1. Always Establish a Base Case First in Recursion: Verify that recursive arguments strictly advance towards the base condition to prevent Stack Overflow (SIGSEGV).
2. Favor Iteration for Simple Loops: Recursion carries stack frame overhead (register saving, parameter copying). Use iteration unless the underlying data structure is recursive (trees, divide & conquer).
3. Use typedef for Function Pointer Readability: Writing void (*cb)(int) everywhere is prone to bugs. Write typedef void (*Callback)(int); instead.