Recursion in C Language

Recursion in C

The process of calling a function by itself is called recursion and  the function which calls itself is called recursive function. Recursion is used to solve various mathematical problems by dividing it into smaller problems.

Syntax 

returntype recursive_func([argument list])

{

statements;

----

recursive_func([actula argument list])

---

}

Example 

#include<stdio.h>

main()

{

printf("hello world");

main();

return 0;

}

In this program, we are calling main() from main () which is recursion. But we haven't defined any condition for the program to exit. Hence this code will print "hello world" infinitely in the output screen.

Types of recursion 

Direct Recursion

Indirect Recursion

Example of Direct Recursion

int fibo (int n)
{
if (n= = 1 || n= =2)
return 1;
else
return (fibo(n-1) + fibo (n-2));
}

In this program, fibo() is a direct recursive function. This is because, inside fibo() function, there is a statement which calls fibo() function again directly.

Indirect Recursion

A function is said to be indirect recursive if it calls another function and this new function calls the first function again.

Example of Indirect Recursion

int fun1(int n)
{
if (n<=1)
return 1;
else
return fun2(n);
}
int fun2(int n)
{
return fun1(n);
}

In this program, fun1() calls fun2(), which is a new function. But this new function fun2() calls first calling function, fun1(), again. This makes the above function an indirect recursive function.

Program  to calculate factorial of number using recursion.

#include <stdio.h>
int factorial(int n)
{
if(n=0)
return 1;
else
return (factorial(n-1)*n);
}
int main()
{
int num, f;
printf("enter a number: ");
scanf("%d", &num);
f=factorial(num);
printf("factorial of %d = %d", num, f);
return 0;
}

Output

enter a number: 7
factorial of 7 = 5040

Here,

The number whose factorial is to be found is stored in the variable n.

A recursive function factorial(num) calculates the factorial of the number.

As factorial is (n-1)!*n, factorial function Calculates the factorial by recursively multiplying n with factorial of factorial of (n-1)l

Finally, when n=0, it returns 1 because 0! =1l

Disadvantages of Recursion

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

Recursive programs requires more memory to hold intermediate states in a stack. Non recursive programs don't have any intermediate states, hence they don't require any extra memory.