🚀 Learn BLE on Linux (BlueZ) – Programming Part 1
Hands-on Bluetooth Low Energy course. Special price: ₹399
Enroll Now on Udemy →Recursive Power Function in C
Understand the winding and unwinding phases of recursion, see how stack frames pile up, and build a recursive power function in C that is safe enough for embedded targets.
In this lecture of our free C programming course we build a recursive power function in C, and along the way we answer a question every beginner asks: what is actually happening in memory while a function keeps calling itself? This free C tutorial keeps C programming for embedded systems in mind, so we measure recursion depth, discuss stack budgets, and then upgrade the naive power function into a much faster version.
Last time we wrote factorial with recursion. Here we look underneath it. Once you understand the two phases of recursion, every other recursive program in this free embedded C course becomes easy to read.
What You Will Learn
- The winding phase and the unwinding phase of a recursive function
- Why one copy of code can serve many simultaneous calls
- How to write a recursive power function in C for integers and floating-point numbers
- How to handle a negative exponent and a zero exponent correctly
- How exponentiation by squaring reduces recursion depth from n to about log n
- How to estimate stack consumption for embedded C programming
Prerequisites
- The previous lecture on factorial using recursion in C
- Understanding of function parameters and return values
- Comfort with
unsignedintegers and thedoubletype
Winding and Unwinding: The Two Phases of Recursion
Every recursive function call sequence has two clearly separate stages. During the winding phase the function keeps calling itself and nothing is returned yet. Each call is frozen at the line that makes the next call, holding its own parameters and its own return address. The winding stops when a call meets the base case. Then the unwinding phase begins: the deepest call returns, the call just above it resumes and finishes its expression, returns in turn, and so on until the first call delivers the final answer to its caller.
Winding
Calls go deeper. Stack grows. No result is produced yet. Ends when the base case is reached.
Turning point
The base case returns a known value without calling anything else.
Unwinding
Calls return in reverse order. Stack shrinks. Each caller finishes its pending work.
One Copy of Code, Many Calls
A common misunderstanding is that a recursive function with six active calls exists six times in memory. It does not. The instructions are stored once in flash or in the code segment. What multiplies is the stack frame, a small block that holds the parameters, local variables, saved registers and the return address of one specific call. Two calls differ only because the values inside their frames differ.
| Item | Stored how many times | Where it lives |
|---|---|---|
| Machine instructions of the function | Once | Flash or code segment |
| Parameters and locals of each call | Once per active call | Stack |
| Return address of each call | Once per active call | Stack or link register |
| Global and static variables | Once, shared by all calls | Data or BSS section |
Defining Power Recursively
Raising a number a to a non-negative integer power n means multiplying a by itself n times. That is the iterative view. The recursive view says: a to the power n equals a multiplied by a to the power n minus 1, and anything raised to the power 0 is 1.
| Exponent | Rule | Role |
|---|---|---|
| n equals 0 | Result is 1 | Base case |
| n greater than 0 | a multiplied by power(a, n – 1) | Recursive case |
Recursive Power Function in C: Working Program
The following program raises a floating-point base to an unsigned exponent. The exponent is unsigned on purpose: it can never be negative, so the recursion is guaranteed to reach zero.
#include <stdio.h>
/* base raised to exp, exp is never negative */
static double pow_simple(double base, unsigned exp)
{
if (exp == 0u) {
return 1.0; /* base case */
}
return base * pow_simple(base, exp - 1u); /* recursive case */
}
int main(void)
{
double base;
unsigned exponent;
printf("Enter base and exponent: ");
if (scanf("%lf %u", &base, &exponent) != 2) {
puts("Bad input");
return 1;
}
printf("%g to the power %u = %f\n", base, exponent,
pow_simple(base, exponent));
return 0;
}
$ gcc -Wall -Wextra -o pw pw.c
$ ./pw
Enter base and exponent: 2.5 4
2.5 to the power 4 = 39.062500
Stack Picture at the Deepest Point
Suppose we call pow_simple(2.0, 3u). At the instant the base case runs, four frames exist above main. The table lists the stack from the newest frame to the oldest.
| Position | Frame | Exponent held | Waiting to compute |
|---|---|---|---|
| Top (newest) | pow_simple call 4 | 0 | Returns 1.0 now |
| Below | pow_simple call 3 | 1 | 2.0 multiplied by the result of call 4 |
| Below | pow_simple call 2 | 2 | 2.0 multiplied by the result of call 3 |
| Below | pow_simple call 1 | 3 | 2.0 multiplied by the result of call 2 |
| Bottom (oldest) | main | – | Waiting for the final answer |
On the way back the values are 1.0, then 2.0, then 4.0, then 8.0. The multiplications happen only during unwinding, which is why the final answer appears at the very end.
Handling Negative Exponents
A negative exponent means the reciprocal: a to the power minus n equals one divided by a to the power n. We can keep the recursive core simple and put the sign logic in a thin wrapper.
static double pow_signed(double base, int exp)
{
if (exp < 0) {
unsigned magnitude = 0u - (unsigned)exp; /* safe for INT_MIN too */
return 1.0 / pow_simple(base, magnitude);
}
return pow_simple(base, (unsigned)exp);
}
Improving the Recursive Power Function in C
The version above makes n + 1 calls. Raising a number to the power one million would need about a million stack frames, which is impossible on a microcontroller with a few kilobytes of RAM. A smarter recursion halves the exponent each time. This idea is called exponentiation by squaring.
If the exponent is even, the answer is the square of the base raised to half the exponent. If it is odd, you also multiply by one extra copy of the base. The recursion depth drops from n to roughly the number of bits in n.
#include <stdio.h>
#include <stdint.h>
static uint32_t ipow_fast(uint32_t base, uint32_t exp)
{
uint32_t half;
if (exp == 0u) {
return 1u;
}
half = ipow_fast(base, exp / 2u);
if ((exp & 1u) == 0u) {
return half * half;
}
return half * half * base;
}
int main(void)
{
printf("3^13 = %lu\n", (unsigned long)ipow_fast(3u, 13u));
return 0;
}
3^13 = 1594323
| Call | Exponent | Half result received | Result returned |
|---|---|---|---|
| A | 13 | 729 | 729 x 729 x 3 = 1594323 |
| B | 6 | 27 | 27 x 27 = 729 |
| C | 3 | 3 | 3 x 3 x 3 = 27 |
| D | 1 | 1 | 1 x 1 x 3 = 3 |
| E | 0 | – | 1 (base case) |
Depth Comparison
| Exponent | Calls in simple version | Calls in squaring version |
|---|---|---|
| 13 | 14 | 5 |
| 100 | 101 | 8 |
| 1000 | 1001 | 11 |
Estimating Stack Use in Embedded C Programming
Stack budgeting is a skill that separates firmware engineers from application programmers. The rule of thumb is simple: worst-case stack for recursion equals maximum depth multiplied by the frame size. The frame size on a small ARM core is often a few dozen bytes once the return address, saved registers and locals are counted, but the exact figure depends on the compiler, the optimisation level and the calling convention. Read the generated assembly or use your toolchain’s stack-usage option to get the real number.
$ arm-none-eabi-gcc -O2 -fstack-usage -c pw.c
$ cat pw.su
The .su file lists the stack size of every function. For a recursive function the tool cannot give a total, and it marks it as dynamic or unbounded, which is exactly why static analysis tools dislike recursion.
Real-World Use Cases
- Computing scaling factors such as powers of ten or two in sensor drivers
- Modular exponentiation in cryptographic routines, where squaring is the core trick
- Building lookup tables at start-up
- Calculating buffer sizes that double at each level of a data structure
Common Mistakes and Troubleshooting
| Symptom | Cause | Fix |
|---|---|---|
| Crash on negative exponent | Exponent is a signed type that moves away from zero | Use an unsigned exponent and a wrapper for negatives |
| Result suddenly wrong for large exponent | Integer overflow, for example 3 to the 21 does not fit in 32 bits | Use a wider type or check the range first |
| Output prints 0.000000 unexpectedly | Wrong format specifier or integer division | Use %f for double and 1.0 instead of 1 |
| Slow for huge exponents | Linear recursion | Switch to exponentiation by squaring |
| Stack overflow at moderate input | Frame size larger than assumed | Measure with stack-usage tools and cap the depth |
Best Practices, Performance and Security
- Keep the recursive core tiny and put validation in a wrapper.
- Choose the parameter that shrinks to be unsigned so the base case is always reachable.
- Prefer logarithmic recursion depth over linear depth whenever the problem allows it.
- Performance: the squaring version also performs far fewer multiplications, so it saves time and stack together.
- Security: never let an untrusted value control recursion depth directly. Clamp it to a documented maximum.
- Document the allowed input range in a comment above the function.
Summary and Key Takeaways
- Recursion has a winding phase that grows the stack and an unwinding phase that shrinks it.
- The function code exists once, but each active call owns a stack frame.
- A recursive power function in C needs a base case at exponent 0.
- Halving the exponent cuts the depth from n to about log n.
- Always estimate stack use before choosing recursion for firmware.
Conclusion
The recursive power function in C is a small program, yet it taught us the full life cycle of a recursive call: descend, hit the base case, then return in reverse order. You also saw that a small change in the recursion rule can turn an impractical algorithm into an efficient one. In the next lecture of this free embedded C course we move to Fibonacci numbers, where a function calls itself twice and the number of calls grows dramatically.
Frequently Asked Questions
What are the winding and unwinding phases in recursion?
Winding is the descent where each call invokes the next. Unwinding is the return trip after the base case, where each call finishes its pending work in reverse order.
How is a recursive power function in C different from the pow function in math.h?
The library function works on floating-point values and is highly optimised. A hand-written recursive version is mainly for learning, or for integer-only targets without a floating-point unit.
Why should the exponent be unsigned in recursive power?
An unsigned exponent can never be negative, so repeatedly subtracting one always reaches zero and the recursion terminates.
What is exponentiation by squaring?
It is a method that computes a power by repeatedly halving the exponent and squaring the intermediate result, needing only about log base 2 of n multiplications.
Do all recursive calls share the same local variables?
No. Each call has its own copy of parameters and local variables in its own stack frame. Only global and static variables are shared.
How can I check how much stack my recursive function uses?
Use compiler options such as -fstack-usage to see per-function frame sizes, then multiply by your worst-case depth, and confirm on hardware by filling the stack with a known pattern.
Keep Learning C for Free
Follow the whole free C programming course on EmbeddedPathashala and build the skills used in real firmware projects.

2 Comments