What are Recursion Versus Loops in C- Free Embedded Systems and C Programming Course

🚀 Learn BLE on Linux (BlueZ) – Programming Part 1

Hands-on Bluetooth Low Energy course. Special price: ₹399

Enroll Now on Udemy →
💬 Need help or career guidance? Ask us!Contact Us →

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.

3
Worked problems
2
Runnable programs
Free
Embedded C course

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.

IdeaLoop versionRecursive version
Current positionVariable kParameter lo
Running totalVariable accPending additions on the stack
Stop conditionk <= hi failslo > hi is true
Extra memoryConstantOne frame per number

Recursive sum of squares for 2 to 6 unwinding

1

Going down

Calls for 2, 3, 4, 5, 6 each wait; call 7 finds an empty range and returns 0.

2

Coming back

6 gives 36, then 5 adds 25 for 61, then 4 adds 16 for 77.

3

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)

x = 7y = 8sum 15
x = 6y = 9sum 15
x = 3y = 12sum 15
x = 0y = 15base case, return y
Do not forget return: in 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.

CallDividendDivisorDecision
1551755 is at least 17, so add 1 and recurse with 38
23817Add 1 and recurse with 21
32117Add 1 and recurse with 4
44174 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

CriterionLoopRecursion in C
Stack useConstantGrows with depth
Typical speedFaster, no call overheadSlower, one call per step
Best fitCounting, scanning arrays, pollingTrees, nested data, divide and conquer
Proof of safetyEasy to boundNeeds a depth limit
Allowed in strict firmware rulesYesOften 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

MistakeWhat happensFix
Missing return before the recursive callGarbage or undefined resultReturn the value of the inner call
Recursing with the same argumentEndless recursion and stack overflowChange the argument toward the base case
Zero divisor in the quotient helperNever reaches the base caseValidate the divisor first
Negative inputs to add or quotientBase case is skippedDocument the non-negative contract or handle signs
Using int for large sumsOverflow, wrong totalsUse 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.

💬 Need help or career guidance? Ask us!Contact Us →

2 Comments

Leave a Reply

Your email address will not be published. Required fields are marked *

×

🚀 BLE on Linux (BlueZ)

Hands-on course. Only ₹399

Enroll Now →