Recursion, Holberton

IIaRC: IIaRC is about 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»

Recursion in google meets
Pooh’s recursion
Infinity recursion
void recursive_fun(void)
{
printf("I'm Unique\n");
recursive_fun();
}
int main(void)
{
recursive_fun();
return (0);
}

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.

RAM Memory distribution
  • 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

running code showing a Segmentation Fault
void recursive_fun(void)
{
recursive_fun();
}
int main(void)
{
recursive_fun();
return (0);
}
Stack Memory with recursion

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);
}
if (y == 0)
return (1);
if (y < 0)
return (_pow_recursion(x, y + 1) / x);
return (_pow_recursion(x, y - 1) * x);
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
  • 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

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

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

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

Examples of Recursion in Names

These programs use the same name in their definitions:

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