What is the difference between call by value and call by reference in C?

Call by value copies the argument — the function gets its own copy, changes don't affect the caller. C only has call by value. Call by reference (simulated in C using pointers) passes the address — the function modifies the original variable through the pointer.

How do you count the number of recursive calls in a function?

Draw the recursion tree — each node is one call. Count total nodes. For T(n)=2T(n-1)+1 (Tower of Hanoi), the tree has 2^n-1 nodes. For T(n)=T(n-1)+T(n-2) (Fibonacci), calls grow exponentially.

What is the maximum depth of recursion limited by?

The call stack size, which is typically 1–8 MB. Each stack frame stores return address, parameters, and local variables. Deep recursion causes stack overflow. The maximum depth is roughly stack_size / frame_size.

Functions and Recursion in C for GATE CS

Q: What is tail recursion and why does it matter?

A function is tail recursive if the recursive call is the very last operation before return (no pending computation after the call). Tail-recursive functions can be optimized by compilers into loops (tail call optimization), using O(1) stack space instead of O(n).

Call stack tracing, parameter passing, tail recursion, recursion trees — everything GATE tests on functions and recursion in C.

Last updated: April 2026 | GATE CS 2024–2026 syllabus

Key Takeaways for GATE

C uses call by value only — functions get copies. Simulate call-by-reference using pointers.
Each function call creates a stack frame storing: return address, parameters, local variables, saved registers.
Tail recursion: recursive call is last operation → compiler can optimise to O(1) stack. Not tail recursive if work done after call.
Count recursive calls using recurrence relations — then solve with Master theorem or unrolling.
Mutual recursion: f() calls g(), g() calls f() — both functions must be declared before use (forward declaration).
Recursion converts to iteration via explicit stack (DFS, tree traversal).
Stack overflow occurs when recursion depth exceeds stack size (~1–8MB typically).

1. Function Basics & Declaration

Function prototype (declaration): return_type name(param_types);
Must appear before first call (or define function before call).

Return type rules:
• Functions return at most one value. Multiple values: use pointers, struct, or global.
• void function: no return value. return; exits early.
• Missing return in non-void: undefined behaviour (compiler may warn).

Inline functions: inline int sq(int x) { return x*x; }
Hint to compiler to replace call with function body — avoids call overhead.

2. Parameter Passing in C

Method	Mechanism	Caller affected?	Example
Call by value	Copy of value	No	`void f(int x)`
Call by pointer	Copy of address	Yes (via *ptr)	`void f(int *x)`
Call by reference (C++)	Alias	Yes (directly)	`void f(int &x)`

Classic swap — by value (WRONG):

void swap(int a, int b) { int t=a; a=b; b=t; }
// caller's variables unchanged — a and b are local copies

Correct swap — by pointer:

void swap(int *a, int *b) { int t=*a; *a=*b; *b=t; }
swap(&x, &y);  // passes addresses, modifies caller's x and y

Array parameter: Arrays always decay to pointer — effectively passed by reference.

3. The Call Stack

Each function call pushes a stack frame (activation record) containing:
• Return address (where to resume after call)
• Arguments (copies)
• Local variables
• Saved register values

Stack grows downward (high address → low address on most architectures).
Stack is LIFO — most recent call is topmost frame.

Stack overflow: Occurs when stack exceeds OS limit (~1–8MB). Common cause: infinite or very deep recursion.
Space complexity of recursion = O(maximum recursion depth) = O(depth of call stack).

4. Recursion Fundamentals

Every recursive function needs:
1. Base case: condition that stops recursion (no recursive call).
2. Recursive case: problem reduced toward base case.
3. Progress: each call must move toward base case.

Factorial:

int fact(int n) {
    if (n == 0) return 1;         // base case
    return n * fact(n-1);         // recursive case, reduces n
}

Time: O(n) — n recursive calls, O(1) work each.
Space: O(n) — n stack frames simultaneously active.

5. Tail Recursion

A recursive call is tail position if it is the last operation — no computation after the call.
Tail-recursive functions can be converted to loops (Tail Call Optimisation, TCO).

NOT tail recursive (pending multiplication):

int fact(int n) { return n * fact(n-1); }
// after fact(n-1) returns, still need to multiply by n

Tail recursive (accumulator pattern):

int fact_tail(int n, int acc) {
    if (n == 0) return acc;
    return fact_tail(n-1, n*acc);  // nothing to do after call returns
}
// TCO converts this to: while(n>0){acc*=n; n--;} return acc;

With TCO: O(1) space. Without TCO: O(n) space (compiler-dependent).

6. Classic Recursive Problems

Problem	Recurrence	Time	Space
Factorial	T(n)=T(n−1)+1	O(n)	O(n)
Fibonacci (naive)	T(n)=T(n−1)+T(n−2)+1	O(2ⁿ)	O(n)
Fibonacci (memo)	O(n) total work	O(n)	O(n)
Binary search	T(n)=T(n/2)+1	O(log n)	O(log n)
Merge sort	T(n)=2T(n/2)+n	O(n log n)	O(n)
Tower of Hanoi	T(n)=2T(n−1)+1	O(2ⁿ)	O(n)
Power xⁿ	T(n)=T(n/2)+1	O(log n)	O(log n)

Tower of Hanoi — minimum moves: 2ⁿ−1 moves for n disks.
T(n) = 2T(n−1)+1. Unroll: T(n) = 2ⁿ−1.

7. Recursion Tree & Counting Calls

Counting calls = counting nodes in recursion tree.

T(n) = 2T(n−1) + 1: binary tree of depth n. Nodes = 2⁰+2¹+…+2ⁿ = 2ⁿ⁺¹−1 = O(2ⁿ).

Naive Fibonacci f(n):

f(5)
├── f(4)
│   ├── f(3) ...
│   └── f(2) ...
└── f(3) ...

f(n) called T(n) times where T(n)=T(n−1)+T(n−2)+1 ≈ φⁿ calls. Exponential!
f(1) called F(n−1) times (Fibonacci number itself!). f(2) called F(n−2) times.

Counting calls to f(k) in naive recursion: f(k) is called F(n−k+1) times when computing f(n).

8. Mutual Recursion

Two functions that call each other. Need forward declaration in C.

int is_even(int n);   // forward declaration
int is_odd(int n) {
    if (n == 0) return 0;
    return is_even(n - 1);
}
int is_even(int n) {
    if (n == 0) return 1;
    return is_odd(n - 1);
}

Depth of call stack for is_even(n): O(n). Time: O(n).
This is tail recursive — compiler can optimise to O(1) space.

9. GATE Examples

GATE 2016 — How many times is f(1) called when computing f(5)?

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

Recurrence: T(n)=2T(n−1). f(1) called 2⁴=16 times (not Fibonacci — both branches call f(n−1)).

GATE 2019 — What is the output?

int f(int n) {
    if (n == 0) return 0;
    return f(n/2) + n%2;
}
printf("%d", f(13));

f(13): f(6)+1. f(6): f(3)+0. f(3): f(1)+1. f(1): f(0)+1=1.
f(1)=1, f(3)=1+1=2, f(6)=2+0=2, f(13)=2+1=3.
This counts number of 1-bits in 13 (binary 1101 = three 1s). Output: 3

GATE 2022 — Space complexity of this recursive function:

void f(int n) {
    if (n <= 0) return;
    f(n/2);
    f(n/2);
    printf("%d", n);
}

Maximum depth: log₂n (each call halves n). Stack depth at any time: O(log n). Space: O(log n).

10. Common Mistakes

Forgetting base case: Omitting or writing wrong base case leads to infinite recursion and stack overflow. Always verify the base case first.
Confusing number of calls with depth: Space complexity = O(max stack depth), not total calls. For Fibonacci f(n): O(2ⁿ) calls but only O(n) depth (longest path in tree).
Tail recursion misidentification: return f(n-1) + 1 is NOT tail recursive — the +1 is pending after return. Only return f(n-1) (with no other computation) is tail position.
Swap by value: void swap(int a, int b) doesn’t swap caller’s variables. Must use int *a, int *b and dereference.
Array passed by value: Arrays decay to pointers when passed — changes inside function affect original array (unlike other call-by-value arguments).

11. FAQ

What is the difference between call by value and call by reference in C?: C only has call by value — the function receives a copy of the argument. Call by reference is simulated by passing a pointer: the function receives a copy of the address, but dereferencing it allows modifying the original. Arrays are an exception — they always decay to pointers, so array contents are always modifiable by the called function.
What is tail recursion and why does it matter?: Tail recursion is when the recursive call is the very last operation performed before returning — there is no pending computation waiting for it. Tail-recursive functions can be compiled into loops (tail call optimization), reducing stack usage from O(n) to O(1). return n * fact(n-1) is NOT tail recursive (multiplication pending); return fact_tail(n-1, n*acc) IS tail recursive.
How do you count the number of recursive calls in a function?: Set up a recurrence relation for the number of calls T(n). Solve using Master theorem or unrolling. Alternatively, draw the recursion tree and count nodes. For f(n)=f(n-1)+f(n-2): exponential calls (~φⁿ). For f(n)=2f(n/2): T(n)=2T(n/2) → polynomial (2n-1 calls for merge sort).
What is the maximum depth of recursion limited by?: The call stack size set by the OS (typically 1–8 MB). Each frame uses memory for the return address, parameters, and local variables. Depth limit ≈ stack_size / frame_size. Deep recursion (e.g., linear recursion on n=100,000) causes stack overflow. Use iteration or tail recursion for deep problems.

Functions and Recursion in C for GATE CS – Complete Guide | EngineeringHulk