</>EmbeddedInterview

What is recursion and why is it avoided in embedded code?

EasyC Programming

Short answer: Recursion is a function calling itself (directly or through other functions). Each call uses a new stack frame. It is avoided in embedded systems because the maximum stack depth depends on the input and cannot easily be bounded at compile time, stacks are small (often 512 bytes to a few KB per task), and a stack overflow on a microcontroller without an MPU silently corrupts other memory. MISRA C forbids recursion.

/* recursive: stack use grows with n */
unsigned fact_rec(unsigned n) { return n <= 1 ? 1 : n * fact_rec(n - 1); }

/* iterative: constant stack use */
unsigned fact_iter(unsigned n)
{
    unsigned r = 1;
    while (n > 1) r *= n--;
    return r;
}

Problems in detail

  • Unbounded stack: a recursive tree walk on a degenerate (linked-list shaped) tree goes as deep as the number of nodes.
  • Static analysis: tools that compute worst-case stack usage (-fstack-usage + call-graph analysis, StackAnalyzer) cannot give a bound for recursive call cycles.
  • Silent corruption: on a Cortex-M without stack limit checking, the stack grows into .bss or another task's stack. The failure appears somewhere else, much later.
  • Timing: deep recursion takes variable time, bad for real-time code.

How to replace recursion

  • Tail-recursive functions become simple loops.
  • Tree and graph traversals use an explicit stack (a fixed-size array) with a checked maximum depth.
  • Divide-and-conquer sorting: use heapsort or an iterative merge sort, or quicksort that recurses only on the smaller part (bounding depth to log₂ n) and loops on the larger.

If you must use recursion: prove a maximum depth (e.g. a parser limited to 8 nesting levels), check it at run time, and size the stack for it. Cortex-M33 (Armv8-M) has stack limit registers (MSPLIM/PSPLIM) that fault on overflow instead of corrupting memory.