What is Recursion in C?

A process in which a function calls itself directly or indirectly is called Recursion in C and the corresponding function is called a Recursive function.

Recursion is a powerful technique of writing a complicated algorithm in an easy way.

According to this technique, a problem is defined in terms of itself. The problem is solved by dividing it into small problems, which are similar in nature to the original problem.

These smaller problems are solved and their solutions are applied to get the final solution to our original problem.

To implement recursion technique in programming, a function should be capable of calling itself and this facility is available in C.

There are two types of recursion namely, direct recursion and indirect recursion.

1. Direct Recursion:

If function definition contains, the function call itself then it is direct recursion.

Example:

Fun( )
{
…..
…..
Fun( );
}

2. Indirect Recursion:

If function fun1() calls another function fun2() and function fun2() calls function fun1(), then it is known as indirect recursion.

Example:

Fun2( )
{
…..
Fun1( );
}

Fun1( )
{
…..
Fun2( );
}

Every recursive function satisfies the following:

We should be able to define the solution to the problem in terms of a similar type of smaller problem. At each step, we get closer to the final solution to our original problem.

A recursive function must have a termination condition that must be satisfied. Otherwise, the recursive function will call itself indefinitely until a stack overflow error occurs.

Recursive functions work in two phases namely, Winding phase and Unwinding Phase.

In the winding phase, the function keeps on calling itself. The winding phases stop when the terminating condition arrives in a call, now the unwinding phase starts.

In the unwinding phase, the called functions return values in reverse order.

Now consider the problem of finding factorial of a number.

<div class="wp-block-codemirror-blocks-code-block code-block">
<pre>//Learnprogramo
#include<stdio.h>
int fact(int);
int main()
{
int num;
printf("Enter the number whose factorial is to be find :");
scanf("%%d" ,&num);
if(num<0)
{
printf("ERROR. Factorial is not defined for negative integers");
}
printf("Factorial of %%d is %%d", num, fact(num));
return 0;
}
int fact(int num)
{
if(num==0) //base condition
{
return 1;
}
else
{
return(num*fact(num-1)); //recursive call
}
}</pre>
</div>

Output:

recursion in c

Suppose we want to find out the factorial of 5.

Initially main( ) calls factorial(5).

5>0, factorial(5) calls factorial(4)
4>0, factorial(4) calls factorial(3)
3>0, factorial(3) calls factorial(2)
2>0, factorial(2) calls factorial(l)
1>0, factorial(l) calls factorial(0)

When factorial( ) is called with n=0 then the Condition inside if the statement becomes true, so now the recursion stops and control returns to factorial(l).

Now every called function will return the value to the previous function. These values are returned in reverse order of function calls.

Difference Between Recursion and Iteration:

Iteration uses a repetition statement whereas recursion does repetition through repeated function calls.

Iteration terminates when the loop condition fails whereas recursion terminates when the base became true.

Advantages of Recursion:

Recursion provides a clean and simple way to write code.

Some problems are inherently recursive like tree traversals, Tower of Hanoi, etc. For problems, it is preferred to write recursive code.

Using recursion, the length of the program can be reduced.

Disadvantages of Recursion:

Recursive programs are generally slower than non-recursive programs because it needs to function call, so the program must save all its current state and retrieve them again later,
consumes more time making recursive programs slower.

Recursive programs require more memory to hold intermediate states in a stack. Non-programs don’t have any intermediate states; hence they don’t require any extra memory.

If the programmer forgets to specify the exit condition in the recursive function, the program execute out of memory.

Example: Armstrong number program using recursion in c.

<div class="wp-block-codemirror-blocks-code-block code-block">
<pre>//Learnprogramo
#include <stdio.h>
#include <math.h>
int Check_Armstrong (int, int);
int main()
{
int Number, Sum = 0, Times =0,Temp;
printf("\nPlease Enter number to Check for Armstrong \n");
scanf("%%d", &Number);
Temp = Number;
while (Temp != 0) 
{
Times = Times + 1;
Temp = Temp / 10;
}
Sum = Check_Armstrong (Number, Times);
printf("Sum of entered number is = %%d\n", Sum);
if ( Number == Sum )
printf("\n%%d is Armstrong Number.\n", Number);
else
printf("%%d is not the Armstrong Number.\n", Number);
return 0;
}
int Check_Armstrong (int Number, int Times)
{
static int Reminder, Sum = 0;
if (Number > 0)
{
Reminder = Number %%10;
Sum = Sum + pow(Reminder, Times);
Check_Armstrong (Number /10, Times);
return Sum;
}
else
return 0;
}</pre>
</div>

Output:

recursion in c

Scope of Variables:

Every variable in a program has a memory associated with it. The memory requirement of variables is different for different types of variables in C. Memory is allocated and released at different places.

A scope in any programming is a region of the program where a defined variable can have its existence and beyond that variable cannot be accessed.

Scope of a variable can be of two types namely, Block or Local scope and File or Global Scope.

1. Local Variables in C:

Variable is said to have a local scope if it is defined within a function or local block. Block scope i.e., Local scope of a variable is used to evaluate an expression at the block level. In short, we can say that local variables are in block scope.

Local variables are not visible or accessible outside the functions.

Example:

<div class="wp-block-codemirror-blocks-code-block code-block">
<pre>//Learnprogramo
int main(void) 
{
  int age = 37;
}</pre>
</div>

2. Global Variables in C:

Global variables are also called as File Scope. Variables defined within Global scope are called as Global variables.

Variable is said to have a global scope if it is defined outside the function and whose visibility is the entire program.

A global variable can be accessed by any function. That is, a global variable is available for use throughout your entire program after its declaration.

Example:

<div class="wp-block-codemirror-blocks-code-block code-block">
<pre>//Learnprogramo
int age = 37;
int main(void)
{
  /* ... */
}</pre>
</div>

Conclusion:

In this lesson we have learned about Recursion in C and Scope of Variables in C. Now, in the next lesson, we will storage classes in C.

Also Read: