A function that calls itself.
Until it doesn't.

// NOT tail recursive: the stack grows with n.
fn sum_wrong(n: u64) -> u64 {
    if n == 0 { return 0; }
    n + sum_wrong(n - 1)
    // the addition happens AFTER the call returns,
    // so this frame must stay on the stack to finish.
    // n = 100,000 -> 100,000 frames -> overflow
}

// Tail recursive: the stack stays constant.
fn sum_tail(n: u64, acc: u64) -> u64 {
    if n == 0 { return acc; }
    sum_tail(n - 1, acc + n)
    // the addition happens BEFORE the call.
    // nothing is left to do after, so the compiler
    // can reuse the frame: this becomes a loop.
}

fn sum(n: u64) -> u64 {
    sum_tail(n, 0) // public API hides the accumulator
}

// Rust does not guarantee tail-call optimisation, but LLVM
// often applies it in release builds. For a guarantee, use a
// loop or the trampoline pattern below.

#include <stdint.h>

/* NOT tail recursive. */
uint64_t sum_wrong(uint64_t n) {
    if (n == 0) return 0;
    return n + sum_wrong(n - 1); /* add after the call returns */
                                 /* so the frame stays alive */
}

/* Tail recursive: GCC and Clang optimise this with -O2. */
uint64_t sum_tail(uint64_t n, uint64_t acc) {
    if (n == 0) return acc;
    return sum_tail(n - 1, acc + n); /* the last operation */
                                     /* becomes a jmp, not a call */
}

uint64_t sum(uint64_t n) {
    return sum_tail(n, 0);
}

/* Verify the tail call was optimised:
 *   gcc -O2 -S recursion.c
 * Look for 'jmp' instead of 'call' in the output. */

// A trampoline turns recursion into iteration, guaranteed,
// regardless of compiler support.
enum Bounce<T> {
    Done(T),
    More(Box<dyn FnOnce() -> Bounce<T>>),
}

fn trampoline<T>(mut bounce: Bounce<T>) -> T {
    loop {
        match bounce {
            Bounce::Done(val) => return val,
            Bounce::More(f) => bounce = f(),
            // each iteration replaces the closure.
            // no stack growth whatsoever.
        }
    }
}

fn fact_bounce(n: u64, acc: u64) -> Bounce<u64> {
    if n == 0 {
        Bounce::Done(acc)
    } else {
        Bounce::More(Box::new(move || fact_bounce(n - 1, acc * n)))
    }
}

fn factorial(n: u64) -> u64 {
    trampoline(fact_bounce(n, 1))
    // runs as a loop internally: zero stack growth, any n.
}

#include <stdint.h>

/* A trampoline in C using a small state struct. */
typedef struct Bounce {
    int      done;
    uint64_t value;
    uint64_t next_n;
    uint64_t next_acc;
} Bounce;

Bounce fact_bounce(uint64_t n, uint64_t acc) {
    if (n == 0) {
        return (Bounce){ .done = 1, .value = acc };
    }
    return (Bounce){
        .done     = 0,
        .next_n   = n - 1,
        .next_acc = acc * n,
    };
}

uint64_t factorial(uint64_t n) {
    Bounce b = fact_bounce(n, 1);
    while (!b.done) {                 /* iteration, not recursion */
        b = fact_bounce(b.next_n, b.next_acc);
    }
    return b.value;
    /* one frame, any n, no stack growth */
}

// Mutual recursion: two functions calling each other.
// Same stack risk as direct recursion.
fn is_even(n: u64) -> bool {
    if n == 0 { return true; }
    is_odd(n - 1) // calls is_odd
}

fn is_odd(n: u64) -> bool {
    if n == 0 { return false; }
    is_even(n - 1) // calls is_even
    // is_even -> is_odd -> is_even -> is_odd ...
    // n = 100,000 -> 100,000 frames -> overflow
}

// Safe version: one function, no mutual calls.
fn is_even_safe(n: u64) -> bool {
    n % 2 == 0 // O(1). No recursion. No stack.
}

#include <stdbool.h>
#include <stdint.h>

/* Mutual recursion: same stack risk as direct recursion. */
bool is_odd(uint64_t n);

bool is_even(uint64_t n) {
    if (n == 0) return true;
    return is_odd(n - 1);   /* calls is_odd */
}

bool is_odd(uint64_t n) {
    if (n == 0) return false;
    return is_even(n - 1);  /* calls is_even */
    /* is_even -> is_odd -> ... -> n frames -> overflow */
}

/* Safe version: no recursion, no stack. */
bool is_even_safe(uint64_t n) {
    return n % 2 == 0; /* O(1) */
}

// The blockchain is conceptually recursive: block N is valid
// only if block N-1 is valid, all the way back to genesis.
// But the chain is 800,000+ blocks deep. Recursion would need
// 800,000 frames and overflow on every machine. So: iterate.
fn validate_chain(tip: &Block) -> bool {
    let mut current = Some(tip);
    while let Some(block) = current {
        if !validate_block(block) {
            return false;
        }
        current = block.prev.as_deref(); // iterate backward
    }
    true
    // the recursive thinking is preserved.
    // the recursive implementation is forbidden.
}

/* Bitcoin Core validates the chain iteratively, never
 * recursively. 800,000 blocks at ~200 bytes per frame would be
 * 160MB of stack against an 8MB limit: instant overflow. */
void validate_chain(Block *tip) {
    Block *current = tip;
    while (current != NULL) {
        if (!validate_block(current)) {
            reject_chain();
            return;
        }
        current = current->prev; /* iterate backward */
    }
    /* one stack frame, 800,000 blocks, no overflow, ever */
}