Posted on

# 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:

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 :)

pentacular
• "Copy by reference is generally dynamic memory while copy by value is static"

I think you're going to need to elaborate on this, since it doesn't make a great deal of sense.

In what regard is 'copy by value' static?
In what regard is 'copy by reference' generally dynamic?

• "Tail recursion just returns the function itself"

I this there may be a typo here, since there's no requirement for a tail recursive function to return the function itself.

• "In conclusion, recursions can be avoided by using iteration"

Iteration is recursive.

In this article you where you write 'recursion', you should generally seem to mean 'calling functions'.
If you write "calling functions can often be avoided by using iteration", then it is certainly true.

Recursion, on the other hand, does not imply function calls.

Hey @pentacular , thanks for reading and yes you are right here by recursion I meant calling functions.

Here, copy by reference was in the context of referring to class objects, and copy by value meant struct members. Potentially what I could have written would have been pass by value and pass by reference since I'm writing about functions and their parameters.

Yeah there could be some typos, English is not my first language and writing posts is an effort to improve that. The general idea was to have an elaborated approach towards learning algorithms and why the recursive functions could be a bad idea over a simple for or while loop.

As a matter of fact, I have little to no professional experience with C, I am a javascript developer(trying to shift into C/C++) so the attempts more or less are just reflection of a little bit of self-learning.

Always open to suggestions and ways to improve. Thanks :)

pentacular

You're welcome.

Class and struct instances have the same semantics with respect to copying and passing.

To understand pass-by-reference and pass-by-value we need to think about arguments vs parameters.

``````int X = 1;
// X is an argument in the call to foo.
foo(X);
``````
``````// Y is a parameter in the function
void foo(int Y) { ... }
``````

With pass-by-value, Y is assigned the value of X.
Changing Y will not change X -- they are different variables.

With pass-by-reference, Y is a reference to X.
Changing Y will change X -- they are effectively the same variable.

There is no difference between class and struct instances with respect to this.

Thanks for this :) I completely understand it now and how I misused the concepts in the main article however aren't class objects always pass by reference ? in the context of C++.
@pentacular ^

pentacular

Consider the following code:

``````#include <iostream>

class Foo {
public:
Foo():v(0) {};
int v;
};

void bar(Foo x) {
x.v = 1;
}

int main() {
Foo a;
a.v = 0;
bar(a);
std::cout << "a.v is " << a.v;
return 0;
}
``````

What does this output and why? :)

This should print `1` but this is printing 0. My thinking is `x implicit reference to a` so if x changes a should also change.
If I do it like this explicitly `void bar(Foo& x)` then it is printing 1. I wonder what is happening behind the scenes here.
My source of the learning is from Bjarne c++ 4th edition ( First 2 section done). I also did C++ in 2015-16 during the final year in college I'm familiar with the syntax.
This is extremely helpful to me as I was looking for some guidance already :)

pentacular

The explanation is that your thinking is incorrect. :)

In the example x is not a reference, so a is passed by value.
The value of a is assigned to x, which is an independent variable.
So changes to x do not affect a.

There is no 'implicit reference' in C++.

When you change x to be Foo& , a is passed by reference.

This is the difference between pass by value and pass by reference, and class instances are passed by value as usual.