← Functions & Recursion

Select a question from the sidebar

15 questions in this topic

Question 1 / 15

What is the difference between function declaration and definition in C?

Function declaration (prototype): Tells the compiler the function's name, return type, and parameter types. Does NOT include the body. Ends with a semicolon.

Function definition: Provides the actual body (implementation) of the function.

Why declarations matter:

In C, you must declare a function before calling it (or define it before the call).
Declarations are typically placed in header files (.h) so multiple source files can use the function.
Without a declaration, C89 assumes the function returns int and accepts any arguments (implicit declaration). C99+ makes implicit declarations an error.

Declaration syntax: return_type function_name(param_types);

Parameter names are optional in declarations: int add(int, int); is valid.
But parameter names in declarations improve readability: int add(int a, int b);.

Pseudo Code

Declaration (prototype):
  int add(int a, int b);   // tells compiler about function

Definition:
  int add(int a, int b) {  // provides the implementation
      return a + b;
  }

1. Declaration before first use (or definition before use)
2. Declarations go in header files (.h)
3. Definitions go in source files (.c)
4. One definition allowed (ODR), multiple declarations OK

Code

#include <stdio.h>

/* Declaration (prototype) -- no body, ends with ; */
int add(int a, int b);
int multiply(int, int);  /* parameter names optional */

int main(void) {
    /* Can call add() and multiply() because they are declared above */
    printf("add(3, 4) = %d\n", add(3, 4));           /* 7 */
    printf("mul(3, 4) = %d\n", multiply(3, 4));       /* 12 */
    return 0;
}

/* Definition -- provides the body */
int add(int a, int b) {
    return a + b;
}

int multiply(int a, int b) {
    return a * b;
}

add(3, 4) = 7
mul(3, 4) = 12

Key Points

•Declaration = signature only (no body, ends with ;)
•Definition = signature + body (the implementation)
•Declare before use; define once in a .c file
•Declarations go in .h files; definitions in .c files
•C99+ requires explicit declaration before calling a function

Gotchas

•C89 allows implicit declarations (assumes int return) -- C99+ makes this an error
•Declaring int f() means f takes UNSPECIFIED parameters, not zero; use int f(void) for zero
•Multiple declarations are fine; multiple definitions cause a linker error
•Forgetting to include the header with the prototype can cause implicit declaration warnings

Declaration = name + return type + param types (no body, ends with ;). Definition = declaration + body. Declare before use. Put declarations in .h files, definitions in .c files. Use f(void) for no parameters.

•Declaration = no body; definition = with body
•Use f(void) for zero parameters

#include <stdio.h>
int add(int a, int b); /* declaration */
int main(void) {
    printf("%d\n", add(3, 4)); /* 7 */
    return 0;
}
int add(int a, int b) { return a + b; } /* definition */

f() means unspecified params, not zero params -- use f(void)

Question 2 / 15

How does pass by value work in C? Does C have pass by reference?

C is strictly pass by value. When you call a function, the argument values are COPIED into the function's parameters. Modifying a parameter inside the function does NOT affect the original variable.

C does NOT have pass by reference (unlike C++ with &). However, you can SIMULATE pass by reference by passing a pointer to the variable. The pointer itself is passed by value, but through it you can modify the original data.

Why this matters:

void swap(int a, int b) cannot swap the caller's variables.
void swap(int *a, int *b) can, because it receives pointers to the originals.
Arrays appear to be passed by reference, but they actually decay to pointers (still pass by value -- the pointer is copied).

Pseudo Code

1. C is ALWAYS pass by value
2. Parameters are copies of the arguments
3. Modifying a parameter does NOT change the original
4. To modify the original: pass a pointer
5. void swap(int *a, int *b) -- pointer passed by value
6. Arrays decay to pointers when passed to functions

Code

#include <stdio.h>

/* This does NOT work: a and b are copies */
void bad_swap(int a, int b) {
    int temp = a;
    a = b;
    b = temp;
    /* only local copies are swapped */
}

/* This works: pointers to originals */
void good_swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

/* Demonstrating that the pointer itself is a copy */
void try_change_ptr(int *p) {
    int local = 99;
    p = &local;  /* only changes the local copy of the pointer */
}

int main(void) {
    int x = 10, y = 20;

    bad_swap(x, y);
    printf("After bad_swap:  x=%d y=%d\n", x, y);  /* x=10 y=20 */

    good_swap(&x, &y);
    printf("After good_swap: x=%d y=%d\n", x, y);  /* x=20 y=10 */

    /* Pointer itself is passed by value */
    int val = 42;
    int *ptr = &val;
    try_change_ptr(ptr);
    printf("ptr still points to: %d\n", *ptr); /* 42, not 99 */

    return 0;
}

After bad_swap:  x=10 y=20
After good_swap: x=20 y=10
ptr still points to: 42

Key Points

•C is always pass by value -- arguments are copied
•To modify the caller's variable, pass a pointer to it
•The pointer itself is still passed by value
•Arrays decay to pointers, giving the illusion of pass by reference
•To change what a pointer points to, pass a pointer to the pointer

Gotchas

•void f(int a) cannot modify the caller's a -- it is a copy
•Even pointers are passed by value: changing the pointer itself inside f does not affect the caller
•To change a pointer in the caller, pass int **p (pointer to pointer)
•Arrays look like pass by reference but are actually pointer decay + pass by value

C is always pass by value. Parameters are copies. To modify the caller's variable, pass a pointer (&x). The pointer itself is also a copy; to change a pointer, pass a pointer-to-pointer.

•C is always pass by value
•Use pointers to simulate pass by reference

#include <stdio.h>
void swap(int *a, int *b) {
    int tmp = *a; *a = *b; *b = tmp;
}
int main(void) {
    int x = 1, y = 2;
    swap(&x, &y);
    printf("x=%d y=%d\n", x, y); /* x=2 y=1 */
    return 0;
}

x=2 y=1

Even pointers are passed by value -- changing the pointer itself does not affect the caller

Question 3 / 15

How do you simulate pass by reference using pointers?

Since C only supports pass by value, you simulate pass by reference by passing the address of a variable (a pointer to it). Inside the function, you dereference the pointer to read or modify the original variable.

Pattern:

Caller: pass &variable (address of variable).
Function: accept type *param (pointer parameter).
Inside function: use *param to access/modify the original.

Common uses:

Swap functions.
Functions that need to return multiple values.
Functions that modify data structures.
Output parameters (a function that fills in a struct or array).

For pointers: If you want to change what a pointer points to, pass a pointer to the pointer (int **pp).

Pseudo Code

1. void modify(int *p) { *p = 42; }  // modify through pointer
2. Caller: int x; modify(&x);         // pass address
3. For pointer modification: void f(int **pp) { *pp = new_addr; }
4. Caller: int *p; f(&p);             // pass address of pointer
5. Output parameters: int parse(const char *s, int *result);

Code

#include <stdio.h>
#include <stdlib.h>

/* Modify a single value */
void set_to_zero(int *p) {
    *p = 0;
}

/* Return multiple values via output parameters */
void divide(int dividend, int divisor, int *quotient, int *remainder) {
    *quotient = dividend / divisor;
    *remainder = dividend % divisor;
}

/* Modify a pointer itself (pointer to pointer) */
void allocate(int **pp, int value) {
    *pp = malloc(sizeof(int));
    if (*pp) {
        **pp = value;
    }
}

int main(void) {
    /* Modify value */
    int x = 42;
    set_to_zero(&x);
    printf("x = %d\n", x); /* 0 */

    /* Multiple return values */
    int q, r;
    divide(17, 5, &q, &r);
    printf("17 / 5 = %d remainder %d\n", q, r); /* 3 remainder 2 */

    /* Modify a pointer */
    int *ptr = NULL;
    allocate(&ptr, 99);
    if (ptr) {
        printf("*ptr = %d\n", *ptr); /* 99 */
        free(ptr);
    }

    return 0;
}

x = 0
17 / 5 = 3 remainder 2
*ptr = 99

Key Points

•Pass &variable to give the function access to the original
•Dereference with *param to read/modify the original value
•Use pointer-to-pointer to modify what a pointer points to
•Output parameters allow returning multiple values from a function
•This is the standard C idiom for simulating pass by reference

Gotchas

•Passing NULL as the address causes undefined behavior when dereferenced
•Always check for NULL before dereferencing output parameters
•The original pointer is not modified if you only pass the pointer (not &pointer)
•Returning a pointer to a local variable is a bug (local dies when function returns)

Pass &variable to the function. Accept type *param. Use *param to modify the original. For pointer modification, use type **pp and pass &pointer.

•Pass address, dereference to modify original
•Common for multiple return values

#include <stdio.h>
void divide(int a, int b, int *q, int *r) {
    *q = a / b;
    *r = a % b;
}
int main(void) {
    int q, r;
    divide(17, 5, &q, &r);
    printf("%d rem %d\n", q, r); /* 3 rem 2 */
    return 0;
}

3 rem 2

Always check for NULL before dereferencing

Question 4 / 15

What are function prototypes and why are they important?

A function prototype is a declaration that specifies the function's return type and parameter types, allowing the compiler to check calls before seeing the definition.

Why prototypes matter:

Type checking: The compiler verifies arguments match parameters.
Implicit conversion: The compiler generates correct type conversions.
Error detection: Catches wrong number of arguments or wrong types at compile time.
Required in C99+: Calling an undeclared function is an error (was just a warning in C89).

Without a prototype (C89):

The compiler assumes the function returns int.
Arguments are passed with default promotions (float -> double, short -> int).
Wrong argument types produce undefined behavior silently.

Important distinction: int f() means unspecified parameters (NOT zero). int f(void) means zero parameters. Always use (void) for no parameters.

Pseudo Code

1. int add(int, int);      // prototype in header or before use
2. int add(int a, int b);  // names optional but good for docs
3. int f(void);            // takes NO parameters
4. int f();                // takes UNSPECIFIED parameters (dangerous!)
5. Put prototypes in .h files for multi-file projects

Code

#include <stdio.h>

/* Prototypes -- allow calling before definition */
int add(int a, int b);
void greet(const char *name);
int no_args(void);  /* void means ZERO parameters */

int main(void) {
    printf("%d\n", add(3, 4));  /* 7 -- compiler checks types */
    greet("World");
    printf("%d\n", no_args());

    /* Without prototype, these errors would be silent: */
    /* add(3.5, "hello"); -- compiler catches type mismatch */
    /* add(1, 2, 3);      -- compiler catches wrong arg count */

    return 0;
}

int add(int a, int b) {
    return a + b;
}

void greet(const char *name) {
    printf("Hello, %s!\n", name);
}

int no_args(void) {
    return 42;
}

7
Hello, World!
42

Key Points

•Prototypes enable compile-time type checking of function calls
•Required in C99+ (implicit declarations are errors)
•Use (void) for zero parameters, not empty ()
•Place prototypes in header files for multi-file projects
•Parameter names in prototypes are optional but improve documentation

Gotchas

•int f() does NOT mean zero parameters in C -- it means unspecified (any number accepted)
•Always write int f(void) when the function takes no parameters
•Without prototypes, float args are promoted to double, causing ABI bugs
•C89 implicit int rule: undeclared functions assumed to return int, hiding type mismatches

A prototype declares return type and parameter types before the function is used. Enables type checking. Required in C99+. Use f(void) for no parameters, not f() which means unspecified.

•Prototypes enable type checking
•f(void) means zero params; f() means unspecified

#include <stdio.h>
int add(int a, int b);  /* prototype */
int main(void) {
    printf("%d\n", add(3, 4)); /* compiler checks types */
    return 0;
}
int add(int a, int b) { return a + b; }

int f() accepts any number of arguments in C, not zero

Question 5 / 15

How do variadic functions work in C (stdarg.h)?

Variadic functions accept a variable number of arguments. They are declared with ... (ellipsis) after at least one fixed parameter.

The <stdarg.h> macros:

va_list -- type for the argument list.
va_start(ap, last_fixed) -- initialize ap after the last fixed parameter.
va_arg(ap, type) -- retrieve the next argument as type.
va_end(ap) -- clean up.
va_copy(dest, src) (C99) -- copy a va_list.

Key rules:

Must have at least one fixed parameter (to anchor va_start).
The caller must indicate how many variable arguments there are (via a count, format string, or sentinel value like NULL).
Type safety is the programmer's responsibility -- there is no compiler checking for variadic arguments.
Default promotions apply: float -> double, char/short -> int.

Pseudo Code

1. int f(int count, ...) { }     // ... = variable args
2. va_list ap;                    // declare argument pointer
3. va_start(ap, count);           // init after last fixed param
4. val = va_arg(ap, int);         // get next arg as int
5. va_end(ap);                    // clean up
6. Caller must tell function how many args (count or sentinel)

Code

#include <stdio.h>
#include <stdarg.h>

/* Sum of n integers */
int sum(int count, ...) {
    va_list ap;
    va_start(ap, count);

    int total = 0;
    for (int i = 0; i < count; i++) {
        total += va_arg(ap, int);
    }

    va_end(ap);
    return total;
}

/* Simple printf-like function */
void my_printf(const char *fmt, ...) {
    va_list ap;
    va_start(ap, fmt);

    for (const char *p = fmt; *p; p++) {
        if (*p == '%' && *(p + 1)) {
            p++;
            switch (*p) {
                case 'd': printf("%d", va_arg(ap, int)); break;
                case 's': printf("%s", va_arg(ap, char *)); break;
                case 'f': printf("%f", va_arg(ap, double)); break;
                default: putchar(*p); break;
            }
        } else {
            putchar(*p);
        }
    }

    va_end(ap);
}

int main(void) {
    printf("sum = %d\n", sum(4, 10, 20, 30, 40)); /* 100 */

    my_printf("Name: %s, Age: %d, GPA: %f\n",
              "Alice", 22, 3.8);

    return 0;
}

sum = 100
Name: Alice, Age: 22, GPA: 3.800000

Key Points

•Use ... in function declaration for variable arguments
•va_start initializes; va_arg retrieves; va_end cleans up
•Must have at least one fixed parameter before ...
•Caller must communicate the number/types of arguments
•No type safety: wrong va_arg type is undefined behavior

Gotchas

•va_arg with wrong type is undefined behavior (no compiler checking)
•Forgetting va_end can cause memory leaks or stack corruption on some platforms
•float is promoted to double in variadic calls: use va_arg(ap, double) not float
•NULL as a variadic argument may not be a null pointer on all platforms: use (void *)NULL

Declare with ... after fixed params. Use va_start/va_arg/va_end from <stdarg.h>. No type safety on variadic arguments. float is promoted to double. Always call va_end.

•va_start / va_arg / va_end for variable arguments
•No type safety on variadic args

#include <stdio.h>
#include <stdarg.h>
int sum(int n, ...) {
    va_list ap;
    va_start(ap, n);
    int total = 0;
    for (int i = 0; i < n; i++) total += va_arg(ap, int);
    va_end(ap);
    return total;
}
int main(void) {
    printf("%d\n", sum(3, 10, 20, 30)); /* 60 */
    return 0;
}

Use va_arg(ap, double) not float (promotion rule)

Question 6 / 15

How does recursion work in C?

Recursion is when a function calls itself. Every recursive function needs:

Base case: A condition that stops the recursion.
Recursive case: The function calls itself with a "smaller" problem.
Progress: Each call must move toward the base case.

How it works internally:

Each call creates a new stack frame with its own local variables.
When the base case is reached, the calls start returning (unwinding the stack).
The return values propagate back up through the chain of calls.

Stack usage: Each recursive call uses stack memory. Very deep recursion can cause stack overflow (typically the stack is 1-8 MB).

Pseudo Code

1. Define base case (stopping condition)
2. Define recursive case (calls self with smaller input)
3. Each call creates a new stack frame
4. Stack unwinds as calls return
5. Must make progress toward base case to avoid infinite recursion

Code

#include <stdio.h>

/* Factorial: n! = n * (n-1)! with 0! = 1 */
int factorial(int n) {
    if (n <= 1) return 1;       /* base case */
    return n * factorial(n - 1); /* recursive case */
}

/* Fibonacci: fib(n) = fib(n-1) + fib(n-2) */
int fibonacci(int n) {
    if (n <= 0) return 0;       /* base case */
    if (n == 1) return 1;       /* base case */
    return fibonacci(n - 1) + fibonacci(n - 2); /* recursive */
}

/* Tracing recursion */
void countdown(int n) {
    if (n < 0) return;          /* base case */
    printf("%d ", n);
    countdown(n - 1);           /* recursive call */
}

int main(void) {
    printf("5! = %d\n", factorial(5));  /* 120 */
    printf("fib(7) = %d\n", fibonacci(7)); /* 13 */

    printf("Countdown: ");
    countdown(5); /* 5 4 3 2 1 0 */
    printf("\n");

    return 0;
}

5! = 120
fib(7) = 13
Countdown: 5 4 3 2 1 0

Key Points

•Every recursion needs a base case and a recursive case
•Each call creates a new stack frame with its own variables
•The stack unwinds as recursive calls return
•Recursion is often simpler than iteration for tree/graph problems
•Must progress toward the base case to terminate

Gotchas

•Missing base case causes infinite recursion and stack overflow
•Naive Fibonacci is O(2^n) -- exponentially slow; use memoization or iteration
•Each recursive call uses stack space -- deep recursion can crash
•Recursion can be slower than iteration due to function call overhead

A function calls itself. Needs: base case (stops recursion), recursive case (smaller problem), progress toward base case. Each call uses a stack frame. Missing base case = stack overflow.

•Base case + recursive case + progress
•Each call uses a stack frame

#include <stdio.h>
int factorial(int n) {
    if (n <= 1) return 1;          /* base case */
    return n * factorial(n - 1);   /* recursive case */
}
int main(void) {
    printf("%d\n", factorial(5)); /* 120 */
    return 0;
}

Missing base case = infinite recursion = stack overflow

Question 7 / 15

What is tail recursion and can C compilers optimize it?

Tail recursion is when the recursive call is the LAST operation in the function -- there is no work left to do after the recursive call returns.

Why it matters: A tail-recursive function can theoretically reuse the same stack frame for each call, converting the recursion into a loop. This is called tail call optimization (TCO).

C and TCO:

The C standard does NOT require TCO.
GCC and Clang perform TCO with optimization enabled (-O2 or higher).
Without optimization, even tail-recursive functions will use stack frames normally.
You cannot rely on TCO in portable C code.

Converting to tail recursion:

Use an accumulator parameter to carry the result.
factorial(n) becomes factorial_tail(n, 1) where the second argument accumulates the product.

Pseudo Code

Non-tail recursive:
  int fact(n) { return n * fact(n-1); }  // multiplication AFTER call

Tail recursive:
  int fact_tail(n, acc) {
    if (n <= 1) return acc;
    return fact_tail(n-1, n*acc);  // call is the LAST thing
  }

TCO: compiler can rewrite as a loop
Not guaranteed by C standard; works with -O2 in GCC/Clang

Code

#include <stdio.h>

/* Non-tail recursive: multiplication after recursive call */
int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);  /* n * ... is done AFTER call returns */
}

/* Tail recursive: call is the last operation */
int factorial_tail(int n, int acc) {
    if (n <= 1) return acc;
    return factorial_tail(n - 1, n * acc); /* nothing after this call */
}

/* Wrapper for clean API */
int factorial_optimized(int n) {
    return factorial_tail(n, 1);
}

/* Tail recursive GCD (naturally tail recursive) */
int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);  /* last operation is the call */
}

int main(void) {
    printf("5! = %d\n", factorial(5));           /* 120 */
    printf("5! = %d\n", factorial_optimized(5));  /* 120 */
    printf("gcd(48,18) = %d\n", gcd(48, 18));    /* 6 */
    return 0;
}

5! = 120
5! = 120
gcd(48,18) = 6

Key Points

•Tail recursion: the recursive call is the very last operation
•Use an accumulator to convert regular recursion to tail recursion
•GCC/Clang optimize tail calls with -O2 or higher
•C standard does not mandate TCO -- it is compiler-dependent
•GCD (Euclidean algorithm) is naturally tail recursive

Gotchas

•n * factorial(n-1) is NOT tail recursive -- multiplication happens after the call
•TCO is not guaranteed -- do not rely on it for correctness in C
•Debug builds (-O0) will NOT apply TCO, so you may still get stack overflow
•Some compilers may optimize non-tail calls into loops too (aggressive optimization)

Tail recursion means the recursive call is the last operation. Compilers can optimize it into a loop (TCO). Use an accumulator parameter. GCC/Clang do TCO with -O2. Not guaranteed by the C standard.

•Recursive call must be the last operation
•TCO requires -O2 in GCC/Clang; not guaranteed by standard

#include <stdio.h>
int fact_tail(int n, int acc) {
    if (n <= 1) return acc;
    return fact_tail(n - 1, n * acc); /* tail call */
}
int main(void) {
    printf("%d\n", fact_tail(5, 1)); /* 120 */
    return 0;
}

n * f(n-1) is NOT tail recursive

Question 8 / 15

When should you choose recursion over iteration?

Choose recursion when:

The problem is naturally recursive (trees, graphs, divide-and-conquer).
Code clarity is more important than performance.
The recursion depth is bounded and small.
The data structure is recursive (linked lists, trees).

Choose iteration when:

Performance is critical (no function call overhead).
The recursion depth could be large (risk of stack overflow).
The problem maps naturally to a loop (linear scan, counting).
Tail recursion cannot be guaranteed by the compiler.

Any recursion can be converted to iteration using an explicit stack (which is essentially what the call stack does). This trades code clarity for stack safety.

Performance comparison:

Iteration: no function call overhead, no stack frame allocation.
Recursion: cleaner code for recursive problems, but slower and stack-limited.

Pseudo Code

Use recursion:
  - Tree traversal (inorder, preorder, postorder)
  - Merge sort, quicksort
  - Directory traversal
  - Parsing nested expressions

Use iteration:
  - Simple counting, summing
  - Linear search
  - Large/unknown depth problems
  - Performance-critical code

Code

#include <stdio.h>

/* Recursive: natural for the problem */
int sum_recursive(int n) {
    if (n <= 0) return 0;
    return n + sum_recursive(n - 1);
}

/* Iterative: more efficient for this simple case */
int sum_iterative(int n) {
    int total = 0;
    for (int i = 1; i <= n; i++) {
        total += i;
    }
    return total;
}

/* Recursive: natural for binary search */
int bsearch_recursive(int arr[], int lo, int hi, int target) {
    if (lo > hi) return -1;
    int mid = lo + (hi - lo) / 2;
    if (arr[mid] == target) return mid;
    if (arr[mid] < target) return bsearch_recursive(arr, mid + 1, hi, target);
    return bsearch_recursive(arr, lo, mid - 1, target);
}

/* Iterative: safer for large arrays */
int bsearch_iterative(int arr[], int n, int target) {
    int lo = 0, hi = n - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

int main(void) {
    printf("sum(100) recursive: %d\n", sum_recursive(100));  /* 5050 */
    printf("sum(100) iterative: %d\n", sum_iterative(100));  /* 5050 */

    int arr[] = {1, 3, 5, 7, 9, 11, 13};
    printf("find 7: idx %d\n", bsearch_recursive(arr, 0, 6, 7));  /* 3 */
    printf("find 7: idx %d\n", bsearch_iterative(arr, 7, 7));     /* 3 */

    return 0;
}

sum(100) recursive: 5050
sum(100) iterative: 5050
find 7: idx 3
find 7: idx 3

Key Points

•Recursion is natural for trees, graphs, and divide-and-conquer
•Iteration is faster and uses less memory
•Any recursion can be converted to iteration with an explicit stack
•Use recursion for clarity; iteration for performance
•Binary search works well both ways; tree traversal is cleaner recursive

Gotchas

•sum_recursive(1000000) will stack overflow; sum_iterative will not
•Naive recursive Fibonacci is O(2^n); iterative is O(n)
•Converting recursion to iteration can make code much harder to read
•Depth-first search on a large graph should use an explicit stack to avoid overflow

Use recursion for naturally recursive problems (trees, divide-and-conquer). Use iteration for simple loops, large depths, and performance-critical code. Any recursion can be converted to iteration with an explicit stack.

•Recursion = clarity; iteration = performance
•Any recursion can become iteration with explicit stack

#include <stdio.h>
/* Recursion: natural for recursive problems */
int power(int base, int exp) {
    if (exp == 0) return 1;
    return base * power(base, exp - 1);
}
/* Iteration: better for performance */
int power_iter(int base, int exp) {
    int result = 1;
    for (int i = 0; i < exp; i++) result *= base;
    return result;
}
int main(void) {
    printf("%d %d\n", power(2, 10), power_iter(2, 10)); /* 1024 1024 */
    return 0;
}

1024 1024

Deep recursion = stack overflow risk

Question 9 / 15

How can deep recursion cause stack overflow?

Each function call pushes a stack frame onto the call stack, containing local variables, parameters, return address, and saved registers. The stack has a fixed size (typically 1-8 MB, depending on OS).

Stack overflow occurs when the stack grows beyond its limit, typically from:

Deep recursion (e.g., processing a million elements recursively).
Large local arrays in recursive functions.
Infinite recursion (missing base case).

Detection:

Segfault (SIGSEGV) is the typical crash signal.
Stack overflow is NOT an exception in C -- there is no try/catch.
Address Sanitizer (-fsanitize=address) can detect stack issues.

Solutions:

Convert to iteration with an explicit stack (heap-allocated).
Increase stack size (OS-dependent: ulimit -s on Linux).
Use tail recursion and hope the compiler optimizes it.
Reduce stack frame size (minimize local variables).

Pseudo Code

Problem: each call uses ~16-64+ bytes of stack
  1000 calls = 16-64 KB
  100000 calls = 1.6-6.4 MB -> stack overflow!

Solutions:
1. Convert to iteration with heap-allocated stack
2. ulimit -s unlimited (Linux)
3. Tail recursion with -O2 (compiler-dependent)
4. Minimize local variables in recursive functions

Code

#include <stdio.h>
#include <stdlib.h>

/* This WILL stack overflow for large n */
int sum_recursive(int n) {
    if (n <= 0) return 0;
    return n + sum_recursive(n - 1);
}

/* Safe iterative version */
long sum_iterative(int n) {
    long total = 0;
    for (int i = 1; i <= n; i++) {
        total += i;
    }
    return total;
}

/* Simulating recursion with explicit stack */
long sum_with_stack(int n) {
    int *stack = malloc(n * sizeof(int));
    if (!stack) return -1;

    int top = 0;
    for (int i = n; i > 0; i--) {
        stack[top++] = i;
    }

    long total = 0;
    while (top > 0) {
        total += stack[--top];
    }

    free(stack);
    return total;
}

int main(void) {
    /* Safe for small n */
    printf("sum(100) = %d\n", sum_recursive(100)); /* 5050 */

    /* Iterative works for any n */
    printf("sum(1000000) = %ld\n", sum_iterative(1000000));

    /* Explicit stack also works for any n */
    printf("sum(1000000) = %ld\n", sum_with_stack(1000000));

    /* DO NOT: sum_recursive(1000000) -- stack overflow! */
    return 0;
}

sum(100) = 5050
sum(1000000) = 500000500000
sum(1000000) = 500000500000

Key Points

•Each recursive call uses stack memory for its frame
•Stack size is limited (typically 1-8 MB)
•Stack overflow causes segfault -- no exception handling in C
•Convert to iteration or use an explicit heap-allocated stack
•Large local arrays in recursive functions worsen the problem

Gotchas

•Stack overflow is not a catchable exception -- it kills the process
•The maximum safe recursion depth depends on stack frame size and OS stack limit
•int arr[10000] inside a recursive function uses 40KB per call
•Tail call optimization is not guaranteed -- do not rely on it for deep recursion

Each recursive call uses stack space. The stack is limited (1-8 MB). Deep recursion causes segfault. Fix: convert to iteration with heap-allocated stack, or increase stack size (ulimit -s).

•Stack is limited; deep recursion overflows it
•Convert to iteration for safety

#include <stdio.h>
/* BAD: will overflow for large n */
int sum(int n) {
    if (n <= 0) return 0;
    return n + sum(n - 1);
}
/* GOOD: iterative version */
long safe_sum(int n) {
    long total = 0;
    for (int i = 1; i <= n; i++) total += i;
    return total;
}
int main(void) {
    printf("%ld\n", safe_sum(1000000));
    return 0;
}

500000500000

Stack overflow causes segfault, not an exception

Question 10 / 15

What are inline functions in C?

The inline keyword (C99) suggests to the compiler that the function body should be inserted at the call site, eliminating function call overhead.

Key points:

inline is a suggestion, not a command -- the compiler may ignore it.
Modern compilers inline functions automatically based on their own analysis (-O2/-O3).
inline is most useful for very small, frequently called functions.

C inline rules (different from C++):

An inline function in C has no external definition by default.
You need a separate extern inline declaration in exactly one translation unit to provide an external definition.
Or use static inline (most common), which avoids linkage issues entirely.

static inline is the recommended approach for C:

Define in the header file.
Each translation unit gets its own copy.
No linkage issues.

Pseudo Code

1. static inline int max(int a, int b) { return a > b ? a : b; }
2. inline is a hint -- compiler decides whether to inline
3. static inline in headers is the safest approach
4. Modern compilers auto-inline with -O2/-O3
5. Best for small, frequently called functions

Code

#include <stdio.h>

/* static inline: recommended approach */
static inline int max(int a, int b) {
    return (a > b) ? a : b;
}

static inline int min(int a, int b) {
    return (a < b) ? a : b;
}

static inline int clamp(int val, int lo, int hi) {
    return min(max(val, lo), hi);
}

int main(void) {
    printf("max(3, 7) = %d\n", max(3, 7));           /* 7 */
    printf("min(3, 7) = %d\n", min(3, 7));           /* 3 */
    printf("clamp(15, 0, 10) = %d\n", clamp(15, 0, 10)); /* 10 */

    /* The compiler may replace these calls with the actual code:
     * int result = (3 > 7) ? 3 : 7;  // instead of calling max() */

    return 0;
}

max(3, 7) = 7
min(3, 7) = 3
clamp(15, 0, 10) = 10

Key Points

•inline suggests inlining -- the compiler can ignore it
•Use static inline for header-file definitions (avoids linkage issues)
•Best for small, frequently called functions
•Modern compilers auto-inline with optimization flags
•C inline rules differ from C++ -- prefer static inline in C

Gotchas

•inline in C does not guarantee inlining -- it is just a hint
•Non-static inline in C requires an extern inline definition in exactly one .c file
•Inlining large functions can increase code size (code bloat)
•static inline in a header means each .c file gets its own copy

inline suggests the compiler insert the function body at the call site. Use static inline in headers for safety. The compiler may ignore inline hints. Best for small, hot functions.

•static inline is the safe approach in C
•Compiler may ignore the hint and decide itself

#include <stdio.h>
static inline int max(int a, int b) {
    return (a > b) ? a : b;
}
int main(void) {
    printf("%d\n", max(3, 7)); /* 7 */
    return 0;
}

inline does not guarantee inlining

Question 11 / 15

What are static functions and why are they useful?

A static function has internal linkage -- it is only visible within the translation unit (source file) where it is defined. Other files cannot call it, even with an extern declaration.

Why use static functions:

Encapsulation: Hide implementation details. Only expose the public API.
Avoid name collisions: Two files can each have static void helper() without conflict.
Optimization: The compiler knows all call sites, enabling better inlining and optimization.
Documentation: Signals to readers that the function is a private helper.

This is C's version of "private" functions. Since C has no classes or namespaces, static at file scope is the primary encapsulation mechanism.

Pseudo Code

1. static void helper(void) { ... }  // only visible in this file
2. void public_api(void) { helper(); }  // calls the static helper
3. Other files cannot see or call helper()
4. Two files can have static functions with the same name
5. static = internal linkage = file-private

Code

#include <stdio.h>

/* Private helper: only visible in this file */
static int square(int x) {
    return x * x;
}

static void print_separator(void) {
    printf("---\n");
}

/* Public function: visible to other files */
void compute_and_print(int n) {
    print_separator();
    for (int i = 1; i <= n; i++) {
        printf("%d^2 = %d\n", i, square(i));
    }
    print_separator();
}

int main(void) {
    compute_and_print(5);
    /* Output:
       ---
       1^2 = 1
       2^2 = 4
       3^2 = 9
       4^2 = 16
       5^2 = 25
       --- */
    return 0;
}

Key Points

•static functions are file-private (internal linkage)
•Cannot be called from other files
•Prevents name collisions between translation units
•Enables better compiler optimization (all call sites known)
•C's equivalent of private methods

Gotchas

•static on a function = internal linkage; static on a local variable = persistent lifetime
•If you put a static function in a header, each .c file gets its own copy
•Unused static functions generate compiler warnings (good for cleanup)
•Cannot take the address of a static function and use it across files (well, technically you can pass it as a callback, but that is unusual)

static functions are file-private. Other files cannot call them. Use for helper functions, avoiding name collisions, and enabling compiler optimizations. C's equivalent of private methods.

•static function = internal linkage = file-private
•Prevents name collisions across files

#include <stdio.h>
static int square(int x) { return x * x; } /* file-private */
int main(void) {
    printf("%d\n", square(5)); /* 25 */
    return 0;
}

static on function vs static on local variable mean different things

Question 12 / 15

What are function pointers and the callback pattern?

A function pointer stores the address of a function, allowing you to call different functions through the same pointer variable.

Declaration syntax: return_type (*pointer_name)(param_types);

The callback pattern: Pass a function pointer as an argument to another function. The receiving function calls the pointed-to function at the appropriate time. This is how C implements higher-order functions.

Common uses:

qsort() and bsearch() in stdlib.h -- accept comparison function pointers.
Event handlers in GUI frameworks.
Plugin/strategy pattern.
Dispatch tables (arrays of function pointers).

Pseudo Code

1. int (*fp)(int, int);           // declare function pointer
2. fp = add;                       // assign function address
3. int result = fp(3, 4);          // call through pointer
4. void sort(arr, n, int (*cmp)(const void*, const void*));  // callback
5. typedef int (*Comparator)(const void*, const void*);  // typedef for clarity

Code

#include <stdio.h>
#include <stdlib.h>

/* Functions with matching signatures */
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; }

/* Higher-order function using callback */
int apply(int (*op)(int, int), int a, int b) {
    return op(a, b);
}

/* qsort comparison callback */
int compare_int(const void *a, const void *b) {
    return (*(const int *)a - *(const int *)b);
}

int main(void) {
    /* Basic function pointer */
    int (*fp)(int, int) = add;
    printf("fp(3, 4) = %d\n", fp(3, 4)); /* 7 */

    fp = mul;
    printf("fp(3, 4) = %d\n", fp(3, 4)); /* 12 */

    /* Callback pattern */
    printf("add: %d\n", apply(add, 10, 3));  /* 13 */
    printf("sub: %d\n", apply(sub, 10, 3));  /* 7 */
    printf("mul: %d\n", apply(mul, 10, 3));  /* 30 */

    /* Dispatch table */
    int (*ops[])(int, int) = {add, sub, mul};
    const char *names[] = {"+", "-", "*"};
    for (int i = 0; i < 3; i++) {
        printf("5 %s 3 = %d\n", names[i], ops[i](5, 3));
    }

    /* qsort with callback */
    int arr[] = {5, 2, 8, 1, 9, 3};
    qsort(arr, 6, sizeof(int), compare_int);
    for (int i = 0; i < 6; i++) printf("%d ", arr[i]);
    printf("\n"); /* 1 2 3 5 8 9 */

    return 0;
}

fp(3, 4) = 7
fp(3, 4) = 12
add: 13
sub: 7
mul: 30
5 + 3 = 8
5 - 3 = 2
5 * 3 = 15
1 2 3 5 8 9

Key Points

•Function pointer: int (*fp)(int, int) declares a pointer to a function
•Callbacks allow passing behavior as an argument
•qsort() is the classic callback example in C
•Dispatch tables (arrays of function pointers) replace switch statements
•Use typedef to make function pointer types readable

Gotchas

•int *fp(int) declares a function returning int*, not a function pointer -- need parens: int (*fp)(int)
•Calling through a NULL function pointer is undefined behavior
•Function pointer types must match exactly -- wrong signature is UB
•Function pointer syntax is confusing -- use typedef for clarity

Function pointer int (*fp)(int, int) stores a function's address. Call with fp(args). Callbacks: pass function pointers as arguments. qsort() is the classic C callback example.

•int (*fp)(int, int) is a function pointer
•Callbacks let you pass behavior as an argument

#include <stdio.h>
int add(int a, int b) { return a + b; }
int sub(int a, int b) { return a - b; }
int apply(int (*op)(int, int), int a, int b) { return op(a, b); }
int main(void) {
    printf("%d\n", apply(add, 5, 3)); /* 8 */
    printf("%d\n", apply(sub, 5, 3)); /* 2 */
    return 0;
}

8
2

int *fp(int) != int (*fp)(int) -- parentheses matter

Question 13 / 15

What are the valid signatures for main() in C?

The C standard defines two valid signatures for main():

1. int main(void) -- no arguments. 2. int main(int argc, char *argv[]) -- command-line arguments.

Return value:

return 0; or return EXIT_SUCCESS; indicates success.
return EXIT_FAILURE; or any non-zero value indicates failure.
In C99+, reaching the end of main without a return statement implicitly returns 0.

Important notes:

void main() is NOT standard C -- some compilers accept it, but it is non-portable.
main must return int.
argv[argc] is guaranteed to be NULL.
argv[0] is typically the program name.
The environment may also support a third parameter: char *envp[] (common extension, not standard).

Pseudo Code

1. int main(void) { return 0; }             // no args
2. int main(int argc, char *argv[]) { ... } // with args
3. return 0 = success; return non-zero = failure
4. void main() is NOT standard C
5. argv[argc] is always NULL
6. C99+: implicit return 0 at end of main

Code

#include <stdio.h>
#include <stdlib.h>

/* Standard main with command-line arguments */
int main(int argc, char *argv[]) {
    printf("Program: %s\n", argv[0]);
    printf("Argument count: %d\n", argc);

    for (int i = 1; i < argc; i++) {
        printf("  argv[%d] = \"%s\"\n", i, argv[i]);
    }

    /* argv[argc] is guaranteed to be NULL */
    if (argv[argc] == NULL) {
        printf("argv[%d] is NULL (guaranteed)\n", argc);
    }

    if (argc < 2) {
        fprintf(stderr, "Usage: %s <name>\n", argv[0]);
        return EXIT_FAILURE;  /* non-zero = error */
    }

    printf("Hello, %s!\n", argv[1]);
    return EXIT_SUCCESS;  /* 0 = success */
}

Program: /var/folders/qz/99sz9qnd1gld4tqq0rgyd41m0000gn/T/tmprbw34lyc
Argument count: 1
argv[1] is NULL (guaranteed)

Key Points

•Two standard signatures: int main(void) and int main(int argc, char *argv[])
•main must return int -- void main() is non-standard
•return 0 or EXIT_SUCCESS for success; EXIT_FAILURE for error
•argv[0] is the program name; argv[argc] is NULL
•C99+ implicitly returns 0 if you reach the end of main

Gotchas

•void main() compiles on some compilers but is NOT standard C
•char **argv and char *argv[] are equivalent in function parameters
•argv[0] may be NULL on some systems if the program name is unavailable
•main() calling itself recursively is legal but highly unusual

Two standard signatures: int main(void) and int main(int argc, char *argv[]). Returns int (0 = success). void main() is non-standard. argv[0] = program name. argv[argc] = NULL.

•int main(void) or int main(int argc, char *argv[])
•void main() is non-standard

#include <stdio.h>
int main(int argc, char *argv[]) {
    for (int i = 0; i < argc; i++)
        printf("argv[%d] = %s\n", i, argv[i]);
    return 0;
}

argv[0] = /var/folders/qz/99sz9qnd1gld4tqq0rgyd41m0000gn/T/tmp6yd5ly_c

void main() is not portable -- always use int main()

Question 14 / 15

How do command-line arguments work (argc and argv)?

When a C program starts, the OS passes command-line arguments through main():

argc (argument count): The number of arguments, including the program name. Always >= 1.

argv (argument vector): An array of C strings (char *). argv[0] is the program name, argv[1] through argv[argc-1] are the actual arguments, and argv[argc] is NULL.

Parsing arguments:

All arguments are strings -- you must convert numbers with atoi(), strtol(), strtod(), etc.
For complex argument parsing, use getopt() (POSIX) or write a custom parser.

Example run: ./prog hello 42 gives argc=3, argv={"./prog", "hello", "42", NULL}.

Pseudo Code

argc = number of arguments (including program name)
argv[0] = program name
argv[1] to argv[argc-1] = user arguments
argv[argc] = NULL

All arguments are strings: use atoi/strtol to convert to int
argc is always >= 1

Code

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(int argc, char *argv[]) {
    /* Basic argument display */
    printf("argc = %d\n", argc);
    for (int i = 0; i < argc; i++) {
        printf("argv[%d] = \"%s\"\n", i, argv[i]);
    }

    /* Simple argument parsing */
    if (argc < 3) {
        fprintf(stderr, "Usage: %s <name> <age>\n", argv[0]);
        return 1;
    }

    const char *name = argv[1];
    int age = atoi(argv[2]);  /* convert string to int */

    printf("Hello %s, you are %d years old.\n", name, age);

    /* Safer conversion with strtol */
    char *endptr;
    long age_safe = strtol(argv[2], &endptr, 10);
    if (*endptr != '\0') {
        fprintf(stderr, "Invalid number: %s\n", argv[2]);
        return 1;
    }
    printf("(safe) age = %ld\n", age_safe);

    /* Check for flags */
    for (int i = 1; i < argc; i++) {
        if (strcmp(argv[i], "--verbose") == 0) {
            printf("Verbose mode enabled\n");
        }
    }

    return 0;
}

argc = 1
argv[0] = "/var/folders/qz/99sz9qnd1gld4tqq0rgyd41m0000gn/T/tmp_5vys8ng"

Key Points

•argc >= 1 always; argv[0] is the program name
•All arguments are C strings -- convert with atoi()/strtol() as needed
•argv[argc] is guaranteed to be NULL
•Use strtol() instead of atoi() for safe integer parsing with error checking
•Use getopt() for complex argument parsing

Gotchas

•atoi() returns 0 on invalid input with no error indication -- use strtol() instead
•argv[0] may include the full path or just the program name (OS-dependent)
•Arguments with spaces must be quoted on the command line: ./prog "hello world"
•argc is int, not size_t -- this is one of the few places C uses int for a count

argc = argument count (always >= 1). argv[0] = program name. argv[1] to argv[argc-1] = arguments. All are strings. Use strtol() to convert to numbers safely.

•argv[0] = program name; argv[argc] = NULL
•All arguments are strings; convert numbers manually

#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[]) {
    if (argc != 3) {
        fprintf(stderr, "Usage: %s <name> <num>\n", argv[0]);
        return 1;
    }
    printf("%s: %d\n", argv[1], atoi(argv[2]));
    return 0;
}

/* Expected Output (run as: ./program Alice 42):
Alice: 42
*/

atoi() gives no error on invalid input -- use strtol()

Question 15 / 15

How does the main() return value affect the program's exit status?

The value returned from main() becomes the program's exit status, which is reported to the OS and can be checked by the calling process (e.g., a shell script).

Convention:

0 (or EXIT_SUCCESS): program succeeded.
Non-zero (or EXIT_FAILURE): program failed.
On POSIX, only the lower 8 bits are used (0-255).

Ways to set exit status:

return value; from main().
exit(value); from anywhere in the program.
_Exit(value); for immediate termination (no cleanup).
C99+: reaching the end of main() without return is equivalent to return 0;.

Shell access: In bash, $? gives the exit status of the last command.

exit() vs return in main():

Both have the same effect in main().
exit() can be called from any function.
exit() calls atexit handlers and flushes stdio buffers.

Pseudo Code

return 0;            // success
return EXIT_SUCCESS;  // same as 0 (from <stdlib.h>)
return EXIT_FAILURE;  // failure (typically 1)
return N;            // POSIX uses only lower 8 bits (0-255)

exit(0);             // from anywhere, calls atexit handlers
_Exit(1);            // immediate, no cleanup

In bash: $? gives the exit status

Code

#include <stdio.h>
#include <stdlib.h>

void cleanup(void) {
    printf("Cleanup called\n");
}

int main(int argc, char *argv[]) {
    /* Register cleanup function */
    atexit(cleanup);

    if (argc < 2) {
        fprintf(stderr, "Error: missing argument\n");
        return EXIT_FAILURE; /* non-zero = error */
        /* Shell: echo $? prints 1 */
    }

    printf("Processing: %s\n", argv[1]);

    /* exit() can be called from anywhere */
    if (argv[1][0] == 'q') {
        printf("Quitting early\n");
        exit(EXIT_SUCCESS); /* calls atexit handlers */
    }

    printf("Done\n");
    return EXIT_SUCCESS; /* 0 = success */
    /* Shell: echo $? prints 0 */

    /* Cleanup called in both cases (atexit) */
}

Cleanup called

Key Points

•return 0 from main = success; non-zero = failure
•EXIT_SUCCESS and EXIT_FAILURE are the portable constants
•exit() can be called from any function, not just main
•atexit() handlers are called by exit() and normal return from main()
•POSIX uses only the lower 8 bits of the exit status (0-255)

Gotchas

•_Exit() and abort() skip atexit handlers and do not flush buffers
•On POSIX, exit(256) appears as exit status 0 (only lower 8 bits)
•Calling exit() from a library function can surprise callers -- prefer returning error codes
•In C99+, reaching end of main without return implicitly returns 0; in C89 it is undefined

return 0 (or EXIT_SUCCESS) = success. Non-zero = failure. exit() works from anywhere and calls atexit handlers. POSIX uses only lower 8 bits. Shell checks with $?.

•0 = success, non-zero = failure
•exit() calls atexit handlers

#include <stdio.h>
#include <stdlib.h>
int main(int argc, char *argv[]) {
    if (argc < 2) {
        fprintf(stderr, "Usage: %s <arg>\n", argv[0]);
        return EXIT_FAILURE; /* echo $? -> 1 */
    }
    printf("OK\n");
    return EXIT_SUCCESS; /* echo $? -> 0 */
}

/* Expected Output (run as: ./program hello):
OK
*/

exit(256) appears as status 0 on POSIX (lower 8 bits only)

Built by onllm.dev

Home GitHub Support awesomePrep