Explain Recursion with Example in C

C allows a function to call itself. This is called Recursion. Let’s see an example,

void main(void)
{
    main();
}

What happens when the program is compiled and run, main() function’s type, here for ex., is void and it doesn’t take any arguments. main() has only one statement, main(), calling to itself. When main() starts executing, it calls to itself, let’s say level 1, then level 1 main() executes and calls level 2 main() and so on indefinitely until program is aborted automatically on Linux.

Let’s take one more simple example,

/* down_recur.c -- program counts down ways */
#include <stdio.h>
void countdown(int);
 
int main(void)
{
    int num = 100;
    countdown(num);
 
    return 0;
}
 
void countdown(int count)
{
    if (count >= 1) {
        printf("%d\n", count);
	countdown(count--);
    }
}

Now, let’s analyse the above program. Function ‘countdown()’ doesn’t return any value to its calling function as its type is void. However it takes an integer value. Will ‘countdown()’, too, during its successive recursive calls to itself, end up in a program abnormally aborted or should this behave differently this time? let’s unravel this. When ‘main()’ called the ‘countdown()’ with integer ‘num’ with value 100, for the first time, say level 1, ‘countdown()’ executes instructions defined therein. Value of ‘count’ is tested and if condition founds to be true, displays current value of ‘count’ which is 100 and ‘countdown()’ calls to itself with ‘count’ minus 1. This is level 2 call to ‘countdown()’. Again ‘countdown()’ executes, tested value of ‘count’ if >= 1, if true, displays the current value, 99, of ‘count’ before ‘countdown()’ is again called to itself with ‘count’ minus 1. This is level 3 call. This way ‘countdown()’ recursively calls to itself until ‘count’ reduced to 0. At this point, test condition

    if (count >= 1) {
        printf("%d\n", count);
	countdown(--count);
        /* interesting when count-- is used! */
    }

failed and statements within if construct didn’t execute. So ‘countdown()’ further didn’t call to itself. Since type of recursive function ‘countdown()’ was void, every recursive call, beginnig from when recursion stopped, to the function doesn’t return any value to its previous level of recursive call.

Also, notice that each time ‘countdown()’ is called recursively, formal integer argument ‘count’ is created and it obtained copy of integer from previous recursive call of function ‘countdown()’. Therefore, there were created 101 integers with same name ‘count’, last one with value 0. Each ‘count’ is private/local to its function and so there’s no same name conflict.

Therefore, we observed here that we must design some condition in recursive function which during successive recursive calls eventually fails and recursion stops. If type of recursive function isn’t void, each recursive call only after recursion stopped returns that type of value to its calling function.