codescracker
c

Recursion or Recursive Function in C



« Previous Tutorial Next Tutorial »

In this article, we will learn about recursion in C with example. That is, you will get the brief explanation or the working principle of a recursive function in C.

Definition of Recursive Function with Example

When a function calls itself during its definition or execution is known as recursive function. For example, a function name printFiveTime() calls itself to print anything say my name for five times as shown here in the following program:

// Example of Recursive function in C
// ------codescracker.com------

#include<stdio.h>
#include<conio.h>
int printFiveTime(int);
int main()
{
    printFiveTime(5);
    getch();
    return 0;
}
int printFiveTime(int t)
{
    if(t==0)
        return 0;
    else
    {
        printf("codescracker\n");
        printFiveTime(t-1);
    }
}

This program was written under Code::Blocks IDE. Here is the sample run:

recursion in c

As you can clearly see here in the program given above, inside the function printFiveTime(), the function calls itself. That is printFiveTime() gets called from inside the function definition. Therefore the above function printFiveTime() can be called as recursive function.

How a Recursive Function gets Executed ?

To execute a function in the application, inside the RAM, memory will be allocated (here memory is called stack memory). That is, to execute a function (or method or block), some amount of memory will be allocated inside the stack memory that is called frame. Particular amount of memory gets allocated for every function or method execution.

Therefore when we start the program given above, first operating system invokes main() function. So to main() function, some memory gets allocated. So here the main frame will be created. Therefore the amount of memory will be allocated to execute all the three statement given inside the main function of above program as shown here in the snapshot given below:

recursive function in c

As you can clearly see, frame for main() function gets created inside the stack memory. Here the first statement, we are calling printFiveTime() function, so for this function, another frame will be created like this:

c recursive function

In above figure, ------- represents other statements of the function printFiveTime(). Now let's back to the code, first we are passing 5 to the function printFiveTime(). So at first run, 5 gets passed to the function definition. Therefore function gets executed like this:

printf("codescracker\n");
printFiveTime(5-1);

While passing 5 to function printFiveTime() at first, the variable t holds 5. Program flow goes inside the function definition part, as 5 is not equal to 0, therefore program flow goes to else part, and the above two statements gets executed.

As t-1 or 5-1 gives 4, therefore we have just passed 4 to printFiveTime() function. Now for this function, another frame gets created. The frame continue creating until the value of t becomes 0 as shown in the image given here:

recursion c

In all the frame except printFiveTime(0), else block gets executed, but in last frame printFiveTime(0), the if block gets executed. In else block, following statement:

return 0;

gets executed. So here, Once all the function space gets clearly defined with its value, all the frame gets deleted. In recursive function, control goes in forward direction, until and unless all the frame's statement gets clearly executed. And in which order the control goes (in forward direction), in the same order the control should come back and where it starts the execution, there only it should complete the execution.

So here, when the value of t becomes 0, the program flow come back to where, from it starts the execution, and all the statement gets executed, and then the control goes to main function, and the last two statement gets executed that are:

getch();
return 0;

To clarify the above statement (about the flow of forward and backward direction in recursive function), you can print the value of t along with codescracker as shown in the following program:

// ------codescracker.com------

#include<stdio.h>
#include<conio.h>
int printFiveTime(int);
int main()
{
    printFiveTime(5);
    getch();
    return 0;
}
int printFiveTime(int t)
{
    if(t==0)
        return 0;
    else
    {
        printf("%d. codescracker\n", t);
        printFiveTime(t-1);
    }
}

The snapshot given below shows the sample run:

recursive function execution in c

« Previous Tutorial Next Tutorial »