🚀 Learn BLE on Linux (BlueZ) – Programming Part 1
Hands-on Bluetooth Low Energy course. Special price: ₹399
Enroll Now on Udemy →Recursion in C Explained
Chapter 6, Lecture 32 of our free C programming course: learn recursion in C step by step, from the terminating condition to the call stack, with examples from embedded C programming.
Welcome to another lecture of our free C programming course on EmbeddedPathashala. In this free C tutorial we explore recursion in C, the technique where a function solves a problem by calling itself on a smaller version of the same problem. Recursion turns many complicated algorithms into a few clean lines, and it appears in sorting, tree traversal, parsing and mathematics. It also has real costs that matter in embedded C programming, where stack memory is tiny. By the end you will understand how recursion works, how to write it safely and when to avoid it.
What You Will Learn
- What recursion is and what a recursive function looks like
- The two rules every recursive solution must follow
- How the call stack grows and unwinds during recursive calls
- How to turn a mathematical definition, such as the factorial, into a recursive definition
- What infinite recursion and stack overflow are, and how to prevent them
- How recursion compares with loops, and why safety standards often forbid it in firmware
Prerequisites
Make sure you understand local variables from this chapter, because every recursive call receives its own fresh set of them. You should also be comfortable with if statements, return values and function calls.
What Is Recursion in C?
Recursion is a way of defining a problem in terms of itself. You solve a big problem by splitting off a small piece of work and handing the remaining, smaller problem to the very same solution. The smaller problem is again split, and so on, until the problem becomes so small that the answer is obvious. The obvious answers are then combined on the way back to give the final result.
In C, this idea is implemented by a function that calls itself. The function that calls itself from inside its own body is called a recursive function, and the call it makes is a recursive call. The calling function and the called function are the same function, each call working on different data.
Shape of every recursive function
1. Check the terminating condition
If the problem is small enough, return the answer directly. This is the base case.
▼ otherwise ▼
2. Do a little work
Handle one piece of the problem, such as printing a value or multiplying by n.
▼
3. Call yourself on a smaller problem
The argument must move closer to the terminating condition on every call.
The Two Rules for Writing a Recursive Function
Before writing any recursive function, check two points. If either one fails, recursion is the wrong tool or your design needs more thought.
- A smaller version of the same problem must exist. You must be able to express the solution in terms of a similar but smaller problem, so that every step brings you nearer to the final answer.
- A terminating condition must exist. Without it, the function keeps calling itself endlessly and never returns.
Recursion in C: Your First Working Examples
We start with two tiny programs. The first prints a countdown, and the second adds the numbers from 1 to n. Save the code as ep_recursion.c.
#include <stdio.h>
static void countdown(int n)
{
if (n == 0) { /* terminating condition */
printf("liftoff\n");
return;
}
printf("%d ", n);
countdown(n - 1); /* smaller problem */
}
static int sum_to(int n)
{
if (n == 0)
return 0;
return n + sum_to(n - 1);
}
int main(void)
{
countdown(5);
printf("sum_to(4) = %d\n", sum_to(4));
return 0;
}
gcc -Wall -Wextra -o ep_recursion ep_recursion.c
./ep_recursion
5 4 3 2 1 liftoff
sum_to(4) = 10
In countdown, the terminating condition is n == 0. Every other call prints its number and calls countdown(n - 1), which is a smaller problem. The argument shrinks by one each time and must eventually hit zero. In sum_to, the idea is that the sum from 1 to n equals n plus the sum from 1 to n minus 1. The sum up to 0 is simply 0, so that is the base case.
How the Call Stack Works During Recursion in C
Each call of a function gets its own stack frame with its own copy of the parameters and local variables, as we saw in the local variables lecture. During recursion these frames pile up one above the other. Nothing can return until the deepest call reaches the terminating condition. Then the frames are released one by one, and each waiting call finishes its pending addition.
Going down: calls waiting for results (sum_to(4))
sum_to(4) waits to compute 4 + sum_to(3)
sum_to(3) waits to compute 3 + sum_to(2)
sum_to(2) waits to compute 2 + sum_to(1)
sum_to(1) waits to compute 1 + sum_to(0)
sum_to(0) reaches the terminating condition and returns 0
Coming back up: results flow back
| Call returning | Calculation | Value returned |
|---|---|---|
| sum_to(1) | 1 + 0 | 1 |
| sum_to(2) | 2 + 1 | 3 |
| sum_to(3) | 3 + 3 | 6 |
| sum_to(4) | 4 + 6 | 10 |
Notice the difference between the two examples. In countdown the work (printing) happens on the way down, so the numbers appear in descending order. In sum_to the useful work (the additions) happens on the way back up. If you moved the print statement of countdown after the recursive call, the numbers would print 1 up to 5 instead. Understanding which direction the work happens in is the key to reading recursive code.
From Iterative to Recursive Definition: The Factorial
The factorial of a positive integer n is the product of all integers from 1 up to n. That is the iterative definition, and you have already coded it with a loop in an earlier chapter. To find the recursive definition, look for a smaller problem hiding inside the bigger one.
| Expression | Rewritten using a smaller factorial |
|---|---|
| 6! | 6 × 5! |
| 5! | 5 × 4! |
| n! | n × (n-1)! |
The factorial of n-1 is the same kind of problem as the factorial of n, but definitely smaller, so the first rule is satisfied. For the second rule we need a stopping point, and mathematics provides one: the factorial of 0 is 1. That gives the complete recursive definition: the factorial of 0 is 1, and for larger n it is n times the factorial of n-1. In the next lecture we turn this definition into a working function and trace its stack in detail, then continue with power, Fibonacci numbers and the Tower of Hanoi.
Infinite Recursion and Stack Overflow
If the terminating condition is missing, or the argument never moves toward it, the calls never stop. Each call consumes stack memory, so eventually the stack is exhausted. On a PC the operating system stops the program with a segmentation fault. On a bare-metal microcontroller there may be nothing to catch the overflow, so the stack silently overwrites other variables, or the processor jumps to a fault handler and resets.
/* BROKEN: n is never compared against a stopping value */
static int bad_sum(int n)
{
return n + bad_sum(n - 1);
}
The argument n - 1 heads towards negative infinity and no if ever stops it. A common subtle version of this bug is a terminating condition that tests for equality when the argument can skip over the value. For example, a base case of n == 0 fails if someone calls the function with a negative number. Writing the test as n <= 0 is the safer habit.
Recursion versus Loops
| Aspect | Recursion | Loop |
|---|---|---|
| Memory | One stack frame per call, grows with depth | Constant extra memory |
| Speed | Function call overhead every step | Usually faster |
| Readability | Very clear for tree-shaped and divide-and-conquer problems | Very clear for simple repetition |
| Risk | Stack overflow if too deep | Infinite loop if the condition is wrong |
| Best for | Trees, sorting, parsing, Tower of Hanoi | Counting, summing, scanning arrays |
Every recursive function can be rewritten with a loop, sometimes with an explicit stack of your own. The choice is about clarity versus resource cost.
Recursion in Embedded C Programming
Recursion is used on firmware too, but with caution. Typical safe uses are parsing a small nested configuration, walking a shallow tree of menu items, or sorting a short array. Many safety-critical coding standards, including MISRA C, forbid recursion entirely, because the maximum stack depth must be provable at build time. If every function call chain is finite and known, you can calculate the worst-case stack usage and size the stack with confidence. Recursion depth that depends on input makes that impossible.
Common Mistakes and Troubleshooting
No terminating condition. Always write the base case first, before the recursive call.
Argument does not shrink. Calling f(n) from inside f(n) loops forever. Each recursive call must pass a strictly smaller problem.
Forgetting to use the returned value. Writing sum_to(n - 1); as a statement discards the result and computes nothing useful.
Large local arrays inside recursive functions. Each level gets its own copy, so memory use multiplies by the depth.
If a recursive program crashes, run it on small inputs first, add a temporary printf showing the argument at the top of the function, and watch whether the value approaches the base case.
Best Practices, Performance and Security
- Write the terminating condition first and test it with the smallest inputs.
- Prefer
<=style base cases when the argument might go below the stopping value. - Estimate the maximum depth and the bytes per frame before using recursion on a microcontroller.
- Replace recursion with a loop when depth depends on untrusted input. An attacker who controls the depth can crash the device by overflowing the stack.
- Keep recursive functions small, with few locals and no large buffers.
Summary and Key Takeaways
- Recursion in C means a function calls itself to solve a smaller version of the same problem.
- Every recursive function needs a smaller problem at each step and a terminating condition.
- Each call has its own stack frame, so depth costs memory.
- The factorial has the recursive definition n! = n × (n-1)! with 0! = 1.
- Embedded and safety-critical code often avoids recursion because stack use must be predictable.
Conclusion
Recursion is one of those ideas that feels strange at first and then becomes natural. The recipe never changes: define the stopping case, do a little work, and trust the function to handle the smaller remainder. Understanding the call stack takes the mystery out of it and also shows you the cost. With this foundation you are ready for the next lecture, where we convert the factorial definition into code and trace it step by step, before moving on to classic recursive problems.
Frequently Asked Questions
What is recursion in C?
A technique where a function calls itself, each time solving a smaller version of the original problem until a simple base case is reached.
What is a terminating condition?
The test that stops the recursion and returns a direct answer without another recursive call. Also called the base case.
What happens without a terminating condition?
The function calls itself endlessly until the stack runs out of memory, causing a crash or a reset.
Is recursion slower than a loop?
Usually yes, because every call adds overhead and a stack frame. For simple repetition a loop is faster and uses less memory.
Can recursion be used in embedded systems?
Yes, for shallow and bounded depths, but many standards such as MISRA C forbid it because stack usage must be predictable.
Can every recursive function be written with a loop?
Yes. Some need an explicit stack that you manage yourself, but the result is always possible.
Keep Going With the Free Embedded C Course
Continue to the next lecture, share this free C tutorial with a friend, and keep building your embedded C programming skills.

2 Comments