Recursion, Holberton

IIaRC: IIaRC is about Recursion in C

What is a recursion In C

Let’s start with a simple definition of Recursion

«A thing is defined in terms of itself or of its type»

— Wikipedia

But what it means. Well, Let’s keep simple «It’s like search a word in a dictionary and find the word in the definition»

In these days that we are in quarantine and the virtual conferences are everywhere. We can find a recursion when we see our shared screen

Recursion in google meets

I admit that is funny search some visual recursions

Pooh’s recursion

But I want to explain is what happens when you use this concept in a program. C programming language is simple. There is an entry point and it do some stuffs with conditionals and loops. Also You can set some statements somewhere and call it as function.

Let’s take the last idea. If a function is a set of statements. What happens if one of these statements is a call to the function itself?

lets try it with this code

Infinity recursion

void recursive_fun(void)
{
   printf("I'm Unique\n");
   recursive_fun();
}
int main(void)
{
   recursive_fun();
   return (0);
}

As you can see, the function calls itself over and over again. but let me explain what happen inside this calls.

The RAM, the Recursion and the Stack

The RAM is one of the first devices that you hear about when someone talks about a computer. The RAM is a memory, obviously. But is the one on charge to load your program.

The RAM

Take this situation. First, you execute your program ./program and then the OS loads this program into the RAM memory.

⚠️CAUTION: The Memory allocation is not quite simple. For every instance, the OS sets a space in a virtual memory which is a combination of the RAM and the Disk. but for simplicity I’m going to encompass the concept

This “RAM” set the program information in 6 different areas. This is a visual representation

RAM Memory distribution

If we start from the Low Address

• The fist space is the Instructions set. It’s where every assembly instruction of your program are loaded.
• The second one is the Literals, This is where the string literals and constants are saved.
• The third one is the Static Data. Here are loaded the global variables.
• The Heap is the space where you as a programmer ask the OS for memory with malloc. It increases from Low Address to High Address.
• The Free memory is between the Heap and the Stack, and it’s the source of free memory used by them
• And finally the Stack. It is where the local variables are, the return address from the function calls and the input parameters are stored. It increase from the Higher address to the lowest address. We are going to talk about this space.

RAM distribution table

The Recursion and the Stack

Every time that we call a function, Some information is stored in the stack. The recursion will use this memory and if you are not careful about it. You would use all the free memory and crash the program (this is bad).
The recursion will end into a Segmentation Fault

Like the above example this is another example of an infinity recursion in C, but this time I removed the printf to show the Segmentation fault

running code showing a Segmentation Fault

void recursive_fun(void)
{
    recursive_fun();
}
int main(void)
{
    recursive_fun();
    return (0);
}

And This is a graphical representation of the increasing Stack

Stack Memory with recursion

If the stack increase without control it could try to write into a forbidden area of the memory. The Hardware knows it an it will send a signal to the O.S. This signal is the Segmentation Fault

In computing, a segmentation fault (often shortened to segfault) or access violation is a fault, or failure condition, raised by hardware with memory protection, notifying an operating system (OS) the software has attempted to access a restricted area of memory (a memory access violation) — Wikipedia

Let’s do an Exercise

You has this code

Let’s understand the code

float _pow_recursion(float x, float y)
{
    if (y == 0)
        return (1);
    if (y < 0)
        return (_pow_recursion(x, y + 1) / x);

    return (_pow_recursion(x, y - 1) * x);
}
int main(void)
{
    _pow_recursion(3,2);
    return (0);
}

In this code, we have the function _pow_recursion(base, exp) . This function could calculate the base to the exp power using recursion. (awesome, no?)

if the exp is 0, it will return 1

if (y == 0)
        return (1);

This is important because this is the break of the recursion, without it, the recursion could become into a infinity loop

it can calculate negative and positives exponents

if (y < 0)
        return (_pow_recursion(x, y + 1) / x);
return (_pow_recursion(x, y - 1) * x);

The code are going to call itself and decrementing the exponent by 1.

Additionally the function returns the base times the return of the recursion

return (_pow_recursion(x, y - 1) * x);

Let’s debug the code

First I’m going to create a visual for every recursion call

Free interpreted sequence diagram _pow_recursion

Now let me explain the diagram

• This diagram has 4 columns.
• Each column is a function call.
• The first line of each column has this syntax function_name(arg1, arg2)
• The first one is the main function.
• The columns 2,3,4 are _pow_recursion call.
• Every left-right arrow is a function call.
• Every right-left arrow is the return of the function.
• The program start and ends at the first column

Now that we has all this clarifications lets start:

Column 1 (The main)

The entry point of a program is The main function, and this is not an exception, The main calls the _pow_recursion function with the values 3,2 and let’s see what it does at the column 2

Column 2 (1st call)

The _pow_recursion is called and it checks the exit condition y==0 without this. It could do an infinity loop. The second condition is only for negatives values of y inputs, We won’t enter here. The next statement is a recursion call, it will send the base number (3) and the exponent minus 1 (1)

Column 3 (2nd call)

In this call it will call the recursion again but with an exponent minus 1 (0)

Column 4 (The return)

In this call. The exponent is 0 it will return the value 1

Column 3 (The return)

After the 4th column return the value 1. the code continue where it stop and it use the returned value as replacement of the function

return (_pow_recursion(x, y - 1) * x);
return (           1             * 3);
return (1 * 3);
return (3);

At this moment, the column 3 returns a value 3

Column 2 (The return)

As the above step, the column 3 return a value 3, and it replace the function and continue

return (_pow_recursion(x, y - 1) * x);
return (          3              * 3);
return (3 * 3);
return (9);

It return the value 9

Column 1 (Last step. The main again)

The column 2 returns the value 9 and the main gets the value 9 as return of the function _pow_recursion(3,2); after this. the function return 0 as the end of the program.

_pow_recursion(3,2); //9
return (0);

Curiosities

Recursion In The C Bible

in the C Programming language book by Brian Kernighan and Dennis Ritchie. If you search recursion in the index it will send you to the same page

Recursion in C programming language Book

Recursion in google

Let’s search recursion in google.com

Recursion in google Searching

It will suggest you «recursion» as another search

Examples of Recursion in Names

These programs use the same name in their definitions:

GNU = GNU’s not Unix
cURL = cURL Request Library
PHP = PHP: Hypertext Preprocessor

Conclusions

• A recursion needs an exit condition. Without it i could generate an infinite loop
• The behavior of a statement can change if it’s before or after the recursion
• The recursion is limited with the stack capacity
• DON’T use a recursion if you can do it with a for