Part 3 · Lesson 19
Recursion
On this page
What you'll learn: recursion: functions that call themselves, base cases, recursive steps, and the danger of stack overflow.
Before you start: Lessons 7 and 8.
So far, when you've needed to repeat a task, you've used a loop (for or while).
Today, we're going to learn a powerful and elegant alternative: RECURSION.
What Is Recursion?
RECURSION is the process of a function calling itself.
Think of it like a set of Russian nesting dolls. You open a doll to find a slightly smaller doll inside. You open that one to find an even smaller one, and so on, until you reach the smallest, solid doll that can't be opened.
In programming, a recursive function works the same way. It has two essential parts:
-
THE BASE CASE: This is the condition that STOPS the recursion. It's the "smallest doll" that doesn't call itself again. Without a base case, a recursive function would call itself forever, leading to a crash. This is the MOST IMPORTANT part of any recursive function.
-
THE RECURSIVE STEP: This is where the function calls itself, but with a modified argument that brings it one step closer to the base case. It's the act of "opening the doll to find the next smaller one."
The Danger: Infinite Recursion and Stack Overflow
What happens if you forget the base case? The function will call itself endlessly. Each time a function is called, a small amount of memory is used on the "call stack". If the recursion never stops, it will eventually use up all the available stack memory, and the program will crash with an error called a STACK OVERFLOW.
The lesson keeps this example commented out:
// DO NOT UNCOMMENT AND RUN THIS FUNCTION.
// It is an example of what NOT to do.
void infinite_recursion(void)
{
printf("This will run forever... and then crash!\n");
infinite_recursion(); // No base case, no modification. Uh oh.
}
Full Source
/**
* @file 19_recursion.c
* @brief Part 3, Lesson 19: Recursion
* @author dunamismax
* @date 06-15-2025
*
* This file serves as the lesson and demonstration for recursion. It explains
* the concept of a function calling itself, the importance of a base case,
* and how recursion can be an elegant alternative to loops for some problems.
*/
/*
* =====================================================================================
* | - LESSON START - |
* =====================================================================================
*
* So far, when you've needed to repeat a task, you've used a loop (`for` or `while`).
* Today, we're going to learn a powerful and elegant alternative: RECURSION.
*
* WHAT IS RECURSION?
* RECURSION is the process of a function calling itself.
*
* Think of it like a set of Russian nesting dolls. You open a doll to find a
* slightly smaller doll inside. You open that one to find an even smaller one,
* and so on, until you reach the smallest, solid doll that can't be opened.
*
* In programming, a recursive function works the same way. It has two essential parts:
*
* 1. THE BASE CASE: This is the condition that STOPS the recursion. It's the
* "smallest doll" that doesn't call itself again. Without a base case, a
* recursive function would call itself forever, leading to a crash. This is
* the MOST IMPORTANT part of any recursive function.
*
* 2. THE RECURSIVE STEP: This is where the function calls itself, but with a
* modified argument that brings it one step closer to the base case. It's
* the act of "opening the doll to find the next smaller one."
*/
#include <stdio.h>
// --- Function Prototypes (Lesson 7) ---
// Declaring the functions up front gives a summary of the file. Their
// definitions, with the explanations, follow below.
void countdown(int n);
long long factorial(int n);
// --- Part 1: A Simple Recursive Countdown ---
// This function will count down from a number `n` to 1, then print "Blastoff!".
// It's a simple way to see the base case and recursive step in action.
void countdown(int n)
{
// BASE CASE: If n is 0 or less, we stop the recursion.
if (n <= 0)
{
printf("Blastoff!\n");
return; // Stop.
}
// RECURSIVE STEP:
printf("%d...\n", n);
countdown(n - 1); // The function calls itself with a smaller number.
}
// --- Part 2: A Classic Example - Factorial ---
// The factorial of a non-negative integer `n`, denoted by `n!`, is the
// product of all positive integers less than or equal to `n`.
// Example: 5! = 5 * 4 * 3 * 2 * 1 = 120
//
// This problem has a natural recursive definition:
// - The factorial of 0 is 1. (Base Case)
// - The factorial of any other number `n` is `n` times the factorial of `n-1`. (Recursive Step)
//
// We use `long long` for the return type because factorials grow very quickly!
long long factorial(int n)
{
// BASE CASE: The factorial of 0 (or 1) is 1.
if (n <= 1)
{
return 1;
}
// RECURSIVE STEP: n multiplied by the factorial of the number below it.
return n * factorial(n - 1);
}
// --- Part 3: The Danger - Infinite Recursion and Stack Overflow ---
// What happens if you forget the base case? The function will call itself
// endlessly. Each time a function is called, a small amount of memory is used
// on the "call stack". If the recursion never stops, it will eventually use up
// all the available stack memory, and the program will crash with an error
// called a STACK OVERFLOW.
/*
// DO NOT UNCOMMENT AND RUN THIS FUNCTION.
// It is an example of what NOT to do.
void infinite_recursion(void)
{
printf("This will run forever... and then crash!\n");
infinite_recursion(); // No base case, no modification. Uh oh.
}
*/
int main(void)
{
printf("--- DEMONSTRATION 1: Countdown from 5 ---\n");
countdown(5);
printf("\n--- DEMONSTRATION 2: Calculating Factorial of 10 ---\n");
int number = 10;
long long fact_result = factorial(number);
printf("The factorial of %d is %lld.\n", number, fact_result);
// Let's try another one.
number = 15;
fact_result = factorial(number);
printf("The factorial of %d is %lld.\n", number, fact_result);
return 0;
}
/*
* =====================================================================================
* | - LESSON END - |
* =====================================================================================
*
* Key Takeaways:
*
* 1. Recursion is a problem-solving technique where a function calls itself.
* 2. It's a powerful alternative to loops for problems that can be broken down
* into smaller, self-similar sub-problems.
* 3. Every recursive function MUST have a BASE CASE to prevent infinite recursion.
* 4. Every recursive function MUST have a RECURSIVE STEP that moves it closer
* to the base case.
* 5. Forgetting or having an incorrect base case leads to a STACK OVERFLOW crash.
*
* While loops are often more efficient in C, recursion can provide incredibly
* elegant and readable solutions for certain types of problems, especially when
* dealing with tree-like data structures we'll see later.
*
* HOW TO COMPILE AND RUN THIS CODE:
*
* 1. Open a terminal or command prompt.
* 2. Navigate to the directory where you saved this file.
* 3. Use the GCC compiler to create an executable file:
* `gcc -Wall -Wextra -std=c17 -o 19_recursion 19_recursion.c`
* 4. Run the executable:
* - On Linux/macOS: `./19_recursion`
* - On Windows (WSL): `./19_recursion`
*/How to Compile and Run
Runs the lesson in Compiler Explorer (GCC 16.2), nothing to install.
Once, before your first lesson
Install Apple's command line tools. They include the cc compiler: xcode-select --install
New to the terminal? The setup guide walks through it.
Build
$ cc -Wall -Wextra -std=c17 -o 19_recursion 19_recursion.c
Run
$ ./19_recursion
- Run these commands in the folder that holds the lesson's file. Download it as a zip.
Try It Yourself
Practise what this lesson taught. Change a copy of the lesson file, or start a new one.
- Write a recursive
int sum_to(int n)that returns 1 + 2 + ... + n. - Write a recursive function that prints a string backwards, one character per call.
- Write a recursive
long long fibonacci(int n)(withfibonacci(0)= 0 andfibonacci(1)= 1) and a loop version, and time both for n = 40. Which is faster, and why?
Finished this lesson?
Mark it complete to track your progress through the course.