🚀 Learn BLE on Linux (BlueZ) – Programming Part 1
Hands-on Bluetooth Low Energy course. Special price: ₹399
Enroll Now on Udemy →Recursive Prime Factors in C
Free C tutorial: solve prime factorization with recursion, trace the call stack and learn the limits of recursion in embedded C.
Recursive prime factors in C give you a perfect small problem for understanding how a function can solve a task by calling itself. In this lecture of our free C programming course we rewrite the loop-based factorizer from the previous lecture as a recursive function, measure how deep the recursion goes, and discuss why this matters for C programming for embedded systems, where stack memory is measured in kilobytes. By the end you will know when recursion is elegant, when it is dangerous, and how to write it without hidden state.
What You Will Learn
- How to find the base case and the progress step of a recursive function
- How to convert a loop that updates two variables into a recursive function with two parameters
- How to read a call stack diagram for recursive prime factors in C
- Why a
staticlocal variable makes a recursive function unsafe to call twice - How to measure recursion depth and predict stack usage
- When to prefer the iterative version in embedded C programming
Prerequisites
- The previous lecture on iterative prime factorization
- Understanding of function calls and local variables living on the stack
- Basic recursion: factorial or power functions from earlier lectures
- GCC or any C99 compiler
From a Loop to Recursion
An iterative factorizer keeps two pieces of state: the remaining value and the current candidate divisor. A loop updates them in place. A recursive version carries the same state in the function parameters, and each call represents one step of the loop. Converting a loop to recursion is therefore a mechanical process: list the state variables, make them parameters, turn the loop condition into the base case, and turn the loop body into a recursive call with updated arguments.
| Loop idea | Recursive equivalent |
|---|---|
| Variables changed each pass | Parameters passed to the next call |
| Loop exit condition | Base case that returns without calling again |
| Loop body | Body of the function before the recursive call |
| Next iteration | The recursive call itself |
| Memory used | One stack frame per iteration |
Designing the Recursive Prime Factors Function
Every correct recursive function needs two things: a base case that stops the recursion and a step that moves strictly closer to that base case. For prime factors in C we have three situations when the function receives a remaining value and a candidate divisor.
The first two branches are base cases. The last two shrink either the value or the gap between the divisor and the square root, so the function must eventually reach a base case. If you cannot explain why each call makes progress, the function can recurse forever.
Complete Recursive Prime Factors Program
The program below adds a depth counter so you can observe how many stack frames are alive at the deepest point. The counter is a global used only for measurement; the factorization itself keeps all of its state in parameters.
#include <stdio.h>
#include <stdint.h>
static unsigned ep_depth;
static unsigned ep_max_depth;
/* Recursive trial division: the candidate divisor travels as a parameter */
static void ep_factor_rec(uint32_t value, uint32_t divisor)
{
ep_depth++;
if (ep_depth > ep_max_depth) {
ep_max_depth = ep_depth;
}
if (value < 2U) {
/* nothing left */
} else if (divisor > value / divisor) {
printf("%u ", value); /* remaining value is prime */
} else if (value % divisor == 0U) {
printf("%u ", divisor);
ep_factor_rec(value / divisor, divisor);
} else {
ep_factor_rec(value, divisor + 1U);
}
ep_depth--;
}
static void ep_print_factors_rec(uint32_t value)
{
ep_factor_rec(value, 2U);
printf("\n");
}
int main(void)
{
uint32_t samples[] = { 56U, 98U, 121U, 97U, 360U, 65537U, 4294967291U };
for (unsigned i = 0; i < sizeof samples / sizeof samples[0]; i++) {
ep_max_depth = 0;
printf("%10u : ", samples[i]);
ep_print_factors_rec(samples[i]);
printf(" max recursion depth = %u\n", ep_max_depth);
}
return 0;
}
Notice the small wrapper function ep_print_factors_rec(). The caller supplies only the number; the wrapper supplies the starting divisor of 2. Hiding the extra parameter keeps the public interface simple and prevents callers from passing a bad starting point.
Build and run
$ gcc -std=c99 -Wall -Wextra -O0 -o ep_factor_rec ep_factor_rec.c
$ ./ep_factor_rec
56 : 2 2 2 7
max recursion depth = 5
98 : 2 7 7
max recursion depth = 8
121 : 11 11
max recursion depth = 11
97 : 97
max recursion depth = 9
360 : 2 2 2 3 3 5
max recursion depth = 7
65537 : 65537
max recursion depth = 256
4294967291 : 4294967291
max recursion depth = 65535
Reading the Call Stack
Each active call owns a stack frame holding its parameters, local variables and return address. When the function calls itself, a new frame is pushed. When a call returns, its frame is popped. Here is the stack at the deepest point while factoring 56, where the function has just printed 7 and is about to return.
That matches the measured depth of 5 in the output above. The depth table shows the real cost: the number of frames grows with the number of divisors tested, not with the number of factors found. For the prime 4294967291 the function reaches a depth of 65535 because it tries every divisor from 2 up to 65535, and each failed test adds a frame.
Recursion Depth and Stack Memory in Embedded C
A frame for this function is small, perhaps 32 to 48 bytes depending on the compiler and target, but 65535 frames add up to megabytes. On a desktop with an 8 MB default stack the program survives. When we limited the stack to 64 KB with ulimit -s 64, the same program crashed with a segmentation fault. A typical microcontroller has between 2 KB and 64 KB of RAM in total, so the same program would overwrite other data long before it crashed cleanly, and a stack overflow on a bare-metal target often gives no error message at all.
| Input | Max depth measured | Why |
|---|---|---|
| 56 | 5 | Three 2s, one failed 2, one prime check |
| 360 | 7 | Divisors 2 and 3 repeat, then stops |
| 97 | 9 | Tries 2 to 9 then declares prime |
| 65537 | 256 | Tries 2 to 256 (square root bound) |
| 4294967291 | 65535 | Tries 2 to 65535 (square root bound) |
Embedded rule of thumb: recursion is acceptable only when the maximum depth is bounded by something you can prove at design time. Here the depth is bounded by the square root of the input, which is not small enough for arbitrary 32-bit values on a small device.
Tail calls and compiler optimization
Both recursive calls in our function are in tail position: nothing happens after the call returns except the depth counter in the test version. Compilers such as GCC can convert tail calls into jumps at higher optimization levels, which removes the stack growth completely. This is an optimization, not a language guarantee, so safety-critical code must not depend on it. Coding standards such as MISRA C forbid recursion in safety-related firmware for exactly this reason.
The Static Variable Trap
A tempting way to avoid the second parameter is to keep the divisor in a static local variable, because a static variable keeps its value between calls. The function looks shorter, and it even works the first time you call it. Here is the broken version and what it does.
static void ep_bad_factor(uint32_t value)
{
static uint32_t divisor = 2U;
if (value < 2U) { return; }
if (value % divisor == 0U) { printf("%u ", divisor); ep_bad_factor(value / divisor); }
else { divisor++; ep_bad_factor(value); }
}
int main(void)
{
ep_bad_factor(56U); printf("\n");
ep_bad_factor(90U); printf("\n");
return 0;
}
2 2 2 7
9 10
The first call prints the right answer, but it leaves the static divisor at 7. The second call starts with 7 instead of 2, so it skips the factors 2, 3 and 5 entirely and prints the wrong answer 9 and 10 for 90, whose correct factors are 2, 3, 3 and 5. The function has hidden state that survives between independent uses, which makes it non-reentrant. It also cannot be called safely from two tasks or from an interrupt and a main loop at the same time.
Rule
If a recursive function needs to remember something between steps, pass it as a parameter. Use static storage only for data that really must be shared, and document it.
Iterative or Recursive Prime Factors: Which to Choose?
| Criteria | Iterative | Recursive |
|---|---|---|
| Stack use | Constant | Grows with divisors tested |
| Speed | Slightly faster, no call overhead | Call and return cost on every step |
| Readability | Familiar loop shape | Maps directly to the math definition |
| Safe on tiny devices | Yes | Only with a proven depth bound |
| Good for learning | Yes | Yes, shows how state moves in calls |
In production firmware you would almost always ship the iterative version. Recursion earns its place when the problem is naturally recursive, such as walking a tree, parsing nested structures or divide-and-conquer algorithms, and when the depth is small and bounded.
Common Mistakes and Troubleshooting
- Missing base case. Without the
value < 2check, the function keeps calling itself on 1 and the stack overflows. - No progress in a branch. Calling the function again with the same value and the same divisor loops forever.
- Static state. As shown above, it gives correct output once and wrong output afterwards.
- Ignoring depth for large inputs. Test with the largest prime your type allows and run with a reduced stack limit to see failures early.
- Forgetting to print the leftover prime. The second base case is what prints the last factor, so it must not be removed.
Best Practices, Performance and Security
- Write the base case first, then the recursive step.
- Pass all changing state as parameters and keep the function free of hidden globals.
- Wrap the recursive helper in a friendly function that supplies starting arguments.
- Test with
ulimit -sset low to expose stack problems on a desktop. - For security and reliability, never recurse on untrusted input without a depth limit, because an attacker can choose the input that causes the deepest recursion.
- Build with
-Wstack-usage=Nin GCC to get a warning when a function exceeds a chosen frame size.
Summary and Key Takeaways
- A recursive function needs a base case and a step that always moves toward it.
- Loop state becomes function parameters, and the loop test becomes the base case.
- Each call costs a stack frame, so depth equals memory use.
- Static locals create hidden state and break repeated or concurrent use.
- Iterative code is the safer choice for embedded C programming unless the depth is provably small.
Conclusion
You now have two correct solutions to the same problem and, more importantly, a way to compare them using measurements instead of opinions. Recursion made the algorithm read like its definition, but it traded constant memory for a stack that grows with the input. That trade-off is central to C programming for embedded systems, where RAM is scarce and failures are silent. In the next lecture of this free embedded C course we compute the sum of a series both iteratively and recursively, and you will see the same pattern of state moving between calls in a numeric problem.
Frequently Asked Questions
What is recursion in C in simple words?
Recursion means a function solves a problem by calling itself on a smaller version of the same problem until it reaches a case simple enough to answer directly.
Why does the recursive version use more memory than the loop?
Every call creates a stack frame that stays alive until the call returns. A loop reuses the same variables, so it needs only one frame no matter how many iterations run.
Can the compiler remove the recursion for me?
At higher optimization levels GCC often turns tail calls into jumps, but the language does not promise it. Never rely on it where a stack overflow would be unsafe.
Is recursion allowed in embedded and safety-critical code?
Many coding standards, including MISRA C, restrict or forbid it because stack usage cannot be bounded by static analysis. Where it is allowed, the maximum depth must be proven.
Why is a static local variable a bad idea in a recursive function?
A static variable keeps its value after the function returns, so the next top-level call starts with leftover state. It also makes the function unsafe to call from several tasks.
How can I see how much stack my program uses?
Run it under a smaller limit with ulimit -s, use GCC options such as -fstack-usage, or on a microcontroller fill the stack with a known pattern and check how much was overwritten.
Keep Building Your C Skills for Free
Next we sum a mathematical series with both loops and recursion and watch floating point and overflow problems appear.

2 Comments