Recursion & Storage Classes

What is recursion?

A recursive function is one whose body contains a call to itself. Every recursive function needs two parts:

• Base case — the stopping condition; answers directly without recursing
• Recursive case — solves the problem using a smaller input

long fact(int n) {
    if (n <= 1)
        return 1;                  /* base case */
    return n * fact(n - 1);    /* recursive case */
}

Tracing fact(4):

Why recursion?

• Natural fit — some problems are defined recursively (factorial, Fibonacci, trees)
• Shorter, clearer code — mirrors the mathematical definition
• Divide and conquer — split the problem, solve halves, combine (merge sort, binary search)
• No manual stack — the call stack tracks state for you
• Elegant tree/graph traversal — visiting children is just another call

Applications of recursion

Head recursion vs tail recursion

The difference is where the recursive call sits relative to the other work.

Head recursion — the call comes first; work happens while returning:

void headPrint(int n) {
    if (n == 0)
        return;
    headPrint(n - 1);        /* recurse FIRST */
    printf("%d ", n);        /* then do the work */
}
/* headPrint(5) prints: 1 2 3 4 5  (ascending) */

Tail recursion — the work comes first; the call is the last action:

void tailPrint(int n) {
    if (n == 0)
        return;
    printf("%d ", n);        /* do the work FIRST */
    tailPrint(n - 1);        /* then recurse — nothing after */
}
/* tailPrint(5) prints: 5 4 3 2 1  (descending) */

Types of recursion

/* Indirect recursion — each needs the other */
int isOdd(int n);          /* forward prototype */

int isEven(int n) {
    if (n == 0) return 1;
    return isOdd(n - 1);
}

int isOdd(int n) {
    if (n == 0) return 0;
    return isEven(n - 1);
}

Recursion vs iteration

Local vs global variables

#include <stdio.h>

int g = 10;              /* global — visible to all functions */

void show(void) {
    int g = 99;          /* local hides the global inside show() */
    printf("local g = %d\n", g);
}

Scope and lifetime

• Block scope — visible from declaration to the closing }
• Function scope — parameters and locals of one function
• File scope — globals; visible to every function below in the file
• Program (whole-run) lifetime — globals and static variables
• Automatic lifetime — created on entry to the block, destroyed on exit

Types of storage classes

C has four storage class specifiers:

void demo(void) {
    auto int a = 1;      /* default for locals — keyword rarely written */
    register int r = 2;  /* hint only; &r is not allowed */
    static int s = 0;    /* initialized once; survives calls */
    s++;
    printf("a=%d r=%d s=%d\n", a, r, s);
}

static and extern in detail

static local — remembers its value across calls:

void counter(void) {
    static int count = 0;   /* runs only once */
    int plain = 0;             /* reset every call */
    count++; plain++;
    printf("count=%d plain=%d\n", count, plain);
}
/* Three calls print: 1 1 , 2 1 , 3 1 */

extern — refers to a variable defined in another file:

/* file1.c */
int total = 100;          /* definition */

/* file2.c */
extern int total;        /* declaration — no memory allocated here */

Storage classes and recursion

This is where the two topics meet. In a recursive function:

• Automatic locals — each call has its own separate copy in its own frame
• Static locals — one shared copy for all calls, so you can count invocations
• Globals — also shared across all frames and all functions

void rec(int n) {
    static int calls = 0;  /* shared by every frame */
    int local = n;           /* fresh in every frame */

    calls++;
    if (n == 0) {
        printf("total calls = %d\n", calls);
        return;
    }
    rec(n - 1);
    printf("unwinding local = %d\n", local);
}

The call stack during recursion

Each call pushes a frame with its own parameters, locals, and return address. Frames stack up until the base case, then unwind in reverse (LIFO).

• Winding phase — calls go deeper; nothing is computed yet in head recursion
• Base case — the deepest frame returns a concrete value
• Unwinding phase — pending work in each frame completes
• Depth × frame size ≈ stack used; exceeding the limit is a stack overflow

Converting head recursion to tail recursion

Carry the running result in an extra parameter (an accumulator) so nothing remains to do after the call.

/* Head style: multiply waits for the call to return */
long factHead(int n) {
    if (n <= 1) return 1;
    return n * factHead(n - 1);
}

/* Tail style: the call IS the return value */
long factTail(int n, long acc) {
    if (n <= 1) return acc;
    return factTail(n - 1, acc * n);
}
/* call as factTail(5, 1) */

Tail-call optimization — what C guarantees

• Standard C makes no promise about eliminating tail calls
• GCC / Clang often do it with optimization enabled (-O2)
• Without it, tail recursion still uses one frame per call
• For guaranteed constant memory, write an explicit loop

Complexity — linear vs tree recursion

Memoization — caching repeated subproblems

long memo[100];   /* zero-initialized globally */

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

Recursion on arrays and strings

/* Array sum: shrink the length */
int sum(int a[], int n) {
    if (n == 0)
        return 0;
    return a[n - 1] + sum(a, n - 1);
}

/* Palindrome: move both ends inward */
int isPal(char s[], int i, int j) {
    if (i >= j)
        return 1;
    if (s[i] != s[j])
        return 0;
    return isPal(s, i + 1, j - 1);
}

• The array is not copied — only the pointer and index/length change
• Pass indices when you need to work from both ends
• Base cases: empty range (n == 0) or crossed indices (i >= j)

Memory segments — where each storage class lives

Choosing the right storage class

Common mistakes