Recursion is one of the most elegant and powerful concepts in computer science—a function that calls itself to solve problems by breaking them down into smaller, similar subproblems. From traversing trees to implementing divide-and-conquer algorithms, recursion is indispensable. This comprehensive guide explores recursion in C, covering fundamentals, optimization techniques, and advanced patterns.

What is Recursion?

Recursion is a programming technique where a function calls itself to solve a problem. Every recursive solution consists of two essential parts:

1. Base Case: The condition that stops the recursion
2. Recursive Case: The function calling itself with modified parameters

factorial(5)
= 5 * factorial(4)
= 5 * (4 * factorial(3))
= 5 * (4 * (3 * factorial(2)))
= 5 * (4 * (3 * (2 * factorial(1))))
= 5 * (4 * (3 * (2 * 1)))
= 120

The Anatomy of Recursion

1. Basic Recursive Structure

#include <stdio.h>
#include <stdlib.h>
// Simple recursive function
int factorial(int n) {
// Base case
if (n <= 1) {
return 1;
}
// Recursive case
return n * factorial(n - 1);
}
// Visualizing recursion
void print_recursion_depth(int n, int depth) {
// Indent to show recursion depth
for (int i = 0; i < depth; i++) {
printf("  ");
}
printf("factorial(%d) called\n", n);
if (n <= 1) {
for (int i = 0; i < depth; i++) {
printf("  ");
}
printf("factorial(%d) returning 1\n", n);
return;
}
int result = n * factorial(n - 1);
for (int i = 0; i < depth; i++) {
printf("  ");
}
printf("factorial(%d) returning %d\n", n, result);
}
int main() {
printf("=== Recursive Factorial Demo ===\n");
print_recursion_depth(5, 0);
printf("\nResult: %d\n", factorial(5));
return 0;
}

2. Multiple Recursive Calls (Fibonacci)

// Naive Fibonacci - multiple recursive calls
long long fibonacci(int n) {
if (n <= 1) {
return n;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
// This creates a recursive tree:
//                    fib(5)
//                  /        \
//              fib(4)        fib(3)
//             /    \        /    \
//         fib(3)  fib(2)  fib(2) fib(1)
//         /   \   /   \   /   \
//     fib(2) fib(1) ... and so on
void print_fib_tree(int n, int depth) {
for (int i = 0; i < depth; i++) printf("  ");
printf("fib(%d)\n", n);
if (n <= 1) return;
print_fib_tree(n - 1, depth + 1);
print_fib_tree(n - 2, depth + 1);
}

Classic Recursive Algorithms

1. Binary Search

#include <stdio.h>
#include <stdbool.h>
// Recursive binary search
int binary_search(int arr[], int left, int right, int target) {
if (left > right) {
return -1;  // Base case: element not found
}
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;  // Base case: found
}
else if (arr[mid] > target) {
return binary_search(arr, left, mid - 1, target);  // Search left
}
else {
return binary_search(arr, mid + 1, right, target);  // Search right
}
}
// Generic binary search for any type
typedef int (*compare_func)(const void*, const void*);
void* generic_binary_search(void *arr, size_t size, size_t elem_size,
void *target, compare_func cmp) {
if (size == 0) return NULL;
size_t mid = size / 2;
void *mid_ptr = (char*)arr + mid * elem_size;
int result = cmp(target, mid_ptr);
if (result == 0) {
return mid_ptr;
}
else if (result < 0) {
return generic_binary_search(arr, mid, elem_size, target, cmp);
}
else {
return generic_binary_search((char*)mid_ptr + elem_size,
size - mid - 1, elem_size, target, cmp);
}
}

2. Merge Sort

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// Merge two sorted subarrays
void merge(int arr[], int left, int mid, int right) {
int left_size = mid - left + 1;
int right_size = right - mid;
// Create temporary arrays
int *left_arr = (int*)malloc(left_size * sizeof(int));
int *right_arr = (int*)malloc(right_size * sizeof(int));
if (!left_arr || !right_arr) {
fprintf(stderr, "Memory allocation failed\n");
exit(1);
}
// Copy data
memcpy(left_arr, arr + left, left_size * sizeof(int));
memcpy(right_arr, arr + mid + 1, right_size * sizeof(int));
// Merge back
int i = 0, j = 0, k = left;
while (i < left_size && j < right_size) {
if (left_arr[i] <= right_arr[j]) {
arr[k++] = left_arr[i++];
} else {
arr[k++] = right_arr[j++];
}
}
// Copy remaining elements
while (i < left_size) arr[k++] = left_arr[i++];
while (j < right_size) arr[k++] = right_arr[j++];
free(left_arr);
free(right_arr);
}
// Recursive merge sort
void merge_sort(int arr[], int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
// Recursively sort both halves
merge_sort(arr, left, mid);
merge_sort(arr, mid + 1, right);
// Merge the sorted halves
merge(arr, left, mid, right);
}
}
// Optimized merge sort with threshold for small arrays
void merge_sort_optimized(int arr[], int left, int right) {
const int THRESHOLD = 32;
if (right - left + 1 <= THRESHOLD) {
// Use insertion sort for small arrays
for (int i = left + 1; i <= right; i++) {
int key = arr[i];
int j = i - 1;
while (j >= left && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
return;
}
int mid = left + (right - left) / 2;
merge_sort_optimized(arr, left, mid);
merge_sort_optimized(arr, mid + 1, right);
merge(arr, left, mid, right);
}

3. Quick Sort

// Partition function
int partition(int arr[], int low, int high) {
int pivot = arr[high];  // Choose last element as pivot
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
// Swap arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// Swap pivot into correct position
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
// Recursive quick sort
void quick_sort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
// Recursively sort elements before and after partition
quick_sort(arr, low, pi - 1);
quick_sort(arr, pi + 1, high);
}
}
// Optimized quick sort with tail recursion elimination
void quick_sort_optimized(int arr[], int low, int high) {
while (low < high) {
int pi = partition(arr, low, high);
// Recursively sort the smaller partition first
if (pi - low < high - pi) {
quick_sort_optimized(arr, low, pi - 1);
low = pi + 1;  // Tail recursion for right part
} else {
quick_sort_optimized(arr, pi + 1, high);
high = pi - 1;  // Tail recursion for left part
}
}
}

Tree Traversal Algorithms

#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
// Create a new node
TreeNode* create_node(int data) {
TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
}
// Insert into BST
TreeNode* insert_bst(TreeNode* root, int data) {
if (root == NULL) {
return create_node(data);
}
if (data < root->data) {
root->left = insert_bst(root->left, data);
} else if (data > root->data) {
root->right = insert_bst(root->right, data);
}
return root;
}
// Inorder traversal (Left-Root-Right)
void inorder_traversal(TreeNode* root) {
if (root != NULL) {
inorder_traversal(root->left);
printf("%d ", root->data);
inorder_traversal(root->right);
}
}
// Preorder traversal (Root-Left-Right)
void preorder_traversal(TreeNode* root) {
if (root != NULL) {
printf("%d ", root->data);
preorder_traversal(root->left);
preorder_traversal(root->right);
}
}
// Postorder traversal (Left-Right-Root)
void postorder_traversal(TreeNode* root) {
if (root != NULL) {
postorder_traversal(root->left);
postorder_traversal(root->right);
printf("%d ", root->data);
}
}
// Find height of tree
int tree_height(TreeNode* root) {
if (root == NULL) {
return -1;  // Height of empty tree is -1
}
int left_height = tree_height(root->left);
int right_height = tree_height(root->right);
return (left_height > right_height ? left_height : right_height) + 1;
}
// Count nodes
int count_nodes(TreeNode* root) {
if (root == NULL) return 0;
return 1 + count_nodes(root->left) + count_nodes(root->right);
}
// Check if tree is balanced
int is_balanced(TreeNode* root) {
if (root == NULL) return 1;
int left_height = tree_height(root->left);
int right_height = tree_height(root->right);
if (abs(left_height - right_height) > 1) return 0;
return is_balanced(root->left) && is_balanced(root->right);
}
// Find Lowest Common Ancestor
TreeNode* find_lca(TreeNode* root, int n1, int n2) {
if (root == NULL) return NULL;
// If both values are smaller, LCA is in left subtree
if (n1 < root->data && n2 < root->data) {
return find_lca(root->left, n1, n2);
}
// If both values are larger, LCA is in right subtree
if (n1 > root->data && n2 > root->data) {
return find_lca(root->right, n1, n2);
}
// Current node is the LCA
return root;
}

Backtracking Algorithms

1. N-Queens Problem

#include <stdio.h>
#include <stdbool.h>
#define N 8
// Print the board
void print_board(int board[N][N]) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
printf("%c ", board[i][j] ? 'Q' : '.');
}
printf("\n");
}
printf("\n");
}
// Check if a queen can be placed at board[row][col]
bool is_safe(int board[N][N], int row, int col) {
int i, j;
// Check this row on left side
for (i = 0; i < col; i++) {
if (board[row][i]) return false;
}
// Check upper diagonal on left side
for (i = row, j = col; i >= 0 && j >= 0; i--, j--) {
if (board[i][j]) return false;
}
// Check lower diagonal on left side
for (i = row, j = col; i < N && j >= 0; i++, j--) {
if (board[i][j]) return false;
}
return true;
}
// Solve N-Queens using backtracking
bool solve_nqueens(int board[N][N], int col) {
// Base case: all queens placed
if (col >= N) {
return true;
}
// Try placing queen in each row of current column
for (int i = 0; i < N; i++) {
if (is_safe(board, i, col)) {
board[i][col] = 1;  // Place queen
// Recur to place rest of queens
if (solve_nqueens(board, col + 1)) {
return true;
}
board[i][col] = 0;  // Backtrack
}
}
return false;
}
// Count all solutions
int count_nqueens(int board[N][N], int col) {
if (col >= N) {
return 1;  // Found a solution
}
int count = 0;
for (int i = 0; i < N; i++) {
if (is_safe(board, i, col)) {
board[i][col] = 1;
count += count_nqueens(board, col + 1);
board[i][col] = 0;
}
}
return count;
}

2. Sudoku Solver

#include <stdio.h>
#include <stdbool.h>
#define SIZE 9
#define BOX_SIZE 3
// Check if number can be placed at position
bool is_valid_sudoku(int board[SIZE][SIZE], int row, int col, int num) {
// Check row
for (int i = 0; i < SIZE; i++) {
if (board[row][i] == num) return false;
}
// Check column
for (int i = 0; i < SIZE; i++) {
if (board[i][col] == num) return false;
}
// Check 3x3 box
int box_row = row - row % BOX_SIZE;
int box_col = col - col % BOX_SIZE;
for (int i = 0; i < BOX_SIZE; i++) {
for (int j = 0; j < BOX_SIZE; j++) {
if (board[box_row + i][box_col + j] == num) return false;
}
}
return true;
}
// Find next empty cell
bool find_empty_cell(int board[SIZE][SIZE], int *row, int *col) {
for (*row = 0; *row < SIZE; (*row)++) {
for (*col = 0; *col < SIZE; (*col)++) {
if (board[*row][*col] == 0) {
return true;
}
}
}
return false;
}
// Solve Sudoku using backtracking
bool solve_sudoku(int board[SIZE][SIZE]) {
int row, col;
// Base case: no empty cells
if (!find_empty_cell(board, &row, &col)) {
return true;
}
// Try numbers 1-9
for (int num = 1; num <= SIZE; num++) {
if (is_valid_sudoku(board, row, col, num)) {
board[row][col] = num;
if (solve_sudoku(board)) {
return true;
}
board[row][col] = 0;  // Backtrack
}
}
return false;
}
void print_sudoku(int board[SIZE][SIZE]) {
for (int i = 0; i < SIZE; i++) {
if (i % BOX_SIZE == 0 && i != 0) {
printf("------+-------+------\n");
}
for (int j = 0; j < SIZE; j++) {
if (j % BOX_SIZE == 0 && j != 0) {
printf("| ");
}
printf("%d ", board[i][j]);
}
printf("\n");
}
}

3. Permutations and Combinations

#include <stdio.h>
#include <stdbool.h>
// Generate all permutations of an array
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
void permutations(int arr[], int start, int end) {
if (start == end) {
// Print permutation
for (int i = 0; i <= end; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return;
}
for (int i = start; i <= end; i++) {
swap(&arr[start], &arr[i]);
permutations(arr, start + 1, end);
swap(&arr[start], &arr[i]);  // Backtrack
}
}
// Generate combinations (choose k elements from n)
void combinations(int arr[], int n, int k, int start, int current, int result[]) {
if (current == k) {
// Print combination
for (int i = 0; i < k; i++) {
printf("%d ", result[i]);
}
printf("\n");
return;
}
for (int i = start; i < n; i++) {
result[current] = arr[i];
combinations(arr, n, k, i + 1, current + 1, result);
}
}
// Generate all subsets (power set)
void subsets(int arr[], int n, int index, int current[], int current_size) {
// Print current subset
printf("{ ");
for (int i = 0; i < current_size; i++) {
printf("%d ", current[i]);
}
printf("}\n");
// Generate subsets with remaining elements
for (int i = index; i < n; i++) {
current[current_size] = arr[i];
subsets(arr, n, i + 1, current, current_size + 1);
}
}

Divide and Conquer Algorithms

1. Maximum Subarray (Kadane's Algorithm - Recursive)

#include <limits.h>
// Structure to hold result
typedef struct {
int left;
int right;
int sum;
} Subarray;
// Find maximum crossing subarray
Subarray max_crossing_subarray(int arr[], int low, int mid, int high) {
Subarray result;
int left_sum = INT_MIN;
int right_sum = INT_MIN;
int sum = 0;
// Find maximum sum in left half
for (int i = mid; i >= low; i--) {
sum += arr[i];
if (sum > left_sum) {
left_sum = sum;
result.left = i;
}
}
// Find maximum sum in right half
sum = 0;
for (int i = mid + 1; i <= high; i++) {
sum += arr[i];
if (sum > right_sum) {
right_sum = sum;
result.right = i;
}
}
result.sum = left_sum + right_sum;
return result;
}
// Find maximum subarray using divide and conquer
Subarray max_subarray_dc(int arr[], int low, int high) {
if (low == high) {
Subarray result = {low, high, arr[low]};
return result;
}
int mid = low + (high - low) / 2;
Subarray left = max_subarray_dc(arr, low, mid);
Subarray right = max_subarray_dc(arr, mid + 1, high);
Subarray cross = max_crossing_subarray(arr, low, mid, high);
if (left.sum >= right.sum && left.sum >= cross.sum) return left;
else if (right.sum >= left.sum && right.sum >= cross.sum) return right;
else return cross;
}

2. Exponentiation (Power Function)

// Naive recursive power
long long power_naive(long long base, int exp) {
if (exp == 0) return 1;
return base * power_naive(base, exp - 1);
}
// Optimized power using exponentiation by squaring
long long power_fast(long long base, int exp) {
if (exp == 0) return 1;
long long half = power_fast(base, exp / 2);
if (exp % 2 == 0) {
return half * half;
} else {
return base * half * half;
}
}
// Iterative version for comparison
long long power_iterative(long long base, int exp) {
long long result = 1;
while (exp > 0) {
if (exp & 1) result *= base;
base *= base;
exp >>= 1;
}
return result;
}

Dynamic Programming with Memoization

1. Memoized Fibonacci

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
long long *memo = NULL;
void init_memo(int n) {
memo = (long long*)calloc(n + 1, sizeof(long long));
if (!memo) {
fprintf(stderr, "Memory allocation failed\n");
exit(1);
}
// Initialize with -1 to indicate not computed
for (int i = 0; i <= n; i++) {
memo[i] = -1;
}
}
// Memoized Fibonacci
long long fib_memoized(int n) {
if (n <= 1) return n;
if (memo[n] != -1) {
return memo[n];
}
memo[n] = fib_memoized(n - 1) + fib_memoized(n - 2);
return memo[n];
}
// Clean up
void cleanup_memo() {
free(memo);
memo = NULL;
}

2. Longest Common Subsequence (LCS)

#include <string.h>
#include <stdlib.h>
int **lcs_memo = NULL;
int lcs_length(const char *s1, const char *s2, int i, int j) {
if (i == 0 || j == 0) return 0;
if (lcs_memo[i][j] != -1) {
return lcs_memo[i][j];
}
if (s1[i - 1] == s2[j - 1]) {
lcs_memo[i][j] = 1 + lcs_length(s1, s2, i - 1, j - 1);
} else {
int a = lcs_length(s1, s2, i - 1, j);
int b = lcs_length(s1, s2, i, j - 1);
lcs_memo[i][j] = (a > b) ? a : b;
}
return lcs_memo[i][j];
}
// Initialize memo table
void init_lcs_memo(int len1, int len2) {
lcs_memo = (int**)malloc((len1 + 1) * sizeof(int*));
for (int i = 0; i <= len1; i++) {
lcs_memo[i] = (int*)malloc((len2 + 1) * sizeof(int));
for (int j = 0; j <= len2; j++) {
lcs_memo[i][j] = -1;
}
}
}
// Free memo table
void cleanup_lcs_memo(int len1) {
for (int i = 0; i <= len1; i++) {
free(lcs_memo[i]);
}
free(lcs_memo);
}
// Build LCS string
char* build_lcs(const char *s1, const char *s2, int i, int j) {
if (i == 0 || j == 0) {
return strdup("");
}
if (s1[i - 1] == s2[j - 1]) {
char *sub = build_lcs(s1, s2, i - 1, j - 1);
char *result = (char*)malloc(strlen(sub) + 2);
strcpy(result, sub);
result[strlen(sub)] = s1[i - 1];
result[strlen(sub) + 1] = '\0';
free(sub);
return result;
}
if (lcs_memo[i - 1][j] > lcs_memo[i][j - 1]) {
return build_lcs(s1, s2, i - 1, j);
} else {
return build_lcs(s1, s2, i, j - 1);
}
}

Tail Recursion Optimization

#include <stdio.h>
// Non-tail recursive factorial
int factorial_non_tail(int n) {
if (n <= 1) return 1;
return n * factorial_non_tail(n - 1);  // Multiplication after call
}
// Tail recursive factorial
int factorial_tail(int n, int accumulator) {
if (n <= 1) return accumulator;
return factorial_tail(n - 1, n * accumulator);  // Recursive call is last
}
// Wrapper
int factorial_optimized(int n) {
return factorial_tail(n, 1);
}
// Tail recursive sum
int sum_tail(int n, int accumulator) {
if (n == 0) return accumulator;
return sum_tail(n - 1, accumulator + n);
}
// Tail recursive reverse string
void reverse_tail(char *str, int left, int right) {
if (left >= right) return;
// Swap characters
char temp = str[left];
str[left] = str[right];
str[right] = temp;
// Tail recursive call
reverse_tail(str, left + 1, right - 1);
}
// Compiler optimization hint
#ifdef __GNUC__
#define TAIL_CALL __attribute__((musttail))
#else
#define TAIL_CALL
#endif
int factorial_with_hint(int n, int acc) {
if (n <= 1) return acc;
TAIL_CALL return factorial_with_hint(n - 1, n * acc);
}

Recursive Data Structures

1. Recursive Linked List Operations

#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* next;
} Node;
Node* create_node(int data) {
Node* node = (Node*)malloc(sizeof(Node));
node->data = data;
node->next = NULL;
return node;
}
// Recursive list traversal
void print_list_recursive(Node* head) {
if (head == NULL) {
printf("NULL\n");
return;
}
printf("%d -> ", head->data);
print_list_recursive(head->next);
}
// Recursive list reversal
Node* reverse_list_recursive(Node* head) {
if (head == NULL || head->next == NULL) {
return head;
}
Node* new_head = reverse_list_recursive(head->next);
head->next->next = head;
head->next = NULL;
return new_head;
}
// Recursive list length
int length_recursive(Node* head) {
if (head == NULL) return 0;
return 1 + length_recursive(head->next);
}
// Recursive search
Node* search_recursive(Node* head, int target) {
if (head == NULL) return NULL;
if (head->data == target) return head;
return search_recursive(head->next, target);
}
// Recursive delete
Node* delete_recursive(Node* head, int target) {
if (head == NULL) return NULL;
if (head->data == target) {
Node* next = head->next;
free(head);
return next;
}
head->next = delete_recursive(head->next, target);
return head;
}
// Recursive merge of two sorted lists
Node* merge_sorted_recursive(Node* a, Node* b) {
if (a == NULL) return b;
if (b == NULL) return a;
if (a->data <= b->data) {
a->next = merge_sorted_recursive(a->next, b);
return a;
} else {
b->next = merge_sorted_recursive(a, b->next);
return b;
}
}

2. Recursive Array Operations

#include <stdio.h>
#include <limits.h>
// Recursive array sum
int array_sum(int arr[], int n) {
if (n == 0) return 0;
return arr[n - 1] + array_sum(arr, n - 1);
}
// Recursive array max
int array_max(int arr[], int n) {
if (n == 1) return arr[0];
int max_rest = array_max(arr, n - 1);
return (arr[n - 1] > max_rest) ? arr[n - 1] : max_rest;
}
// Recursive linear search
int linear_search_recursive(int arr[], int n, int target) {
if (n == 0) return -1;
if (arr[n - 1] == target) return n - 1;
return linear_search_recursive(arr, n - 1, target);
}
// Recursive array reversal
void reverse_array_recursive(int arr[], int left, int right) {
if (left >= right) return;
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
reverse_array_recursive(arr, left + 1, right - 1);
}
// Check if array is sorted
int is_sorted_recursive(int arr[], int n) {
if (n <= 1) return 1;
if (arr[n - 2] > arr[n - 1]) return 0;
return is_sorted_recursive(arr, n - 1);
}

Recursion Depth and Stack Overflow

#include <stdio.h>
#include <setjmp.h>
#include <signal.h>
#include <stdlib.h>
// Detect recursion depth
int recursive_depth_count(int n, int depth) {
printf("Depth: %d, n: %d\n", depth, n);
if (n <= 0) return 0;
return n + recursive_depth_count(n - 1, depth + 1);
}
// Stack limit check
void check_stack_limit(int *depth) {
int dummy;
(*depth)++;
// Rough estimate: stack grows downward, difference between &dummy and &depth
// This is platform-dependent and not portable
printf("Depth: %d, stack address: %p\n", *depth, &dummy);
check_stack_limit(depth);
}
// Alternative: use iterative approach for deep recursion
long long factorial_iterative(int n) {
long long result = 1;
for (int i = 2; i <= n; i++) {
result *= i;
}
return result;
}
// Use a custom stack for deep recursion
typedef struct {
int n;
long long result;
int stage;
} Frame;
long long factorial_simulated_stack(int n) {
Frame stack[1000];
int top = 0;
// Initial frame
stack[top].n = n;
stack[top].result = 0;
stack[top].stage = 0;
while (top >= 0) {
Frame *current = &stack[top];
if (current->stage == 0) {
if (current->n <= 1) {
current->result = 1;
top--;  // Pop frame
} else {
// Push new frame
current->stage = 1;
top++;
stack[top].n = current->n - 1;
stack[top].result = 0;
stack[top].stage = 0;
}
} else {
// Stage 1: combine results
current->result = current->n * stack[top + 1].result;
top--;  // Pop current frame
}
}
return stack[0].result;
}

Performance Comparison

#include <time.h>
#include <stdio.h>
void benchmark_recursion() {
const int ITERATIONS = 10000;
clock_t start, end;
double time_taken;
// Test recursive factorial
start = clock();
for (int i = 0; i < ITERATIONS; i++) {
factorial_tail(10, 1);
}
end = clock();
time_taken = ((double)(end - start)) / CLOCKS_PER_SEC;
printf("Tail recursive: %f seconds\n", time_taken);
// Test iterative factorial
start = clock();
for (int i = 0; i < ITERATIONS; i++) {
factorial_iterative(10);
}
end = clock();
time_taken = ((double)(end - start)) / CLOCKS_PER_SEC;
printf("Iterative: %f seconds\n", time_taken);
// Test Fibonacci (memoized vs naive)
init_memo(40);
start = clock();
for (int i = 0; i < 100; i++) {
fib_memoized(40);
}
end = clock();
time_taken = ((double)(end - start)) / CLOCKS_PER_SEC;
printf("Memoized Fibonacci: %f seconds\n", time_taken);
cleanup_memo();
}

Best Practices for Recursive Algorithms

Common Pitfalls

// PITFALL 1: Missing base case
int bad_factorial(int n) {
// Missing base case!
return n * bad_factorial(n - 1);  // Infinite recursion!
}
// PITFALL 2: Not progressing toward base case
int bad_countdown(int n) {
if (n <= 0) return 0;
// n never changes! Infinite recursion
return bad_countdown(n);  // Wrong!
}
// PITFALL 3: Double recursion causing exponential blowup
int fib_naive(int n) {
if (n <= 1) return n;
// Exponential time complexity O(2^n)
return fib_naive(n - 1) + fib_naive(n - 2);
}
// PITFALL 4: Stack overflow with deep recursion
void deep_recursion(int n) {
// May cause stack overflow for large n (e.g., n=100000)
if (n <= 0) return;
deep_recursion(n - 1);
}
// PITFALL 5: Not handling NULL pointers
void print_tree_bad(TreeNode* root) {
printf("%d ", root->data);  // Segfault if root is NULL
print_tree_bad(root->left);
print_tree_bad(root->right);
}
// CORRECT version
void print_tree_good(TreeNode* root) {
if (root == NULL) return;
printf("%d ", root->data);
print_tree_good(root->left);
print_tree_good(root->right);
}

Complete Example: Expression Evaluator

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
typedef struct {
char *expr;
int position;
} Parser;
// Forward declarations
double parse_expression(Parser *p);
double parse_term(Parser *p);
double parse_factor(Parser *p);
// Skip whitespace
void skip_whitespace(Parser *p) {
while (p->expr[p->position] && isspace(p->expr[p->position])) {
p->position++;
}
}
// Parse a number
double parse_number(Parser *p) {
skip_whitespace(p);
char *start = p->expr + p->position;
char *end;
double value = strtod(start, &end);
p->position += (end - start);
return value;
}
// Parse a factor (number or parenthesized expression)
double parse_factor(Parser *p) {
skip_whitespace(p);
if (p->expr[p->position] == '(') {
p->position++;  // Skip '('
double result = parse_expression(p);
skip_whitespace(p);
if (p->expr[p->position] == ')') {
p->position++;  // Skip ')'
}
return result;
}
return parse_number(p);
}
// Parse a term (* and /)
double parse_term(Parser *p) {
double result = parse_factor(p);
skip_whitespace(p);
while (p->expr[p->position] == '*' || p->expr[p->position] == '/') {
char op = p->expr[p->position];
p->position++;
double next = parse_factor(p);
if (op == '*') {
result *= next;
} else {
if (next == 0) {
fprintf(stderr, "Division by zero\n");
exit(1);
}
result /= next;
}
skip_whitespace(p);
}
return result;
}
// Parse an expression (+ and -)
double parse_expression(Parser *p) {
double result = parse_term(p);
skip_whitespace(p);
while (p->expr[p->position] == '+' || p->expr[p->position] == '-') {
char op = p->expr[p->position];
p->position++;
double next = parse_term(p);
if (op == '+') {
result += next;
} else {
result -= next;
}
skip_whitespace(p);
}
return result;
}
// Evaluate expression
double evaluate(const char *expr) {
Parser p = { (char*)expr, 0 };
return parse_expression(&p);
}
int main() {
printf("=== Recursive Descent Parser Demo ===\n\n");
const char *tests[] = {
"3 + 4 * 2",
"(3 + 4) * 2",
"10 / 2 + 3 * 4",
"((3 + 4) * (5 - 2)) / 3",
"2 * (3 + 4 * (5 - 2))"
};
int num_tests = sizeof(tests) / sizeof(tests[0]);
for (int i = 0; i < num_tests; i++) {
double result = evaluate(tests[i]);
printf("%s = %.2f\n", tests[i], result);
}
return 0;
}

Conclusion

Recursion is a powerful paradigm that enables elegant solutions to complex problems. From mathematical computations to tree traversals, backtracking algorithms, and language parsing, recursion is an essential tool in every C programmer's arsenal.

Key takeaways:

• Always define base cases to prevent infinite recursion
• Ensure progress toward base cases in recursive calls
• Consider tail recursion for compiler optimization
• Use memoization for overlapping subproblems
• Be mindful of stack depth and consider iterative alternatives
• Test with small inputs before scaling up
• Profile performance to identify optimization opportunities

When used appropriately, recursion leads to code that is both elegant and efficient. The patterns and techniques in this guide will help you harness the full power of recursive algorithms in your C programs.