Recursion is a computational paradigm where a routine invokes itself to solve progressively smaller instances of a problem. This technique relies on two fundamental prerequisites to function correctly:

1. A terminal condition (base case) that halts further self-invocation.
2. A progressive reduction step that ensures each subsequent call moves closer to the terminal condition.

Failure to satisfy the first rule results in infinite execution, while violating the second leads to logical deadlocks or uncontrolled memory consumption. Both conditions are mandatory for stable execution.

Sequential Digit Extraction

Consider extracting individual digits from a positive integer in left-to-right order. An iterative approach typically employs modulo and division operators within a loop. The recursive equivalent divides the problem by delegating the higher-order digits to a deeper call level before processing the current least significant digit.

#include <stdio.h>

void print_sequential_digits(int number) {
    if (number >= 10) {
        print_sequential_digits(number / 10);
    }
    printf(" %d", number % 10);
}

int main(void) {
    int input = 0;
    scanf("%d", &input);
    print_sequential_digits(input);
    return 0;
}

While conditional branches can enforce termination, replacing control flow statements with loops inside a recursive function creates redundant logic that defeats the purpose of the pattern. Conversely, mutating the passed parameter via assignment obscures data flow and complicates debugging. Always preserve the original argument state when passing computed values to subsequent calls.

The Call Stack Mechanism

Self-referential functions operate successfully because the runtime environment allocates a dedicated memory region, known as a stack frame, for each invocation. Upon entry, parameters, local variables, and return addresses are pushed onto this frame. Execution proceeds until the base case triggers unwinding, at which point frames are popped sequentially until the initial caller resumes. Uncontrolled depth depletes available stack memory rapidly.

String Length Calculation Without Auxiliary Storage

Calculating character count without temporary counters demonstrates recursive decomposition effectively. By advancing a pointer past the null terminator, we reduce the task size incrementally.

#include <stdio.h>
#include <string.h>

// Iterative baseline for reference
size_t count_chars_iterative(const char* p) {
    size_t len = 0;
    while (*p != '\0') {
        ++len;
        ++p;
    }
    return len;
}

// Recursive implementation
size_t count_chars_recursive(const char* p) {
    if (*p == '\0') {
        return 0;
    }
    return 1 + count_chars_recursive(p + 1);
}

int main(void) {
    const char sample[] = "Hello";
    printf("%zu\n", count_chars_recursive(sample));
    return 0;
}

When manipulating pointers, distinguish between mutation variants. Pre-increment alters the pointer before evaluation, post-increment uses the original address then advances, whereas additive offset computes a new address without modifying the source variable. Relying on side-effect operators in complex expressions often introduces subtle bugs; explicit arithmetic addition is preferred for functional clarity.

Algorithmic Paradigm Shift: Recursion Versus Iteration

While recursive definitions align closely with mathematical formulations, they carry inherent overhead due to repeated frame allocation. Iterative constructs avoid this cost through controlled memory reuse.

Factorial Computation

The mathematical definition translates directly to code. However, deep recursion risks triggering a stack overflow exception, and standard integer types impose upper bounds on representable values.

#include <stdio.h>

unsigned long long factorial_recursive(unsigned int n) {
    if (n <= 1) return 1ULL;
    return n * factorial_recursive(n - 1);
}

unsigned long long factorial_iterative(unsigned int n) {
    unsigned long long result = 1ULL;
    for (unsigned int i = 2; i <= n; ++i) {
        result *= i;
    }
    return result;
}

Modifying the loop bound variable directly during traversal corrupts iteration continuity. Preserve loop limits by isolating them from calculation accumulators.

Fibonacci Sequence Generation

The sequence follows $F(n) = F(n-1) + F(n-2)$ with base values $F(0)=1, F(1)=1$. A naive recursive translation mirrors the definition precisely but suffers exponential time complexity due to massive overlapping subproblem recalculations.

#include <stdio.h>

unsigned long long fibonacci_recursive(unsigned int n) {
    if (n <= 1) return 1ULL;
    return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2);
}

Executing this for values exceeding 40 causes noticeable latency. Although stack overflow may not occur immediately due to alternating call depths that trigger early returns, computational redundancy remains prohibitive. Switching to an iterative pattern resolves performence bottlenecks efficiently.

#include <stdio.h>

unsigned long long fibonacci_optimized(unsigned int n) {
    if (n <= 1) return 1ULL;
    
    unsigned long long prev = 1ULL;
    unsigned long long curr = 1ULL;
    unsigned long long next = 0ULL;

    for (unsigned int i = 2; i <= n; ++i) {
        next = prev + curr;
        prev = curr;
        curr = next;
    }
    return curr;
}

int main(void) {
    unsigned int index = 0;
    scanf("%u", &index);
    printf("%llu\n", fibonacci_optimized(index));
    return 0;
}

Functional elegance does not universally equate to optimal execution. When evaluating algorithmic approaches, prioritize empirical characteristics such as temporal complexity, spatial footprint, and hardware constraints over syntactic simplicity. Select recursion when state encapsulation and hierarchical tree traversal simplify design; otherwise, default to iterative patterns for linear progression problems requiring maximum throughput.