Recursion
Tags: c, beginners
Published: 2019-08-26 17:11:08

If you google "recursion", Google asks you: "Do you mean: recursion".

 ![](https://thepracticaldev.s3.amazonaws.com/i/7cj7q2i5gotwrvwz8um7.jpg)

That's one silly joke, but it can tell us how much this topic is important that Google chose to add a built-in joke inside their search engine for it.

Anyways, although Recursion is considered one of the most hated subjects by students, it is not really such a difficult subject in practice and a very useful one.

Recursion is just a way for creating a loop by a function that calls to itself. That's all. Let's see an example. First, there is a code which uses a __`for`__ loop:
```cpp
#include <stdio.h>

void printHello(int times) {
    for (int i = times; i > 0; i--) {
        printf("Hello\n");
    }
}

int main() {
    printHello(3);
    // Success
    return 0;
}
```
As you've probably figured out, the above code just prints "Hello" exactly 3 times. Now, let's see the same code, but with recursion:
```cpp
#include <stdio.h>

void printHello(int times) {
    if (times <= 0) { // You can write instead: if (!times)
        return;
    }
    printf("Hello\n");
    printHello(--times);
}

int main() {
    printHello(3);
    // Success
    return 0;
}
```
This code __also__ prints:
```
Hello
Hello
Hello
```
>"But... why?"

Because the __`main`__ function calls __`printHello(3)`__. This function has __`times==3`__ and therefore its prints and calls itself: __`printHello(2)`__. Again, the condition is not met and the function prints and calls itself: __`printHello(1)`__. And again: __`printHello(0)`__. __Now__, finally, the condition is met and we return to __`printHello(1)`__. This function also finishes its scope and we return to __`printHello(2)`__. The same for this function and we return to __`printHello(3)`__. After that, we return to __`main`__ and the running of our code ends with exit code 0 (success).

> "What, what what?!"

The following flowchart will explain everything:
![Alt Text](https://thepracticaldev.s3.amazonaws.com/i/s4g29r75n1fzdc0ope4w.PNG)
As you can see, each __`printHello(n)`__ calls to __`printHello(n-1)`__ until we reach 0. Then, each __`printHello(k)`__ finishes its run, and return to its caller - the function __`printHello(k+1)`__. That's all!

Let's see another example. In this example, our application asks for an index from the user, and prints the [Fibonacci](https://en.wikipedia.org/wiki/Fibonacci_number) number which has this index in the Fibonacci Sequence.
```cpp
#include <stdio.h>

int fibonacci(int index){
	if (index == 0) {	      // First stop condition
		return 0;
	} else if (index == 1) {  // Second stop condition
		return 1;
	} else {
		// The recursive call
		return (fibonacci(index - 1) + fibonacci(index - 2));
	}
}

int main() {
	int index;
	// Gets an index from the user
	printf("Enter the index\n");
 	scanf("%d", &index);
	// Prints the number in the 
	printf("%d\n", fibonacci(index));
	// Success
	return 0;
}

```
The following flowchart explains what happens in this code for the index 4. Pay attention that each function has 2 recursive calls, and the first one is alway to the left:
![Alt Text](https://thepracticaldev.s3.amazonaws.com/i/9hly2md6q5yuqpi5tpoa.PNG)

In conclusion, each recursion function must have a stop condition and a recursive call (of course). If we don't have a stop condition, our recursive will be like an infinite loop - but in this case, our program will crash relatively fast, because its memory ends. Each function call creates new local variables and other things that the computer needs to save on its memory, and therefore, after a lot of recursive calls - our function may crash. Therefore, pay attention and __always make sure there is a limit to your recursion__.

Make sure you fully understand this subject - many interviewers like to give recursive questions in job interviews.

####__Always remember, it's much C-mpler than you thought!__

Regards,
Gilad