Programming in C & Recursion

C questions in GATE are not about knowing library functions. They are about predicting exactly what a short program prints, and that prediction is always made the same way.

C is a thin layer over memory addresses. A variable is a named location, a pointer is an address with a type attached, and an array name is very nearly an address. Almost every surprising output in a GATE question is a consequence of that fact rather than of any special rule.

So the method is: draw the memory. Draw each variable as a box, each pointer as an arrow, each function call as a new frame on the stack. Then step through the program updating the drawing. This is slower to describe than to do, and it is far more reliable than reasoning about the code as text.

The second organising fact is that the type attached to a pointer controls arithmetic on it. Adding 1 to an int * advances by four bytes on a typical machine, not by one, and this single rule explains most pointer-arithmetic questions.

The third is that recursion is the stack made visible. Each call gets its own frame with its own copies of parameters and locals, and understanding a recursive function means drawing that stack rather than trying to hold the whole unfolding in your head.

1. Pointers as Typed Addresses

A pointer holds an address. The type says what is stored at that address, and therefore how many bytes an object there occupies.

int x = 10;
int *p = &x;    /* p holds the address of x */
*p = 20;        /* writes through p; x is now 20 */

The declaration syntax is read from the identifier outward. In int *p, the * binds to p, so p is a pointer to int. This is why int *p, q; declares one pointer and one plain integer, which catches people constantly.

A pointer to a pointer holds the address of another pointer, and dereferencing twice reaches the final value.

A null pointer is a distinct value guaranteed not to point at any object. Dereferencing it is undefined behaviour, and so is dereferencing an uninitialised pointer, which holds whatever bits were in that memory.

The void * type holds an address with no type attached, so it cannot be dereferenced directly and cannot participate in pointer arithmetic. It exists to pass addresses generically, which is why malloc returns one.

2. Pointer Arithmetic

Adding an integer $n$ to a pointer of type T * advances the address by $n\times \text{sizeof}(T)$ bytes.

$p+n\equiv \text{address}(p)+n\times \text{sizeof}(T)$

This scaling is automatic and is the source of most confusion. If p is an int * holding address 1000 and an int is 4 bytes, then p + 3 holds address 1012, not 1003.

Subtracting two pointers of the same type gives the number of elements between them, not the number of bytes, by dividing the byte difference by the element size.

Comparison and subtraction are defined only within a single array, including one position past its end. Comparing pointers into unrelated objects is undefined behaviour even though it usually appears to work.

Incrementing a pointer past one-past-the-end, or dereferencing the one-past-the-end position, are both undefined. The one-past-the-end address may be formed and compared, which is what makes the standard loop idiom legal.

3. Arrays and Pointers

Arrays and pointers are related but are not the same thing, and the differences are examined directly.

An array name decays to a pointer to its first element in almost every context, which is why arr[i] and *(arr + i) are equivalent, and indeed why i[arr] compiles and means the same thing.

The exceptions are where it matters. sizeof(arr) gives the size of the whole array, not of a pointer, and &arr has type "pointer to array" rather than "pointer to element", so &arr + 1 skips the entire array.

An array cannot be assigned and cannot be passed by value. Declaring a function parameter as int a[] is exactly equivalent to int *a, which is why sizeof inside the function gives the pointer size and why a function can never determine an array's length from the parameter alone.

For a two-dimensional array int a[R][C], the elements are stored in row-major order, so the address of a[i][j] is the base plus $(i\times C+j)\times \text{sizeof(int)}$.

A two-dimensional array is not an array of pointers. int a[3][4] is 12 contiguous integers; int *b[3] is 3 pointers that may point anywhere. Passing the first to a function expecting the second is a type error, and confusing them is a standard exam trap.

Strings inherit every one of these rules, because a C string is only a character array with a convention attached.

The convention is a terminating null character, and every library function relies on it. A character array without one is not a string, and passing it to a string function reads past the end until a zero byte happens to appear.

The two size measures differ accordingly. sizeof on a character array gives the declared size including the terminator, while the length function counts characters up to but excluding it. For an array declared with the literal "GATE", the first gives 5 and the second gives 4.

A string literal assigned to a pointer rather than an array is stored in read-only memory, so writing through that pointer is undefined even though the code compiles cleanly.

4. Parameter Passing

C passes every argument by value, without exception. A function receives a copy, and modifying the copy cannot affect the caller's variable.

The appearance of pass-by-reference is achieved by passing a copy of an address. The function still cannot change the caller's pointer, but it can change what the pointer points at.

void bad(int x)  { x = 99; }        /* caller unaffected */
void good(int *x){ *x = 99; }       /* caller's variable changed */

A function that must change the caller's pointer needs a pointer to pointer. This is why a function that allocates memory and returns it through a parameter takes a T **.

Passing an array passes a copy of the address of its first element, which is why array modifications inside a function are visible to the caller — not because arrays are special, but because an address was copied.

Other languages offer alternatives worth distinguishing. Call by reference binds the parameter to the caller's variable itself. Call by value-result copies in on entry and copies back on exit, which differs from reference when the same variable is passed twice or is modified concurrently. Call by name substitutes the argument expression textually and re-evaluates it at every use.

5. Storage Classes

Four storage classes control lifetime and visibility.

A static local variable keeps its value between calls, because it lives in the data segment rather than on the stack. This is the basis of a standard question shape: a function with a static counter that increments across calls.

Uninitialised locals contain indeterminate values, while uninitialised statics and globals are zero. Relying on the first is undefined behaviour; relying on the second is guaranteed.

Memory divides into four regions with different behaviour: the code segment, the data segment for globals and statics, the heap for malloc, and the stack for locals and call frames.

The heap must be freed explicitly and the stack is freed automatically, which is why forgetting free leaks memory while forgetting to clean up a local does not.

Returning the address of a local variable is a classic error: the frame is destroyed on return, so the pointer refers to memory that no longer belongs to anyone.

6. Recursion and the Stack

Each recursive call creates a new activation record on the stack, containing that call's parameters, locals and return address. This is why each call has its own copies and why recursion terminates the program if the depth exceeds the stack size.

Every correct recursive function has two parts, and questions are usually built by damaging one of them.

A base case that returns without recursing, and a recursive case that moves strictly closer to the base case. Omitting either produces infinite recursion.

The order of operations relative to the recursive call determines the output order, and this is the most frequently examined detail.

void f(int n) {
    if (n == 0) return;
    printf("%d ", n);   /* before the call: descending */
    f(n - 1);
}

void g(int n) {
    if (n == 0) return;
    g(n - 1);
    printf("%d ", n);   /* after the call: ascending */
}

Work done before the call happens on the way down; work done after happens on the way back up. The second version prints in the opposite order despite an almost identical body.

Tail recursion is the case where the recursive call is the last operation, with nothing left to do afterwards. It can be converted mechanically into a loop, and some compilers do so, eliminating the stack growth. The second function above is not tail recursive, because the printf still has to run after the call returns.

7. Analysing Recursive Functions

The running time of a recursive function is described by a recurrence, and the recurrence is read directly from the code.

Count the number of recursive calls and the size of each subproblem, then add the work done outside the calls.

A function that makes one call on a problem of size $n-1$ and does constant work gives $T(n)=T(n-1)+O(1)$, which solves to $O(n)$.

A function that makes two calls on size $n-1$ gives $T(n)=2T(n-1)+O(1)$, which solves to $O(2^n)$ — the naive Fibonacci case.

A function that makes two calls on size $n/2$ with linear extra work gives $T(n)=2T(n/2)+O(n)$, which solves to $O(n\log n)$ — the merge sort case.

The space complexity of a recursive function is the maximum stack depth, not the total number of calls. Naive Fibonacci makes exponentially many calls but its stack never exceeds depth $n$, so it uses $O(n)$ space.

That distinction between total calls and maximum depth is examined directly and is missed often.

8. Undefined Behaviour

Several constructs have no defined meaning, and a question exploiting one is asking whether you recognise it rather than what the output is.

Modifying a variable more than once between sequence points is undefined, which is why expressions like i = i++ + ++i have no correct answer.

Reading an uninitialised variable, dereferencing a freed or null pointer, and indexing outside an array are all undefined, and none of them reliably crashes — which is precisely what makes them dangerous.

Integer overflow of a signed type is undefined, while unsigned overflow is defined to wrap modulo $2^n$. The asymmetry surprises people and is worth remembering exactly.

The practical consequence for an exam is that if a question's code contains one of these, the intended answer is usually that the behaviour is undefined or implementation-dependent, and computing a specific value is the trap.

9. Worked Examples

Example 1. What does this print?

int a[5] = {1, 2, 3, 4, 5};
int *p = a;
printf("%d %d %d", *p + 1, *(p + 1), *++p);

Take the three expressions separately, remembering that * and + bind differently in each.

*p + 1 dereferences first, giving a[0] which is 1, then adds 1, giving 2.

*(p + 1) adds first, advancing the pointer by one int, then dereferences, giving a[1] which is 2.

*++p increments p first, so p now points at a[1], then dereferences, giving 2.

All three print 2, but for three different reasons — which is the point of the question.

There is a serious caveat. The order in which the arguments to printf are evaluated is unspecified, and the third expression modifies p while the second reads it. This program therefore has unspecified behaviour, and a well-set question would separate the statements. Recognising that is worth more than the arithmetic.

Example 2. What is the output?

void f() {
    static int count = 0;
    count++;
    printf("%d ", count);
}
int main() { f(); f(); f(); return 0; }

The variable is static, so it lives in the data segment for the whole program rather than on the stack.

The initialisation = 0 happens once, before main runs, not on every call.

Call 1 increments it to 1 and prints 1. Call 2 increments to 2 and prints 2. Call 3 prints 3.

The output is 1 2 3.

Had static been omitted, the variable would be a fresh stack local each time, initialised to 0 on every call, and the output would be 1 1 1.

Example 3. Trace the output of this recursive function for n = 3.

void g(int n) {
    if (n == 0) return;
    g(n - 1);
    printf("%d ", n);
}

Draw the stack. The call g(3) immediately calls g(2) before printing anything. g(2) calls g(1), which calls g(0).

g(0) returns without printing, because the base case fires first.

Now the stack unwinds. g(1) resumes after its call and prints 1. g(2) resumes and prints 2. g(3) resumes and prints 3.

The output is 1 2 3, in ascending order, even though the parameter descended.

Moving the printf above the recursive call would print 3 2 1, because the work would then happen on the way down rather than on the way back up. That single line placement is the whole content of a common question type.

Example 4. What does this print, and why?

void swap(int a, int b) { int t = a; a = b; b = t; }
int main() {
    int x = 3, y = 5;
    swap(x, y);
    printf("%d %d", x, y);
    return 0;
}

C passes by value, so swap receives copies of x and y in its own stack frame.

The function exchanges its local copies perfectly, and then the frame is destroyed on return.

The caller's variables were never touched, so the output is 3 5.

The fix is to pass addresses: void swap(int *a, int *b) with *t = *a; *a = *b; *b = t; and a call of swap(&x, &y). Even then, the addresses themselves are passed by value — the function cannot change which variables the caller's names refer to, only the contents at those addresses.

Example 5. How many times is f called for f(5), and what is the maximum stack depth?

int f(int n) {
    if (n <= 1) return n;
    return f(n - 1) + f(n - 2);
}

This is naive Fibonacci. Let $C(n)$ be the number of calls including the initial one.

$C(0)=C(1)=1$. For larger $n$, $C(n)=1+C(n-1)+C(n-2)$.

$C(2)=1+1+1=3$. $C(3)=1+3+1=5$. $C(4)=1+5+3=9$. $C(5)=1+9+5=15$.

So f is called 15 times.

The maximum stack depth is different. At any moment the stack holds one chain of calls, and the longest chain follows n-1 repeatedly: f(5), f(4), f(3), f(2), f(1).

The maximum depth is 5, so the space complexity is $O(n)$ even though the time complexity is exponential.

The gap between 15 calls and depth 5 is the whole point. Calls that have returned no longer occupy the stack, so total work and peak space are unrelated quantities.

Example 6. What is wrong with this function, and what does the caller see?

int *make(void) {
    int local = 42;
    return &local;
}

The variable local lives in make's stack frame. When make returns, that frame is released and the memory becomes available for the next call.

The returned pointer therefore refers to memory that no longer belongs to anyone. Dereferencing it is undefined behaviour.

What makes this dangerous rather than merely wrong is that it often appears to work. Immediately after the return, the bytes may still contain 42 because nothing has overwritten them yet. The first unrelated function call will reuse that stack space, and the value will change at an unpredictable moment.

Three correct alternatives exist. Return the value rather than a pointer, which is simplest. Allocate on the heap with malloc, making the caller responsible for free. Or take a pointer to caller-provided storage as a parameter, which avoids allocation entirely.

Note that declaring local as static would also make the pointer valid, since the variable would then live in the data segment — but every call would return the same address, which is a different bug.

Summary

C is a thin layer over memory addresses, so draw the memory: boxes for variables, arrows for pointers, frames for calls.

A pointer's type controls its arithmetic. Adding $n$ advances by $n$ times the element size, and subtracting two pointers gives an element count, not a byte count.

An array name decays to a pointer except under sizeof and &. sizeof(arr) is the whole array; &arr + 1 skips it entirely.

An array parameter is a pointer, so a function cannot recover an array's length from the parameter. A two-dimensional array is contiguous and is not an array of pointers.

Everything is passed by value. Passing an address gives the appearance of reference; changing the caller's pointer requires a pointer to pointer.

Static locals live in the data segment, keep their value between calls, and are initialised once and to zero by default. Uninitialised locals are indeterminate.

Each recursive call gets its own frame. Work before the call happens on the way down and work after it on the way back up, which is what flips the output order.

A recurrence is read straight from the code: number of calls, subproblem size, and work outside the calls. Space is the maximum stack depth, not the total number of calls.

Undefined behaviour includes modifying a variable twice between sequence points, reading uninitialised memory, dereferencing freed or null pointers, indexing out of bounds, and signed overflow — while unsigned overflow is defined to wrap.