What is Recursive Power Function in C- C Programming Training Institute In Hyderabad

🚀 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 →

Free C Programming Course | Functions | Lecture 35

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 unsigned integers and the double type

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.

Two phases of a recursive call
1

Winding

Calls go deeper. Stack grows. No result is produced yet. Ends when the base case is reached.

2

Turning point

The base case returns a known value without calling anything else.

3

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.

ItemStored how many timesWhere it lives
Machine instructions of the functionOnceFlash or code segment
Parameters and locals of each callOnce per active callStack
Return address of each callOnce per active callStack or link register
Global and static variablesOnce, shared by all callsData 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.

Recursive definition of power
ExponentRuleRole
n equals 0Result is 1Base case
n greater than 0a 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.

Stack contents when pow_simple(2.0, 3) reaches the base case
PositionFrameExponent heldWaiting to compute
Top (newest)pow_simple call 40Returns 1.0 now
Belowpow_simple call 312.0 multiplied by the result of call 4
Belowpow_simple call 222.0 multiplied by the result of call 3
Belowpow_simple call 132.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);
}
Warning: A zero base with a negative exponent divides by zero. Floating-point arithmetic produces infinity instead of crashing, but the value is still wrong for your application, so test for it explicitly.

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
How ipow_fast(3, 13) unwinds
CallExponentHalf result receivedResult returned
A13729729 x 729 x 3 = 1594323
B62727 x 27 = 729
C333 x 3 x 3 = 27
D111 x 1 x 3 = 3
E0–1 (base case)

Depth Comparison

ExponentCalls in simple versionCalls in squaring version
13145
1001018
1000100111

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

SymptomCauseFix
Crash on negative exponentExponent is a signed type that moves away from zeroUse an unsigned exponent and a wrapper for negatives
Result suddenly wrong for large exponentInteger overflow, for example 3 to the 21 does not fit in 32 bitsUse a wider type or check the range first
Output prints 0.000000 unexpectedlyWrong format specifier or integer divisionUse %f for double and 1.0 instead of 1
Slow for huge exponentsLinear recursionSwitch to exponentiation by squaring
Stack overflow at moderate inputFrame size larger than assumedMeasure 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.

💬 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 →