Recursion

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

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:

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

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

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 number which has this index in the Fibonacci Sequence.

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

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