Programming Language & Its Applications — Introduction to C Programming, NEC licence examination syllabus (Nepal Engineering Council).
Recursive Functions: a function that calls itself
Every recursion needs a base case and progress towards it — miss either and you get a stack overflow.
Recursion expresses a problem in terms of a smaller version of itself. It is not a performance technique — an iterative version is usually faster and uses less memory. Its value is clarity: tree traversals, divide-and-conquer sorts, and grammar parsing are dramatically shorter recursively. To use it safely you must understand what the call stack does on every call.
🌍 Where this lives: stack overflow — the condition, not the website — is what happens when recursion runs too deep, and it has real consequences. A maliciously deep-nested JSON document can crash a naive recursive parser, which is a genuine denial-of-service vulnerability that gets CVE numbers assigned every year. The good side is everywhere too: every time you compute a folder's total size, something is recursing through subdirectories. Try "tail call optimisation" next — some compilers turn a recursive function back into a loop and eliminate the stack cost entirely.
The two mandatory ingredients
Every correct recursive function has:
1. BASE CASE — a condition where it returns WITHOUT
calling itself. This stops the recursion.
2. RECURSIVE STEP — a call to itself on a SMALLER input,
so the base case is eventually reached.
Missing base case → infinite recursion → stack overflow
Not shrinking the input → infinite recursion → stack overflow
int bad(int n) { return bad(n - 1); } /* no base case */
int bad2(int n){ if(n==0) return 1;
return bad2(n); } /* n never shrinks */
factorial.c
#include <stdio.h>
long fact_rec(int n) {
if (n <= 1) return 1; /* BASE CASE */
return n * fact_rec(n - 1); /* RECURSIVE STEP */
}
long fact_iter(int n) {
long r = 1;
for (int i = 2; i <= n; i++) r *= i;
return r;
}
int main(void) {
for (int i = 0; i <= 10; i++)
printf("%2d! = %-8ld (iter %ld)\n",
i, fact_rec(i), fact_iter(i));
return 0;
}
Output:
0! = 1 (iter 1)
1! = 1 (iter 1)
5! = 120 (iter 120)
10! = 3628800 (iter 3628800)
Worked example 1 — tracing the stack
fact_rec(4) unwinds like this. Each call PUSHES a frame
onto the stack and waits:
fact_rec(4) → 4 * fact_rec(3) [frame 1 waiting]
fact_rec(3) → 3 * fact_rec(2) [frame 2 waiting]
fact_rec(2) → 2 * fact_rec(1) [frame 3 waiting]
fact_rec(1) → 1 BASE CASE reached
Then the frames POP, each completing its multiplication:
fact_rec(1) returns 1
fact_rec(2) returns 2 * 1 = 2
fact_rec(3) returns 3 * 2 = 6
fact_rec(4) returns 4 * 6 = 24 ← final answer
Peak stack depth = 4 frames.
Each frame holds: parameter n, the return address, and
saved registers — roughly 32-64 bytes on a typical x86-64
machine.
For fact_rec(100000) that is ~3-6 MB of stack — most
systems default to 8 MB, so you are close to a crash.
Worked example 2 — Fibonacci, and why naive recursion is terrible
fib.c
#include <stdio.h>
long calls = 0;
long fib(int n) {
calls++;
if (n <= 1) return n;
return fib(n-1) + fib(n-2); /* TWO calls per level */
}
long fib_iter(int n) {
long a = 0, b = 1;
for (int i = 0; i < n; i++) { long t = a + b; a = b; b = t; }
return a;
}
int main(void) {
for (int n = 10; n <= 40; n += 10) {
calls = 0;
long v = fib(n);
printf("fib(%2d)=%-10ld calls=%-12ld iter=%ld\n",
n, v, calls, fib_iter(n));
}
return 0;
}
Output:
fib(10)=55 calls=177 iter=55
fib(20)=6765 calls=21891 iter=6765
fib(30)=832040 calls=2692537 iter=832040
fib(40)=102334155 calls=331160281 iter=102334155
Naive fib does REDUNDANT work. fib(5) computes fib(3)
twice, fib(2) three times:
fib(5)
/ \
fib(4) fib(3) ← fib(3) computed again
/ \ / \
fib(3) fib(2) fib(2) fib(1)
/ \
fib(2) fib(1)
Number of calls ≈ 2 · fib(n+1) − 1, which grows as
φⁿ where φ ≈ 1.618. So:
Recursive Fibonacci: O(φⁿ) ≈ O(1.618ⁿ) EXPONENTIAL
Iterative Fibonacci: O(n) LINEAR
fib(40) recursive = 331 million calls, several seconds.
fib(40) iterative = 40 additions, instantaneous.
That is a ratio of about 8 million to one.
This is the key insight about recursion: it is a expressiveness tool, not a speed tool. Naive recursion on overlapping subproblems is catastrophically slow. The fix is memoisation (cache computed values) or dynamic programming (build up iteratively) — which is exactly the bridge into the DSA syllabus.
Worked example 3 — Tower of Hanoi
hanoi.c
#include <stdio.h>
int moves = 0;
void hanoi(int n, char from, char to, char via) {
if (n == 1) { /* base */
printf("move disk 1: %c -> %c\n", from, to);
moves++;
return;
}
hanoi(n-1, from, via, to); /* n-1 out of the way */
printf("move disk %d: %c -> %c\n", n, from, to);
moves++;
hanoi(n-1, via, to, from); /* n-1 onto the target */
}
int main(void) {
int n = 3;
hanoi(n, 'A', 'C', 'B');
printf("total moves = %d (2^%d - 1 = %d)\n",
moves, n, (1 << n) - 1);
return 0;
}
Output:
move disk 1: A -> C
move disk 2: A -> B
move disk 1: C -> B
move disk 3: A -> C
move disk 1: B -> A
move disk 2: B -> C
move disk 1: A -> C
total moves = 7 (2^3 - 1 = 7)
The recurrence for Hanoi:
T(1) = 1
T(n) = 2·T(n−1) + 1
Solving: T(n) = 2ⁿ − 1
n = 3 → 7 moves
n = 10 → 1023 moves
n = 20 → 1048575 moves
n = 64 → 1.8 × 10¹⁹ moves
At one move per second, 64 disks takes about 585 BILLION
years. This is the legend of the Brahmin priests — and a
concrete demonstration of what exponential growth means.
Note: unlike Fibonacci, Hanoi's exponential cost is
INHERENT — the answer itself has 2ⁿ−1 moves, so no
algorithm can do better. Fibonacci's was WASTE.
💡 Exam angle: be ready to (a) state the two requirements — base case and progress; (b) trace the stack for factorial or Fibonacci, showing push and pop order; (c) compare recursive vs iterative complexity, using naive Fibonacci's O(φⁿ) vs O(n) as the example; (d) derive Hanoi's T(n) = 2ⁿ − 1 from its recurrence. Also know that every recursion can be converted to iteration using an explicit stack.
Syllabus points
Recursion; trace & output (numerical)
Create a free account to tick topics off, take notes as you read, watch the video lessons and get a day-by-day study plan built around your exam date.