SyntaxPilot
Courses/C Programming/Lesson 27

C Programming · Lesson 27 of 30 · 13 min

Recursion in C

queued

These are the notes for C episode 27. It starts with a question everyone has asked their laptop: how big is this folder? Folders sit inside folders, and nobody knows how deep. The obvious answer, loops, prints the wrong total. You fix it by noticing that the rule uses itself ("a folder's size is its own files plus the size of each folder inside it") and writing a function that calls itself: recursion. Then you see how it works underneath (the call stack and stack frames), crash it twice for real (no base case, and too deep), watch naive Fibonacci hit Time Limit Exceeded and make it instant with memoization, compare recursion with loops, meet tail recursion, use recursion on strings, and finish with the Tower of Hanoi. Every example was compiled with gcc -O2 -Wno-unused-result main.c -o main -lm (gcc 13.3, glibc 2.39, the same command as the SyntaxPilot compiler) and run with an 8-second limit (timeout 8 ./main). The stack limit was the Linux default, 8 MB.

The problem: how big is my Projects folder?

Real-life example. Your disk is almost full and you want the size of your Projects folder. Projects has 5 MB of its own files and two folders inside it, Photos (10 MB) and Code (20 MB). Photos holds Trip (7 MB), and Trip holds Day 1 (3 MB). The real total is 5 + 10 + 20 + 7 + 3 = 45 MB. Real folders can be twenty levels deep, and you don't know the depth in advance.

In C, the five folders are numbered 0 to 4. size[i] is the megabytes of files directly inside folder i, and kids[i] lists up to two subfolders (-1 means "no folder").

Folder Number Own files Subfolders
Projects 0 5 MB 1, 2
Photos 1 10 MB 3
Code 2 20 MB none
Trip 3 7 MB 4
Day 1 4 3 MB none

The obvious way: loops

#include <stdio.h>

// folder i: MB of its own files, and up to 2 subfolders (-1 = none)
int size[] = {5, 10, 20, 7, 3};
int kids[][2] = {{1, 2}, {3, -1}, {-1, -1}, {4, -1}, {-1, -1}};

int main() {
    int total = size[0];
    for (int a = 0; a < 2; a++) {
        int x = kids[0][a];
        if (x == -1) continue;
        total += size[x];
        for (int b = 0; b < 2; b++) {
            int y = kids[x][b];
            if (y == -1) continue;
            total += size[y];
        }
    }
    printf("Projects: %d MB\n", total);
    return 0;
}
Projects: 42 MB

Wrong. Three megabytes are missing.

Why the loops failed

  • Each loop handles one level. Two nested loops reach two levels down: Photos, then Trip.
  • Day 1 is three levels down, so it was never counted.
  • Add a third loop and a four-level folder breaks it again. You can't write one loop per level when you don't know how many levels there are.
  • Say it in words instead: the size of a folder = its own files + the size of each folder inside it. That sentence uses itself: "size of a folder" appears inside its own definition.

Recursion: a function that calls itself

Write the code exactly like the sentence:

#include <stdio.h>

// folder i: MB of its own files, and up to 2 subfolders (-1 = none)
int size[] = {5, 10, 20, 7, 3};
int kids[][2] = {{1, 2}, {3, -1}, {-1, -1}, {4, -1}, {-1, -1}};

int total(int i) {
    if (i == -1) return 0;
    return size[i] + total(kids[i][0]) + total(kids[i][1]);
}

int main() {
    printf("Projects: %d MB\n", total(0));
    return 0;
}
Projects: 45 MB

Correct, and it works for a folder a hundred levels deep without one extra line. total calls total. A function that calls itself is called recursion, and such a function is a recursive function. You already met it twice: insert in the binary search tree (episode 24) and merge_sort (episode 25).

How total(0) unfolds:

total(0) = 5 + total(1) + total(2)
total(1) = 10 + total(3) + total(-1)
total(3) = 7 + total(4) + total(-1)
total(4) = 3 + total(-1) + total(-1) = 3 + 0 + 0 = 3
total(3) = 7 + 3 + 0 = 10
total(1) = 10 + 10 + 0 = 20
total(2) = 20 + 0 + 0 = 20
total(0) = 5 + 20 + 20 = 45

Base case and recursive case

Real-life example: the cinema queue. You're far back in a ticket queue and want to know your number. You ask the person ahead: "what number are you?" They don't know either, so they ask the person ahead of them: the same question, on a shorter queue. The person at the counter doesn't need to ask anyone: "I'm number 1". Then the answers travel back, each person adding 1, until the answer reaches you.

#include <stdio.h>

int ahead(int pos) {
    if (pos == 1) return 1;          // the person at the counter
    return 1 + ahead(pos - 1);       // ask the person ahead, add 1
}

int main() {
    printf("I am number %d\n", ahead(7));
    return 0;
}
I am number 7

Every recursive function has two parts:

Part Meaning Queue Folders
Base case The answer is known without another call, so the function stops the person at the counter: "I'm 1" if (i == -1) return 0; (no folder)
Recursive case Do one small step yourself, and call the same function on a smaller problem ask the person ahead, add 1 size[i] + total(kid) + total(kid)

The rule: every call must move closer to the base case (a shorter queue, a folder one level deeper, a smaller n). If it doesn't, the recursion never stops.

A good habit: write the base case first, at the top of the function.

The call stack and stack frames

Real-life example: a stack of plates. (You built a stack in episode 23: last in, first out.)

Plates In your program
One plate holds one person's food A stack frame: the block of memory for one call, holding its parameters (n), its local variables and the place to return to
Put a plate on top Calling a function pushes a new frame on top
Take the top plate off Returning pops the top frame; the call underneath carries on from where it stopped
Pile too high and it falls over Stack overflow: too many frames, the program crashes (Segmentation fault)

The whole pile of frames is called the call stack. Because each call gets its own frame, each waiting call keeps its own n: they never mix. In episode 14 you learned that the stack is small: on Linux, about 8 MB by default.

Factorial, traced

The factorial of n, written n!, is n × (n - 1) × ... × 2 × 1. So 4! = 4 × 3 × 2 × 1 = 24, and 4! = 4 × 3!. In general n! = n × (n - 1)!, with 1! = 1 as the base case.

fact(4) waits: 4 × fact(3)
  fact(3) waits: 3 × fact(2)
    fact(2) waits: 2 × fact(1)
      fact(1) = 1                 ← base case, the top plate
    fact(2) = 2 × 1 = 2
  fact(3) = 3 × 2 = 6
fact(4) = 4 × 6 = 24

The last call to start is the first one to finish.

#include <stdio.h>

long long fact(int n) {
    if (n == 1) return 1;            // base case
    long long r = n * fact(n - 1);   // recursive case
    printf("fact(%d) = %lld\n", n, r);
    return r;
}

int main() {
    printf("Answer: %lld\n", fact(5));
    return 0;
}
fact(2) = 2
fact(3) = 6
fact(4) = 24
fact(5) = 120
Answer: 120

Each call prints after its inner call comes back, so fact(2) prints first: the plates coming off the stack. long long is used because factorials grow very fast (13! no longer fits in an int; 20! = 2,432,902,008,176,640,000 is the largest that fits in a long long).

No base case: Segmentation fault (stack overflow)

Delete the base case line:

#include <stdio.h>

long long fact(int n) {
    long long r = n * fact(n - 1);   // recursive case
    printf("fact(%d) = %lld\n", n, r);
    return r;
}

int main() {
    printf("Answer: %lld\n", fact(5));
    return 0;
}

It compiles with no error and no warning. Running it prints:

Segmentation fault

(The SyntaxPilot compiler shows Runtime Error (SIGSEGV).) Not a single fact(...) line is printed.

  • Nothing ever says stop: fact(5) calls fact(4), ..., fact(1), fact(0), fact(-1), fact(-2), ...
  • Every call pushes a frame and none returns. Hundreds of thousands of frames fill the 8 MB stack in a fraction of a second.
  • Running out of stack space is called a stack overflow. The operating system stops the program: Segmentation fault.
  • The printf lines come after the recursive call, so none of them ever runs.

A note on -O2. With optimisation, gcc can turn a very simple recursion into a loop. The plain version without a base case, return n * fact(n - 1); and nothing else, does not crash with -O2: gcc turns it into an endless loop and you get Time Limit Exceeded instead. Either way the bug is the same: a missing base case. (In the video the printf after the call forces a real frame per call, so you see the real stack overflow.)

Sum of digits: a lucky number

Real-life example. People add up the digits of a car number plate to get a "lucky number": 4589 → 4 + 5 + 8 + 9 = 26 → 2 + 6 = 8.

#include <stdio.h>

int digit_sum(int n) {
    if (n < 10) return n;
    return n % 10 + digit_sum(n / 10);
}

int lucky(int n) {
    if (n < 10) return n;
    return lucky(digit_sum(n));
}

int main() {
    printf("Digit sum of 4589: %d\n", digit_sum(4589));
    printf("Lucky number: %d\n", lucky(4589));
    return 0;
}
Digit sum of 4589: 26
Lucky number: 8
  • digit_sum: a one-digit number is its own digit sum (base case). Otherwise, the last digit n % 10 plus the digit sum of the rest, n / 10 (recursive case). Each call has one digit fewer, so it gets closer to the base case.
  • lucky keeps applying digit_sum until one digit is left. It calls digit_sum and itself.

Fibonacci: correct, but far too slow

Real-life example: the railway footbridge. You run up the footbridge stairs one or two steps at a time. In how many ways can you climb? Your last move came either from one step below or from two below, so ways(n) = ways(n - 1) + ways(n - 2). Each number is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8, 13, 21, ... These are the Fibonacci numbers: fib(0) = 0, fib(1) = 1, fib(n) = fib(n - 1) + fib(n - 2). (The number of ways to climb n steps is fib(n + 1).)

Straight from the rule:

#include <stdio.h>

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

int main() {
    int n = 40;
    printf("fib(%d) = %lld\n", n, fib(n));
    return 0;
}
fib(40) = 102334155

Correct, after a moment (about 0.2 s on our machine). Change int n = 40; to int n = 50;: Time Limit Exceeded. Ten more, and it can't finish in 8 seconds.

Why so slow? The same work, again and again

fib(5)
├── fib(4)
│   ├── fib(3)
│   │   ├── fib(2) ...
│   │   └── fib(1)
│   └── fib(2) ...
└── fib(3)               ← fib(3) again, from scratch
    ├── fib(2) ...
    └── fib(1)
  • fib(3) is worked out twice, fib(2) three times, and it gets worse as n grows.
  • Every call makes two more calls, so the number of calls grows exponentially: about 1.6 times more for every extra n (the exact count for fib(n) is 2 × fib(n + 1) - 1).
  • fib(40): about 331 million calls. fib(50): about 40.7 billion calls, roughly 120 times more.
  • Yet there are only 51 different questions: fib(0) to fib(50). We answer the same ones billions of times.

Memoization: write it in your notebook

Real-life example. You never redo the same homework sum twice: the first time, you write the answer in your notebook; next time, you just look it up.

Memoization (from memo, a note to remember something) means: save each result the first time you compute it, and before computing, check whether it's already saved.

#include <stdio.h>

long long memo[100];

long long fib(int n) {
    if (n <= 1) return n;
    if (memo[n] != 0) return memo[n];
    memo[n] = fib(n - 1) + fib(n - 2);
    return memo[n];
}

int main() {
    printf("fib(50) = %lld\n", fib(50));
    printf("fib(90) = %lld\n", fib(90));
    return 0;
}
fib(50) = 12586269025
fib(90) = 2880067194370816120

Both instantly.

  • memo is a global array, so it starts as all zeros, and 0 means "not worked out yet" (safe here because only fib(0) is 0, and that is answered by the base case before memo is used).
  • Check first: if (memo[n] != 0) return memo[n];. Otherwise compute once, store in memo[n], return it.
  • Each fib(k) is now computed only once: about 90 real calculations instead of billions. The running time drops from exponential to O(n).
  • long long holds up to about 9.2 × 10¹⁸, so fib(92) is the largest Fibonacci number that fits.

Too deep: when recursion crashes even with a base case

#include <stdio.h>

#define N 1000000
#define MOD 1000000007
long long memo[N + 1];

long long fib(int n) {
    if (n <= 1) return n;
    if (memo[n] != 0) return memo[n];
    memo[n] = (fib(n - 1) + fib(n - 2)) % MOD;
    return memo[n];
}

int main() {
    printf("fib(%d) %% %d = %lld\n", N, MOD, fib(N));
    return 0;
}
Segmentation fault

The answer is enormous, so we keep only the remainder after dividing by 1,000,000,007 (a common trick in programming contests). But it crashes: not because it's slow, but because it's too deep. fib(1000000) calls fib(999999), which calls fib(999998), ... a million frames on the stack at once before the first one returns. The 8 MB stack can't hold them. (With the same program, N = 100000 works and prints fib(100000) % 1000000007 = 911435502; N = 200000 already crashes on our machine.)

The fix: a loop

#include <stdio.h>

#define N 1000000
#define MOD 1000000007

int main() {
    long long a = 0, b = 1;
    for (int i = 0; i < N; i++) {
        long long c = (a + b) % MOD;
        a = b;
        b = c;
    }
    printf("fib(%d) %% %d = %lld\n", N, MOD, a);
    return 0;
}
fib(1000000) % 1000000007 = 918091266

Instant. Keep only the last two numbers, a and b; each step the next one is a + b. One frame, no matter how big N is.

Recursion vs iteration

Repeating work with a loop is called iteration.

// recursion                              // iteration
long long fact(int n) {                   long long fact(int n) {
    if (n == 1) return 1;                     long long r = 1;
    return n * fact(n - 1);                   for (int i = 2; i <= n; i++)
}                                                 r *= i;
                                              return r;
                                          }
Recursion Iteration (loop)
Reads like the rule itself (n! = n × (n - 1)!) step-by-step instructions
Memory one stack frame per call one frame
Depth limit yes: too deep = stack overflow none
Speed a little slower (each call has a cost) usually a little faster
Best for branching problems: folders, trees, splitting in halves (merge sort), Tower of Hanoi, subsets long straight-line repetition: counting, summing, Fibonacci of a million

Rule of thumb: if the depth can reach many thousands, use a loop. If the problem branches, recursion is usually simpler and clearer. Anything written with recursion can be written with a loop (plus, if needed, your own stack, as in episode 23).

Tail recursion, in plain words

In fact, after the inner call returns, there's still work to do: multiply by n. So every frame has to wait.

Another style passes the running answer forward in a parameter, often called acc (accumulator). Real-life example: a chit passed down a row in class: each person adds their part and passes it on; nobody waits for an answer to come back, and the last person announces the total.

#include <stdio.h>

long long sum(int n, long long acc) {
    if (n == 0) return acc;
    return sum(n - 1, acc + n);   // tail call: nothing left to do after it
}

int main() {
    printf("1 + 2 + ... + 100000000 = %lld\n", sum(100000000, 0));
    return 0;
}
1 + 2 + ... + 100000000 = 5000000050000000
  • When the recursive call is the very last thing a function does (nothing left to do after it), it's a tail call, and the function is tail recursive.
  • The caller's frame is no longer needed, so an optimising compiler can replace the call with a jump: a loop in disguise. That's why a hundred million "calls" don't crash with gcc -O2.
  • The C standard does not promise this. The same program compiled with gcc -O0 (no optimisation) crashes with Segmentation fault. For really deep work in C, write the loop yourself.
  • -O2 sometimes does this even for simple non-tail recursion (like n + sum(n - 1)), which is why some missing-base-case bugs show up as Time Limit Exceeded instead of a crash. Don't rely on it either way.

Recursion on arrays and strings

Real-life example. Some names read the same backwards: NAYAN, NAMAN. Such a word is a palindrome. To check one, compare the two ends; if they match, the same job is left on the middle part. When the ends meet, there's nothing left to check: the base case. Reversing a string follows the same pattern: swap the two ends, then reverse the middle.

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

void reverse(char s[], int i, int j) {
    if (i >= j) return;
    char t = s[i];
    s[i] = s[j];
    s[j] = t;
    reverse(s, i + 1, j - 1);
}

int is_pal(char s[], int i, int j) {
    if (i >= j) return 1;
    if (s[i] != s[j]) return 0;
    return is_pal(s, i + 1, j - 1);
}

int main() {
    char s[] = "SyntaxPilot";
    reverse(s, 0, strlen(s) - 1);
    printf("%s\n", s);
    printf("NAYAN: %d\n", is_pal("NAYAN", 0, 4));
    printf("NAMAN: %d\n", is_pal("NAMAN", 0, 4));
    printf("ROHAN: %d\n", is_pal("ROHAN", 0, 4));
    return 0;
}
toliPxatnyS
NAYAN: 1
NAMAN: 1
ROHAN: 0
  • reverse(s, i, j) works on the part from index i to j. Base case: i >= j (zero or one letter left).
  • is_pal returns 1 (true) or 0 (false). It stops early as soon as two ends differ.
  • Both are tail recursive and could easily be loops. They're here to show the pattern: same job, smaller part of the array (i + 1 ... j - 1). The recursive binary search in the practice section uses the same idea.

Mini project: the Tower of Hanoi

The puzzle. Three rods, A, B and C. A stack of disks sits on A, biggest at the bottom. Move the whole stack to C. Rules: move one disk at a time, and never put a bigger disk on a smaller one. B is the helper rod.

The recursive trick for n disks from A to C:

  1. Move the top n - 1 disks from A to B (using C as the helper).
  2. Move the biggest disk from A to C.
  3. Move the n - 1 disks from B onto C (using A as the helper).

Steps 1 and 3 are the same puzzle with one disk fewer. Base case: zero disks, nothing to do.

#include <stdio.h>

void hanoi(int n, char from, char to, char via) {
    if (n == 0) return;
    hanoi(n - 1, from, via, to);
    printf("Move disk %d: %c -> %c\n", n, from, to);
    hanoi(n - 1, via, to, from);
}

unsigned long long moves(int n) {
    if (n == 0) return 0;
    return 2 * moves(n - 1) + 1;
}

int main() {
    hanoi(3, 'A', 'C', 'B');
    printf("3 disks: %llu moves\n", moves(3));
    printf("64 disks: %llu moves\n", moves(64));
    return 0;
}
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
3 disks: 7 moves
64 disks: 18446744073709551615 moves
  • The biggest disk (3) moves exactly once, right in the middle.
  • moves(n) = 2 × moves(n - 1) + 1, which works out to 2ⁿ - 1: 7 for 3 disks, 15 for 4.
  • For 64 disks: 2⁶⁴ - 1 = 18,446,744,073,709,551,615, the largest value of unsigned long long (%llu). At one move per second that's over 500 billion years. Recursion writes it in three lines, but the problem itself is huge.

Common mistakes (and the real messages)

Mistake What you see Why Fix
No base case Segmentation fault (Runtime Error, SIGSEGV); with a plain return n * fact(n - 1); gcc -O2 may give Time Limit Exceeded instead The recursion never stops; the stack overflows Add the base case first: if (n == 1) return 1;
Base case never reached: fact(0) with if (n == 1) warning: iteration 2147483648 invokes undefined behavior [-Waggressive-loop-optimizations] and Time Limit Exceeded n goes 0, -1, -2, ... and never meets 1 if (n <= 1) return 1;
Forgetting return in the recursive case: n * fact(n - 1); No error, no warning with this command: 5! = 1 The result is computed and thrown away; the function returns garbage return n * fact(n - 1);
int for factorial No error: 13! = 1932053504 (the real value is 6,227,020,800) int overflows after 12! long long (good up to 20!)
Naive Fibonacci for big n Time Limit Exceeded at n = 50 Exponentially many repeated calls Memoization, or a loop
Very deep recursion (a million levels) Segmentation fault A million frames don't fit in the 8 MB stack Use a loop
A recursive call that doesn't shrink the problem, e.g. f(n) calling f(n) Segmentation fault or Time Limit Exceeded It never gets closer to the base case Make every call smaller: f(n - 1), n / 10, i + 1
Large local arrays inside a recursive function Segmentation fault at a much smaller depth Every frame carries the whole array Make the array global or malloc it once

Practice

  1. Write power(x, n) (x to the power n, n ≥ 0) with recursion. Then write a fast version that uses xⁿ = (x^(n/2))².
  2. Write recursive binary search: bin_search(a, lo, hi, key) on a sorted array (episode 25 did it with a loop).
  3. Print all subsets of {a, b, c}. Hint: for each item, either leave it out or take it.
  4. Sum an array recursively: sum(a, n) = sum(a, n - 1) + a[n - 1].
Solutions

All four, verified together:

#include <stdio.h>

long long power(long long x, int n) {
    if (n == 0) return 1;
    return x * power(x, n - 1);
}

long long fast_power(long long x, int n) {
    if (n == 0) return 1;
    long long half = fast_power(x, n / 2);
    if (n % 2 == 0) return half * half;
    return half * half * x;
}

int bin_search(int a[], int lo, int hi, int key) {
    if (lo > hi) return -1;
    int mid = lo + (hi - lo) / 2;
    if (a[mid] == key) return mid;
    if (a[mid] < key) return bin_search(a, mid + 1, hi, key);
    return bin_search(a, lo, mid - 1, key);
}

void subsets(char items[], int n, int i, char chosen[], int k) {
    if (i == n) {
        printf("{");
        for (int j = 0; j < k; j++) printf(j ? ", %c" : "%c", chosen[j]);
        printf("}\n");
        return;
    }
    subsets(items, n, i + 1, chosen, k);        // leave items[i] out
    chosen[k] = items[i];
    subsets(items, n, i + 1, chosen, k + 1);    // take items[i]
}

int sum(int a[], int n) {
    if (n == 0) return 0;
    return sum(a, n - 1) + a[n - 1];
}

int main() {
    printf("2^10 = %lld\n", power(2, 10));
    printf("3^39 = %lld\n", fast_power(3, 39));
    int a[] = {11, 23, 35, 47, 59};
    printf("59 at %d, 50 at %d\n", bin_search(a, 0, 4, 59), bin_search(a, 0, 4, 50));
    char items[] = {'a', 'b', 'c'}, chosen[3];
    subsets(items, 3, 0, chosen, 0);
    printf("sum = %d\n", sum(a, 5));
    return 0;
}
2^10 = 1024
3^39 = 4052555153018976267
59 at 4, 50 at -1
{}
{c}
{b}
{b, c}
{a}
{a, c}
{a, b}
{a, b, c}
sum = 175
  • 1. power makes n calls: O(n). fast_power halves n each call, so it makes about log₂ n calls: O(log n). 3^39 takes about 6 levels instead of 39. Compute half once and reuse it; calling fast_power(x, n / 2) twice would bring back the repeated work.
  • 2. The same lo, mid, hi as episode 25; the loop is replaced by a call on the half that can still contain the key. Base case: lo > hi → not found.
  • 3. Each item gives two branches (out, in), so 3 items give 2³ = 8 subsets, including the empty set {}. n items give 2ⁿ.
  • 4. Base case: an empty array sums to 0.

Quick quiz

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

// main calls f(3);
  • A. 3 2 1
  • B. 1 2 3
  • C. 3 2 1 0
  • D. nothing
Answer

B: 1 2 3 (verified: the program prints 1 2 3). f(3) calls f(2), which calls f(1), which calls f(0), the base case, which returns without printing. Then the frames come off the stack: f(1) prints 1, f(2) prints 2, f(3) prints 3. If the printf came before the recursive call, the output would be 3 2 1.

Interview questions

  • What is recursion? What are the base case and the recursive case?
  • What happens in memory when a function calls itself? What is a stack frame?
  • What is a stack overflow, and how can recursion cause one?
  • Write factorial recursively and iteratively. Which would you use for n = 1,000,000 (with a modulus)?
  • Why is the naive recursive Fibonacci exponential? How does memoization make it O(n)?
  • What is the difference between memoization (top-down) and a bottom-up loop (tabulation)?
  • What is tail recursion? Does C guarantee tail-call optimisation? (No.)
  • Can every recursive function be written with a loop? (Yes, possibly with an explicit stack.)
  • Solve the Tower of Hanoi. How many moves for n disks, and why? (2ⁿ - 1.)
  • Print all subsets (or permutations) of a set. How many are there?
  • Check whether a string is a palindrome recursively.
  • Compute xⁿ in O(log n).

Glossary

Term Meaning Example
Recursion A function that calls itself, each time on a smaller version of the problem total calls total
Recursive function A function that uses recursion long long fact(int n)
Base case The case answered directly, without another call; it stops the recursion if (n == 1) return 1;
Recursive case Do one small step and call the function on a smaller problem return n * fact(n - 1);
Call stack The pile of stack frames for all calls that haven't returned yet main → fact(5) → fact(4) ...
Stack frame The block of stack memory for one call: parameters, local variables, return address each fact call's own n and r
Push / pop Put a frame on top (a call) / take the top frame off (a return) last in, first out
Stack overflow Running out of stack space, usually from recursion that is endless or too deep Segmentation fault
Segmentation fault The operating system stops a program that touched memory it may not use missing base case
SIGSEGV The signal behind a segmentation fault; the compiler shows "Runtime Error (SIGSEGV)"
Time Limit Exceeded The online compiler stopped a program that ran longer than 8 seconds fib(50) naive
Factorial n! = n × (n - 1) × ... × 1 5! = 120
Digit sum The sum of a number's digits 4589 → 26
Fibonacci numbers Each number is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8 ... fib(50) = 12586269025
Exponential growth The work multiplies by a constant factor for every +1 in n naive fib: about ×1.6 per n
Memoization Save each result the first time; look it up after that memo[n]
Iteration Repeating work with a loop for (int i = 0; i < N; i++)
Tail call A call that is the very last thing a function does return sum(n - 1, acc + n);
Tail recursion Recursion where the recursive call is a tail call sum(n, acc)
Accumulator (acc) A parameter that carries the running answer forward acc + n
Tail-call optimisation The compiler turns a tail call into a jump (a loop); C does not guarantee it gcc -O2
Palindrome A word that reads the same backwards NAYAN, NAMAN
Tower of Hanoi Puzzle: move a stack of disks between three rods, one at a time, never big on small 2ⁿ - 1 moves
Subset Any selection of items from a set, including none or all {a, c} of {a, b, c}
long long / %lld A 64-bit signed integer and its printf specifier fib(90)
unsigned long long / %llu A 64-bit non-negative integer, up to 2⁶⁴ - 1 moves(64)
MOD (1,000,000,007) Keep only the remainder after dividing, so huge answers fit % MOD

Summary

  • When a problem contains a smaller copy of itself (folders in folders, a shorter queue, n! = n × (n - 1)!), loops get ugly or wrong and recursion fits: a function that calls itself.
  • Every recursion needs a base case (stop) and a recursive case (one step + a smaller problem), and every call must get closer to the base case.
  • Each call gets its own stack frame on the call stack; returns happen last-in, first-out.
  • No base case, or a base case that's never reached → endless recursion: Segmentation fault (stack overflow), or Time Limit Exceeded when gcc -O2 turns it into a loop.
  • Naive Fibonacci repeats the same calls exponentially often (Time Limit Exceeded at n = 50); memoization stores each answer once and makes it instant.
  • Even correct recursion crashes when it's too deep (a million levels in an 8 MB stack). Use a loop for deep, straight-line work; use recursion for branching problems.
  • A tail call is the last thing a function does; gcc -O2 may turn it into a loop, but C doesn't promise it.
  • Recursion on arrays works on a smaller part each time (i + 1 ... j - 1): reverse, palindrome, binary search.
  • Tower of Hanoi: move n - 1, move the biggest, move n - 1 again: 2ⁿ - 1 moves.

Next episode: Capstone: a student record system, putting the whole C course together in one real program.