Recursion

Introduction

Recursion is when a function calls itself. Every recursive function needs a base case to stop.

Understanding the topic

Base case Simplest input — return directly without recursing.

Recursive step Break problem into smaller subproblem.

Stack depth Too deep recursion can overflow the stack.

• Base case — Simplest input — return directly without recursing.
• Recursive step — Break problem into smaller subproblem.
• Stack depth — Too deep recursion can overflow the stack.

Step-by-step explanation

1. Base case — Simplest input — return directly without recursing.
2. Recursive step — Break problem into smaller subproblem.
3. Stack depth — Too deep recursion can overflow the stack.

Informative example

Example program:

#include <stdio.h>

int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

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

120

Execution workflow

Best practices

• Enable warnings: gcc -Wall -Wextra -std=c11 source.c -o app
• Give every variable a defined value before it is read.
• Stay inside array bounds — C will not stop you from over-running a buffer.

Common mistakes

• Reading uninitialized storage — behavior is undefined.
• Dismissing compiler warnings instead of fixing root causes.
• Ignoring NULL returns from malloc, fopen, and similar APIs.

Hands-on exercise

Practice problems:

• Fibonacci with recursion
• Sum 1..n recursively

Summary

Recursion in C — Self-calling functions and mandatory base cases.