Understanding recursions and memory

Recursion is a very well-known concept in modern high-level programming languages. In this post, we will try to analyze the recursion in C language. I am pretty sure learning in C should be sufficient to understand this topic's implementation in other languages as well. Well, that's being said recursion are language agnostics just like loops but there is one catch; language should have some support for recursion optimization via tail recursion. In present time, every language has it.

Just to give a quick refresher, recursion or recursive function is the function that returns itself with new computed parameters. The incoming parameters determine the condition for the next call; if the terminating condition is met then, it will return some value else the cycle continues.

A recursive function has one terminating condition and, two phases: winding and unwinding. Let's understand this by a simple expression

// Calculates sum of digits
int recursive_sum(int num) {
  if (num == 1) {
    return num;
  } else {
    return num + recursive_sum(num - 1);
  }
}

Which is simply doing something like this:
F(5) = 5 + F(4); winding start
        4 + F(3);
            3 + F(2);
                2 + F(1); winding end
                1; terminating condition return
            2 + 1; unwinding start
        3 + 3;
    4 + 6;
  F(5) = 5 + 10; unwinding end

or in simple terms: F(x) -> F'(F''(x''));

Recursion can be subdivided into two parts:

1. Basic/traditional recursion
2. Tail recursion

A basic recursion is a recursion that has both winding and unwinding phase and tail recursion just has a winding phase. To fully comprehend the recursion we will be looking into how memory is utilized in a C program.

Whenever we start the execution of our program, memory is allocated for computations. The program can be divided into segments like variables, loops, constants, globals, functions, instructions so on and forth. The memory semantics are different for each segment. Our compiler utilizes the different regions of memory to execute the program, the regions are:

1. Code area
2. Static data area
3. Stack
4. Heap

Code area contains the instructions which your program executes as it advances.

Static data area stores the data that is declared by the program for the duration of its life cycle. Global variables, constants (Read-only) reside here along with the variables which can be modified during runtime.

Stack region is similar to the Stack data structure; it follows the LIFO, last in fast out principle. The stack stores the information about function call for the duration of its execution. Whenever we call a function, our compiler allocates some storage in the stack in a region called activation record or simply a stack frame. In simple terms Stack is an array where each block is a stack frame that stores some information about the function. The top frame is called a Stack pointer which will be updated to refer the most recent activation call.

The stack frame can be further divided into five separate regions to store different information about an activation call.

1. Incoming parameters
2. Return value
3. Temporary storage
4. Saved state information
5. Outgoing parameters

Incoming parameters are the parameters provided in the activation call. Outgoing parameters are the parameters that are passed onto the next call to function(next activation call). Temporary storage stores the data used during the execution. Saved state information is the saved information for reference when the activation terminates. The return value is simply the return of a function.

Heap or dynamic memory is the memory allocated at the runtime. When we cannot pre-allocate storage for our program, we may generally request, reserve, and free the memory as per our need. Malloc, calloc, realloc for memory allocation, and free to deallocate are used in C but most other programming languages do it by default by using something called ARC (Automatic reference control if ARC is 0 for some object then the memory gets freed).

In C memory leaks happen if we forget to call free and in other languages like Swift memory leak will happen if a Node is self-referencing i.e class referring to self, in that case, ARC will always be 1 even when the Class doesn't have any member. There are options of ways to solve this in the respective languages but they are beyond the scope of our main topic. There are memory leaks at stack level as well which we will be looking next, like how recursions could lead to stack overflow.

Copy by reference is generally dynamic memory while copy by value is static, or Class members(not in C) are stored in the heap and struct members in the stack. Accessing heap is costly than accessing stack so a little optimization trick is to use a struct.

Coming back to recursion, each function call in our recursive function is going to be stored in our stack frame along with the information associated with it. Now, let's look into a simple recursive code:

int recursive_sum(int num) {
  if (num == 1) {
    return num;
  } else {
    return num + recursive_sum(num - 1);
  }
}

int t_recursive_sum(int num, int sum = 0) {
  if (num == 0) {
   return sum;
  } else {
   return t_recursive_sum(num - 1, sum + num);
  }
}

int main() {
  printf("Basic: %d\n", recursive_sum(5));
  printf("Tail: %d\n", t_recursive_sum(5));
  return 0;
}

recursive_sum and t_recursive_sum both return the same value, essentially they are doing the same thing but what we abstracted is how they are doing it.

Let's say F(x) is recurive_sum(5);

F(5) -> 5 + (F(4) -> 4 + (F(3) -> 3 + (F(2) -> 2 + (F(1) -> 1))))
F(5) = 5 + F(4); // winding start
      4 + F(3);
         3 + F(2);
            2 + F(1); // winding end
               1; // terminating condition
            2 + 1; // unwinding start
         3 + 3;
      4 + 6;
F(5) = 5 + 10; // unwiding end

F'(x) is t_recursive_function(5);

F'(5, 0) -> F(4, 5) -> F(3, 9) -> F(2, 12) -> F(1, 14) -> F(0, 15)
F(5, 0) = F(4, 5);  // winding start
        F(3, 9);
           F(2, 12);
              F(1, 14);
                 F(0, 15);
                 15; // final return
no unwinding

Both F(x) and F'(x) are doing winding but F(x) is also doing unwinding. This means if there were n call till the first actual return (notice how many parentheses our F(5) has) then there will be n more returns before F(x) finally finishes the execution.

Since F(5) is doing some computations on each return so the stack frames which were used when we returned F(4)…F(1) are never freed this means if there were n calls then there are n stack frames still holding all the information about function variables and state. This means our stack will grow in size but what if it just cannot grow more? Well it will throw an error famously knows as Stack Overflow.

So our basic recursion is not only slow but dangerous as well. Tail recursion just returns the function itself and it finishes its execution (the function memory is freed as soon as it returns). To make it more clear think it like this in basic recursion the function never gets freed since it is doing something like this constant + F'(x) so in this case, the last function or stack frame gets freed first.

In our tail recursion, our stack pointer never updated to the next stack that is because as soon as the function returns, the memory used by it will be freed. It doesn't matter if it returns the next function, the point is next call will be independent of its parent as soon as it is called so we do not need to hold the memory. So we can just rewrite on the previous stack. This means more optimizations and no overflow :).

In conclusion, recursions can be avoided by using iteration but if you are using them then try to use tail recursion. You can practice on recursion if you look into greedy algorithms or divide and conquer(does binary search ring a bell?). If you want to see recursion more interactively you can check Algorithm Visualizations and how basic recursion is significantly improved by using iteration and memorization in the case of Fibonacci numbers.

Thanks for reading the post, please note this is by no means a deep dive into the memory topic but just an introduction. My goal was to understand how recursions and memory work for code optimization and how recursion is analogical with iterations, so I wrote this one to share whatever less I know. Have a good day :)