C - Recursive Functions

Recursion is a technique where a function solves a problem by calling itself on smaller subproblems, and combining those results. It’s essential for problems with natural self-similarity (trees, divide-and-conquer, backtracking).

Learning Objectives

• Recognize problems that suit recursion (divide-and-conquer, tree/graph traversal, backtracking).
• Design correct recursive functions with clear base cases and progress.
• Trace the call stack; reason about time/space complexity and stack depth.
• Compare recursive vs iterative approaches and understand tail recursion.

Prerequisites

• C - Functions
• C - Looping Statements (for comparison)
• C - Pointers (for tree/linked list examples)

How Recursion Works

• Base case: a minimal input where the answer is known directly.
• Recursive case: reduce the problem to smaller subproblems and call the same function.
• Progress: each call moves toward the base case (e.g., n-1).

// Template
ResultType f(Input x) {
  if (is_base_case(x)) return base_answer;
  smaller = reduce(x);
  partial = f(smaller);
  return combine(partial);
}

Visualizing the Call Stack (factorial 4!)

fact(4)
  ↳ 4 * fact(3)
       ↳ 3 * fact(2)
            ↳ 2 * fact(1)
                 ↳ 1 (base)
Unwind: 2*1=2 → 3*2=6 → 4*6=24

Classic Examples

Factorial (simple)

#include <stdio.h>

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

int main(void) { printf("%d\n", fact(5)); }

Factorial (tail-recursive style)

Tail recursion puts the recursive call last; some compilers can optimize it, but tail-call optimization is not guaranteed in C. Don’t rely on it for eliminating stack usage.

int fact_tail(int n, int acc) {
  if (n <= 1) return acc;
  return fact_tail(n - 1, n * acc);
}

int fact_tr(int n) { return fact_tail(n, 1); }

Fibonacci (naive vs improved)

int fib(int n) {                     // O(phi^n): exponential
  if (n < 2) return n;
  return fib(n-1) + fib(n-2);
}

int fib_iter(int n) {                // O(n), iterative
  int a = 0, b = 1;
  for (int i = 0; i < n; i++) { int t = a + b; a = b; b = t; }
  return a;
}

Divide and Conquer

Binary Search (recursive)

#include <stdio.h>

int bsearch_rec(const int *a, int lo, int hi, int key) {
  if (lo > hi) return -1;                 // base: not found
  int mid = lo + (hi - lo) / 2;
  if (a[mid] == key) return mid;          // base: found
  if (key < a[mid]) return bsearch_rec(a, lo, mid - 1, key);
  else               return bsearch_rec(a, mid + 1, hi, key);
}

Quicksort (reference implementation)

#include <stdio.h>

void swap(int *x, int *y) { int t = *x; *x = *y; *y = t; }
int partition(int *a, int lo, int hi) {
  int pivot = a[hi], i = lo;
  for (int j = lo; j < hi; j++) if (a[j] < pivot) swap(&a[i++], &a[j]);
  swap(&a[i], &a[hi]); return i;
}
void quicksort(int *a, int lo, int hi) {
  if (lo >= hi) return; // base
  int p = partition(a, lo, hi);
  quicksort(a, lo, p - 1);
  quicksort(a, p + 1, hi);
}

Recursive Data Structures

Linked List (sum)

struct Node { int val; struct Node *next; };
int sum_list(const struct Node *n) {
  if (!n) return 0;              // base
  return n->val + sum_list(n->next);
}

Binary Tree Traversal

struct T { int v; struct T *l, *r; };
void inorder(const struct T *t) {
  if (!t) return;
  inorder(t->l);
  printf("%d ", t->v);
  inorder(t->r);
}

Backtracking (generate all subsets)

#include <stdio.h>

void subsets(const int *a, int n, int i, int *cur, int k) {
  if (i == n) {
    printf("{"); for (int j = 0; j < k; j++) printf("%s%d", j?", ":"", cur[j]); printf("}\n");
    return;
  }
  // exclude a[i]
  subsets(a, n, i + 1, cur, k);
  // include a[i]
  cur[k] = a[i];
  subsets(a, n, i + 1, cur, k + 1);
}

Complexity and Limits

• Time/space: derive recurrences; consider call depth and extra memory.
• Stack overflow: deep recursion can crash; prefer iteration or manual stacks if depth is large.
• Tail recursion: may reduce stack in some languages/compilers, but not guaranteed in C.

Common Pitfalls

• Missing/incorrect base case → infinite recursion.
• No progress toward base case (e.g., calling with same argument).
• Exponential blowup (e.g., naive Fibonacci). Consider memoization/iteration.

Checks for Understanding

1. Identify the base and recursive cases in fact and bsearch_rec.
2. Why is naive Fibonacci exponential? How to improve it?
3. When should you avoid recursion in C?

Practice Exercises

1. Sum of array recursively: int sum(const int *a, int n).
   Solution

   int sum(const int *a, int n){ return (n==0)?0 : a[n-1]+sum(a,n-1);} 

2. Reverse a string in place recursively.
   Solution

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

3. Fast power by squaring: double powi(double x, int n).
   Solution

   double powi(double x,int n){ if(n==0) return 1; if(n<0) return 1.0/powi(x,-n); double h=powi(x,n/2); return (n%2)? h*h*x : h*h; } 

Recurrence relations and the Master theorem (high level)

Many divide-and-conquer algorithms have runtimes that follow a recurrence of the form T(n) = a T(n/b) + f(n):

• a: number of subproblems; b: factor by which the problem size shrinks; f(n): cost to divide/combine.
• Master theorem (intuition):
  • Let n^{log_b a} be the “tree size.” Compare f(n) to n^{log_b a}.
  • If f(n) is smaller (polynomially), T(n) = Θ(n^{log_b a}).
  • If they match (within polylog factors), T(n) = Θ(n^{log_b a} log n).
  • If f(n) is larger (polynomially) and “regular,” T(n) = Θ(f(n)).

Examples:

• Binary search: T(n) = T(n/2) + Θ(1) → a=1, b=2, n^{log_b a} = n^0 = 1. Since f(n)=Θ(1) matches, result is Θ(log n).
• Mergesort: T(n) = 2 T(n/2) + Θ(n) → a=2, b=2, n^{log_b a}=n. f(n)=Θ(n) matches → Θ(n log n).
• Quicksort (average): T(n) = T(n/2) + T(n/2) + Θ(n) (≈ mergesort) → Θ(n log n).

Memoization patterns in C

Memoization stores results of subproblems to avoid recomputation. In C, simple cases use arrays (dense domains). For sparse domains, consider hash tables (custom or library-based).

Array-based memo (Fibonacci)

#include <stdio.h>

int fib_memo(int n, int memo[]) {
  if (n < 2) return n;
  if (memo[n] != -1) return memo[n];
  memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo);
  return memo[n];
}

int main(void) {
  enum { N = 46 };                 // fits in 32-bit int
  int memo[N+1];
  for (int i = 0; i <= N; i++) memo[i] = -1;  // sentinel
  printf("%d\n", fib_memo(N, memo));
}

Hash-table memo (sketch)

For non-dense keys (e.g., multiple parameters), use a map from a composite key to result. In pure C, you can:

• Use a simple open-addressing table with a struct key (e.g., pair of ints) and sentinel states (EMPTY, USED).
• Or bring a small hash-map implementation and wrap lookups in get_or_compute().

// Pseudocode outline
// struct Key { int x, y; };
// struct Entry { struct Key k; int value; int state; };
// int lookup_or_insert(struct Entry *tab, size_t cap, struct Key k, int (*compute)(int,int)) {
//   size_t i = hash(k) % cap; for (...) { probe... if match return value; if empty, compute & store; }
// }

When to memoize

• Overlapping subproblems (e.g., naive DP like Fibonacci, edit distance).
• Tree/graph traversals where subtrees repeat (with cycle checks).
• Be mindful of memory usage; clear tables if they grow without bound.

Capstone Challenge

Implement a recursive quicksort that handles duplicates well (e.g., 3-way partitioning), or solve a maze using DFS backtracking. Compare recursion depth and performance against iterative variants.