< Prev
Next >

# C - Recursion

Recursion is a technique when a function calls itself from its own code. Using C language, we can execute this technique by which a function will call itself to do a specific task. A function that can call itself from its own code is said to be a "recursive function".

To understand the technique of recursion, we will create two programs to do the same task of printing a numbers from 1 to 5 in successive steps. For example -
• Printing 1 in the first line.
• Printing 1 and 2 in the second line.
• Printing 1, 2 and 3 in the third line.
• Printing 1, 2, 3 and 4 in the fourth line
• Printing 1, 2, 3, 4 and 5 in the fifth line.

In the first program, we will see a simple function(a non-recursive function) doing the task and in the second program we will implement a recursive function doing the same task.

## A simple function(non-recursive) to print numbers from 1 to 5 in steps

Let's see the first program which implements a simple non-recursive function , which has used two for loops(one nested in another) to implement the task of printing the numbers from 1 to 5 in steps, as mentioned above.

``````/* A simple(non-recursive) function */

#include<stdio.h>

int main()
{
void steps(int);  /* function prototype declaration */

int i=1;
steps(i);

return 0;
}

void steps(int a)
{

for(int x=a;x<=5;x++)
{
for(int y=1;y<=x;y++)
{
printf("%d ",y);
}
printf("\n");
}
}``````

## Output

``````1
1 2
1 2 3
1 2 3 4
1 2 3 4 5``````

## Recursive function to print numbers from 1 to 5 in steps

Let's see the second program that implements a recursive function with the same name steps, which calls itself to print the numbers from 1 to 5 in successive steps.

``````/* A simple recursive function */

#include<stdio.h>

int main()
{
void steps();  /* function prototype declaration  */

int i=1;
steps(i);

return 0;
}

void steps(int a)
{
if(a<=5)
{
for(int x=1;x<=a;x++)
{
printf("%d ",x);
}
printf("\n");
steps(a+1);		/* recursive function calling itself from its own code */
}

}
``````

## Output

``````1
1 2
1 2 3
1 2 3 4
1 2 3 4 5``````

## Program Analysis

Let us understand our recursion program with a diagram -

As you can see in the self-explanatory diagram, the function steps() is called in successions, like -
• Starting the program, the main() function calls function steps(), which prints 1.
• Next time, the steps() function calls itself recursively for the first time, which prints 1,2
• Next time, the steps() function calls itself recursively for the second time, which prints 1,2,3
• Next time, the steps() function calls itself recursively for the third time, which prints 1,2,3,4
• Finally, the steps() function calls itself recursively for the fourth time, which prints 1,2,3,4,5

## Another example of Recursion

In the upcoming code example, we are going to find the factorial of 5 using a recursive function that calls itself.

``````/* Recursion Example - Finding Factorial */

#include<stdio.h>

int main()
{
int factor(int); /* function prototype declaration */

int num = 5;
int result = factor(5);

printf("Factorial of 5 is %d ", result);

return 0;
}

int factor(int a)
{
int result;

if(a==1)
return 1;
else
result = a * factor(a-1); /* recursive function factor has called itself */

return result;
}``````

## Output

``Factorial of 5 is 120``