Recursion & Embedded

Disadvantages of recursion

Reucrsion, while useful for backtracking and Divide et Impera, has it’s down sides.

First, it consumes a lot of memory, whether is stack or heap. You can create a simple function:

int fibo(int n)
{
    if(n == 1 || n == 2) return 1;
    return fibo(n - 1) + fibo(n - 2);
}

Stack memory is organised like:

Every call to the function creates a new function frame that consumes sizeof(int) = 4(or 2) bytes This might seem insignifiant, but for an Arduino, which has 2KB and respectively 32KB of SRAM and DRAM it’s a lot. On embedded systems like the mentioned Arduino or ESP-32, heap and stack allocations should be kept to a minimum.

A beginner programmer might write a function like:

void mfill(char value)
{
  void* p = malloc(1000);
  memset(p, value, 1000);
  mfill(value);
}

This creates a memory leak, by infinitely calling mfill() and allocating 1000 bytes of heap memory each time. (Using memset avoids OS/compiler optimisations)

Second, it might not be efficient. For example, dynamic programming is different from Divide et Impera for calculating a value/solivng the problem just once and storing it in a vector/matrix.

Dynamic Programming problems include:

• longest common subset
• labyrinth problem
• backpack problem(discrete)