C functions and recursion interview questions, with answers

The questions, with answers

1. 1.Does C pass arguments by value or by reference?

   In short: Always by value: a function gets copies of its arguments, so to change a caller's variable you pass its address and write through the pointer.

   Every argument in C is copied into the called function's parameter, and assigning to the parameter changes only the copy. That is why a swap function that takes two ints swaps nothing in the caller. C imitates pass-by-reference by passing pointers: the address itself is still passed by value, but writing through it, *a = *b, changes the caller's variable, which is the working version below. A struct argument is copied whole, member by member, which is why large structs are usually passed by pointer instead, often a pointer to const when the function only reads. C++ added real reference parameters, int &a, precisely so that this common pattern would not need explicit pointers.

   void swap(int *a, int *b) {
       int t = *a;
       *a = *b;
       *b = t;
   }
   
   int main(void) {
       int m = 1, n = 2;
       swap(&m, &n);
       printf("%d %d\n", m, n);
   }
   // 2 1

2. 2.What is a function prototype, and what happens if you call a function before declaring it?

   In short: A prototype declares a function's return and parameter types before use; C99 removed calls to undeclared functions, and modern gcc rejects them as errors.

   A prototype such as int area(int w, int h); tells the compiler how to call a function whose definition comes later or lives in another file, so it can check the number and types of the arguments and convert them, for example an int argument to a double parameter. C89 allowed calling an undeclared function and assumed it returned int, which silently broke functions returning pointers or doubles. C99 removed that implicit declaration, and gcc 14 and later treat it as an error by default. Sharing prototypes is most of what header files are for. Before C23, an empty parameter list, int f(), meant unspecified parameters rather than none, so int f(void) was the correct form; C23 finally makes () mean no parameters, as in C++.

   int area(int w, int h);
   
   int main(void) {
       printf("%d\n", area(3, 4));
   }
   
   int area(int w, int h) {
       return w * h;
   }
   // 12

3. 3.Why can deep recursion crash a C program?

   In short: Each call pushes a stack frame, the stack holds only a few megabytes, and C does not guarantee tail-call elimination, so very deep recursion overflows the stack.

   Every active call keeps its own frame on the call stack, holding its parameters, locals and return address, and the frame is released only when that call returns. The main thread's stack is small, typically 1 MB on Windows and 8 MB on Linux, so a recursion a few hundred thousand levels deep, or one with a large local array in every frame, exhausts it. The result is a stack overflow, reported as a segmentation fault or an access violation, not an error the program can catch. Compilers may turn a tail call into a jump at higher optimisation levels, but the standard does not require it. So recursion suits problems whose depth stays small or logarithmic, such as balanced trees, and deep linear recursion over big inputs should be a loop.

   long sum(int n) {
       if (n == 0)
           return 0;
       return n + sum(n - 1);
   }
   
   int main(void) {
       printf("%ld\n", sum(1000));
   }
   // 500500

4. 4.Can a C function return an array, or a pointer to a local variable?

   In short: It cannot return an array type, and returning the address of a local leaves a dangling pointer; return a struct, a malloc'd block, or fill a buffer the caller passes in.

   C functions cannot have an array return type, and a local array lives in the function's stack frame, which is released on return, so returning its address, even disguised as a pointer, hands the caller a dangling pointer: using it is undefined behaviour, and gcc warns that the function returns the address of a local variable. There are three correct designs. Wrap a fixed-size result in a struct and return the struct by value, as below. Allocate with malloc and document that the caller must free the result. Or, most common in the standard library, let the caller pass in a buffer and its size, as snprintf and fgets do. A static local array also survives the return, but every call shares it, which breaks recursion and threads.

   struct pair { int a, b; };
   
   struct pair mm(int x, int y) {
       struct pair p = {x, y};
       if (x > y) {
           p.a = y;
           p.b = x;
       }
       return p;
   }
   
   int main(void) {
       struct pair r = mm(9, 4);
       printf("%d %d\n",
           r.a, r.b);
   }
   // 4 9

5. 5.How do you sort an array with qsort, and what must the comparison function return?

   In short: Pass the array, its length, the element size and a comparison function returning a negative number, zero or a positive number as the first element sorts before, equal to or after the second.

   qsort sorts any array because it knows nothing about the elements: it takes a void pointer to the array, the element count, the size of one element, and your comparison function, which receives two const void pointers to elements and must convert them back to the real type. The function must return a negative value, zero or a positive value, and do so consistently, or the result is undefined. The shortcut return a - b is a known bug, because the subtraction can overflow when the values are large and of opposite signs; (a > b) - (a < b), used below, cannot. qsort is not required to be stable, and despite its name the standard does not require it to be quicksort.

   int cmp(const void *p,
           const void *q) {
       int a = *(const int *)p;
       int b = *(const int *)q;
       return (a > b) - (a < b);
   }
   
   int main(void) {
       int v[] = {5, -2, 9, 0};
       qsort(v, 4, sizeof(int),
           cmp);
       for (int i = 0; i < 4; i++)
           printf("%d ", v[i]);
   }
   // -2 0 5 9

6. 6.How do variadic functions like printf work, and why is a wrong format specifier dangerous?

   In short: They read their extra arguments with va_start and va_arg from <stdarg.h>, trusting the caller about how many there are and their types; a mismatch is undefined behaviour.

   A variadic function declares at least one fixed parameter followed by ..., and walks the remaining arguments with a va_list: va_start begins after the last fixed parameter, each va_arg(ap, type) fetches the next argument as the stated type, and va_end finishes. Nothing in the call records how many arguments there are or their types, so the function needs a convention: a count, as below, a terminating sentinel, or a format string, as in printf. If a caller passes a double where the format says %d, va_arg reads the wrong bytes and the behaviour is undefined, which is why gcc checks printf formats with -Wformat. Arguments to ... are promoted first, char and short to int and float to double, so va_arg must name the promoted type.

   int sum(int n, ...) {
       va_list ap;
       va_start(ap, n);
       int s = 0;
       for (int i = 0; i < n; i++)
           s += va_arg(ap, int);
       va_end(ap);
       return s;
   }
   
   int main(void) {
       int t = sum(3, 4, 5, 6);
       printf("%d\n", t);
   }
   // 15

7. 7.What is tail recursion, and does C optimise it?

   In short: A call is a tail call when it is the last thing a function does; gcc and clang usually turn tail recursion into a loop at -O2, but the C standard never guarantees it.

   In a tail-recursive function the recursive call's result is returned directly, with no pending work after it, so the current frame is no longer needed once the call starts. A compiler can then reuse the frame and turn the recursion into a jump, and gcc and clang usually do so at -O2. The usual factorial, n * fact(n - 1), is not tail recursive, because the multiplication happens after the call returns; carrying an accumulator, as below, makes it tail recursive. Unlike Scheme, C does not promise the optimisation, and debug builds do not perform it, so code that would overflow the stack without it is still broken. When the depth can be large, write the loop yourself.

   long fact(int n, long a) {
       if (n <= 1)
           return a;
       return fact(n - 1, a * n);
   }
   
   int main(void) {
       long f = fact(9, 1);
       printf("%ld\n", f);
   }
   // 362880

How the diagnostic asks it

One question from the C bank, exactly as a sitting would show it. The bank has 4 on functions & recursion and 30 across C.

#include <stdio.h>

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

int main(void) {
    f(3);
}