# IIaRC: IIaRC is about Recursion in C

## What is a recursion In C

«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

I admit that is funny search some visual recursions

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

`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

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.

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

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

And This is a graphical representation of the increasing Stack

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

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); //9return (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

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