🚀 Learn BLE on Linux (BlueZ) – Programming Part 1
Hands-on Bluetooth Low Energy course. Special price: ₹399
Enroll Now on Udemy →Recursion Versus Loops in C
Chapter 6, Functions: solve the same problems with a loop and with recursion in C, then see how recursion can add and divide by simply counting one step at a time. Free C programming course, embedded focus.
Recursion in C confuses many learners because the code looks tiny while the execution feels enormous. A function that calls itself can replace a loop, count with its arguments, and even perform addition and division. In this lecture of the free C tutorial series we take three classic exercise patterns, a sum of squares, recursive addition and a recursive quotient, and solve each one twice: once with a loop, once with recursion in C. Seeing both versions side by side is the fastest way to build intuition.
All examples are original programs written for embedded C programming learners, with real compiler output so you can compare your own results.
What You Will Learn
- How to convert a counting loop into a recursive function and back again.
- How to read a recursive function by tracking what stays constant from call to call.
- How recursion in C can add two numbers by moving one unit at a time.
- How a recursive quotient works by repeated subtraction, and why it is slow for big inputs.
- A practical comparison of stack use, speed and safety between loops and recursion.
Prerequisites
Finish the previous lecture on static variables and basic recursion first. You should know what a base case is and understand that each call owns its own parameters. The programs compile with any C99 compiler, for example gcc -std=c11 -Wall -Wextra file.c.
Recursion in C Compared With a Loop: Sum of Squares
Suppose a sensor-calibration routine needs the sum of the squares of every integer from lo to hi. A loop visits each number in turn and keeps a running total. The recursive version says something different: the answer for the range is the square of the first number plus the answer for the rest of the range.
#include <stdio.h>
long squares_loop(int lo, int hi)
{
long acc = 0;
for (int k = lo; k <= hi; k++)
acc += (long)k * k;
return acc;
}
long squares_rec(int lo, int hi)
{
if (lo > hi)
return 0; /* empty range */
return (long)lo * lo + squares_rec(lo + 1, hi);
}
int main(void)
{
printf("loop: %ld recursive: %ld\n",
squares_loop(2, 6), squares_rec(2, 6));
return 0;
}
loop: 90 recursive: 90
For the range 2 to 6 both functions deliver 90, because 4 + 9 + 16 + 25 + 36 equals 90. Notice how the recursive function handles the end of the range: when lo has moved past hi the range is empty and the sum is zero. That empty-range test is the base case.
Loop variable versus argument
The loop version stores its position in the variable k and updates it with k++. The recursive version stores its position in the argument lo and updates it by passing lo + 1 to the next call. The argument plays exactly the part of the loop counter, which is the key insight behind recursion in C.
| Idea | Loop version | Recursive version |
|---|---|---|
| Current position | Variable k | Parameter lo |
| Running total | Variable acc | Pending additions on the stack |
| Stop condition | k <= hi fails | lo > hi is true |
| Extra memory | Constant | One frame per number |
Recursive sum of squares for 2 to 6 unwinding
Going down
Calls for 2, 3, 4, 5, 6 each wait; call 7 finds an empty range and returns 0.
Coming back
6 gives 36, then 5 adds 25 for 61, then 4 adds 16 for 77.
Final answer
3 adds 9 for 86, and 2 adds 4 for the total of 90.
Recursion in C That Adds Two Numbers
Here is a puzzle: add two non-negative integers using only the ability to subtract one and add one. The idea is to move one unit at a time from the first number to the second. When the first number reaches zero, the second number holds the total.
#include <stdio.h>
static int calls; /* counts how many frames a request needed */
int add_rec(int x, int y)
{
calls++;
if (x == 0)
return y;
return add_rec(x - 1, y + 1); /* move one unit from x to y */
}
int quo_rec(int dividend, int divisor)
{
calls++;
if (dividend < divisor)
return 0;
return 1 + quo_rec(dividend - divisor, divisor);
}
int main(void)
{
int sum, quotient;
calls = 0;
sum = add_rec(7, 8);
printf("add_rec(7, 8) = %d (%d calls)\n", sum, calls);
calls = 0;
quotient = quo_rec(55, 17);
printf("quo_rec(55,17) = %d (%d calls)\n", quotient, calls);
return 0;
}
add_rec(7, 8) = 15 (8 calls)
quo_rec(55,17) = 3 (4 calls)
For 7 and 8 the first argument counts down 7, 6, 5 and so on to 0, while the second counts up 8, 9, 10 and so on to 15. Eight calls are needed: seven moving steps plus the final call that meets the base case. Notice the quantity that never changes. At every step x + y is 15. A value that stays the same through every call is called an invariant, and spotting it is the quickest way to understand any recursive function.
Invariant x plus y stays 15 during add_rec(7, 8)
return add_rec(x - 1, y + 1); the keyword return is essential. Calling the function without returning its value leaves the outer frames with nothing to hand back, and using that result is undefined behaviour. GCC warns about it with “control reaches end of non-void function”.
Recursion in C That Finds a Quotient
The second function in the program divides without a division operator. If the dividend is smaller than the divisor, the quotient is zero. Otherwise subtract one divisor and count one more.
| Call | Dividend | Divisor | Decision |
|---|---|---|---|
| 1 | 55 | 17 | 55 is at least 17, so add 1 and recurse with 38 |
| 2 | 38 | 17 | Add 1 and recurse with 21 |
| 3 | 21 | 17 | Add 1 and recurse with 4 |
| 4 | 4 | 17 | 4 is less than 17: base case, return 0 |
Three pluses of 1 sit on the stack, giving the quotient 3, and the program confirms that four calls were made. The leftover 4 is the remainder, so 55 equals 3 times 17 plus 4. The same invariant idea applies: dividend plus the number of subtractions times the divisor is always the original dividend.
Guarding against a bad divisor
If the divisor were zero, nothing would ever be subtracted and the dividend would never become smaller than it. The function would call itself until the stack overflowed. A production version must reject divisors that are zero or negative before recursing, exactly as the loop-based helpers in the later lectures do.
Choosing Between Loops and Recursion in C
| Criterion | Loop | Recursion in C |
|---|---|---|
| Stack use | Constant | Grows with depth |
| Typical speed | Faster, no call overhead | Slower, one call per step |
| Best fit | Counting, scanning arrays, polling | Trees, nested data, divide and conquer |
| Proof of safety | Easy to bound | Needs a depth limit |
| Allowed in strict firmware rules | Yes | Often banned |
A stack estimate shows the risk. Assume, purely as an illustration, that each frame costs 32 bytes. A depth of 50 uses 1,600 bytes, which is fine. Computing 1,000,000 divided by 1 by this method would need a million frames, tens of megabytes, and no microcontroller has that. The identical task as a loop needs a single counter.
Tail recursion and compilers
The recursive call in add_rec is the last thing the function does. This shape is called tail recursion, and an optimising compiler may turn it into a jump, reusing one frame. The C standard does not promise this, so you must not rely on it for safety. Use a loop when the depth could be large.
Real-World Use Cases
- Long division on small cores: some tiny microcontrollers have no divide instruction, so library code divides by repeated subtraction or shift and subtract. Knowing the logic helps you read those library routines.
- Range accumulation: summing readings over a window of samples is a loop in firmware but a recursive definition on paper.
- Interview questions: add, multiply and divide without operators are favourites because they test invariants and base cases.
Common Mistakes and Troubleshooting
| Mistake | What happens | Fix |
|---|---|---|
Missing return before the recursive call | Garbage or undefined result | Return the value of the inner call |
| Recursing with the same argument | Endless recursion and stack overflow | Change the argument toward the base case |
| Zero divisor in the quotient helper | Never reaches the base case | Validate the divisor first |
| Negative inputs to add or quotient | Base case is skipped | Document the non-negative contract or handle signs |
Using int for large sums | Overflow, wrong totals | Use long or an unsigned type |
Best Practices, Performance and Security
Best practices
- Write the base case first and test it alone.
- Identify the invariant before writing the recursive step.
- Bound the depth, or choose a loop when input size is not known in advance.
- Keep recursive functions small and free of large local arrays.
Performance: the quotient routine runs in time proportional to the quotient, so dividing a large value by a small one is slow. Hardware dividers or a shift-and-subtract algorithm need only as many steps as there are bits.
Security: never let untrusted input choose the recursion depth. A single crafted value can crash a device or corrupt memory next to the stack, which in an embedded system may be your peripheral registers or another task’s data.
Key Takeaways and Conclusion
- A recursive argument takes over the job of a loop counter.
- Look for an invariant to understand what a recursive function really computes.
- Recursive addition moves units between two arguments; recursive quotient subtracts and counts.
- Loops win on stack use and speed; recursion wins on clarity for nested problems.
- Always include a way for the recursion to stop on bad input.
Mastering recursion in C is less about syntax and more about seeing the shape of a problem: what is the smallest case, and how does one step shrink the problem? You now have three worked examples and a comparison table to apply the next time a question asks you to trace or write a recursive function. In the next lecture we study the order in which recursive output appears and the pitfalls hidden in the decrement operator.
Frequently Asked Questions
What is recursion in C in simple words?
It is a function that solves a problem by calling itself on a smaller version of that problem until a case so small that it can be answered directly.
Is recursion in C slower than a loop?
Usually yes, because each call pushes and pops a stack frame. The difference is small for shallow depths but matters in tight embedded loops.
How do I know when a recursive function will stop?
Check that every call moves an argument closer to the base case and that the base case is reachable for every allowed input.
Can recursion in C replace every loop?
In principle yes, but it is rarely wise. Counting and scanning are clearer and safer as loops.
Why does the recursive add function return y at the base case?
Because by then every unit has moved from x into y, so y already holds the full total.
What happens if recursion never reaches the base case?
The stack fills up. On a PC the program is killed; on a microcontroller it may silently corrupt memory or reset.
Learn C Free, One Lecture at a Time
Next up: how the order of printing and decrementing changes recursive output, with complete traces. Our free C programming course keeps every example runnable.

2 Comments