Showing posts with label Recursion in C. Show all posts
Showing posts with label Recursion in C. Show all posts

Friday, July 6, 2018

Recursion in C

When function is called within the same function, it is known as recursion in C. The function which calls the same function, is known as recursive function.

A function that calls itself, and doesn't perform any task after function call, is know as tail recursion. In tail recursion, we generally call the same function with return statement. An example of tail recursion is given below.





recursionfunction()
{
recursionfunction();//calling self function
}



How recursion works?





void recurse()
{
... .. ...
recurse();
... .. ...
}

int main()
{
... .. ...
recurse();
... .. ...
}



How recursion works

The recursion continues until some condition is met to prevent it.

To prevent infinite recursion, if...else statement (or similar approach) can be used where one branch makes the recursive call and other doesn't.

Ex: recursion in C

Let's see an example to print factorial number using tail recursion in C language.





#include<stdio.h>
int factorial (int n)
{
if ( n < 0)
return -1; /*Wrong value*/
if (n == 0)
return 1; /*Terminating condition*/
return (n * factorial (n -1));
}
int main(){
int fact=0;
fact=factorial(5);
printf("\n factorial of 5 is %d",fact);
return 0;
}



Output

factorial of 5 is 120

We can understand the above program of recursive method call by the figure given below.

c recursion program

Example: Sum of Natural Numbers Using Recursion





#include <stdio.h>
int sum(int n);

int main()
{
int number, result;

printf("Enter a positive integer: ");
scanf("%d", &number);

result = sum(number);

printf("sum=%d", result);
}

int sum(int num)
{
if (num!=0)
return num + sum(num-1); // sum() function calls itself
else
return num;
}



Output


Enter a positive integer:
3
6

Initially, the sum() is called from the main() function with number passed as an argument.

Suppose, the value of num is 3 initially. During next function call, 2 is passed to the sum() function. This process continues until num is equal to 0.

When num is equal to 0, the if condition fails and the else part is executed returning the sum of integers to the main() function.

Calculation of sum of natural number using recursion

Advantages and Disadvantages of Recursion

Recursion makes program elegant and cleaner. All algorithms can be defined recursively which makes it easier to visualize and prove.

If the speed of the program is vital then, you should avoid using recursion. Recursions use more memory and are generally slow. Instead, you can use loop.




Instagram



Tuesday, July 3, 2018

Recursion in C

When function is called within the same function, it is known as recursion in C. The function which calls the same function, is known as recursive function.

A function that calls itself, and doesn't perform any task after function call, is know as tail recursion. In tail recursion, we generally call the same function with return statement. An example of tail recursion is given below.

Let's see a simple example of recursion.

How recursion works?





void recurse()
{
... .. ...
recurse();
... .. ...
}

int main()
{
... .. ...
recurse();
... .. ...
}





How recursion works




recursionfunction()
{
recursionfunction();//calling self function
}



Example of tail recursion in C

Let's see an example to print factorial number using tail recursion in C language.





#include<stdio.h>
int factorial (int n)
{
if ( n < 0)
return -1; /*Wrong value*/
if (n == 0)
return 1; /*Terminating condition*/
return (n * factorial (n -1));
}
int main(){
int fact=0;
fact=factorial(5);
printf("\n factorial of 5 is %d",fact);
return 0;
}



Output

factorial of 5 is 120

We can understand the above program of recursive method call by the figure given below:

recursion in C
c recursion program

Example: Sum of Natural Numbers Using Recursion





#include <stdio.h>
int sum(int n);

int main()
{
int number, result;

printf("Enter a positive integer: ");
scanf("%d", &number);

result = sum(number);

printf("sum=%d", result);
}

int sum(int num)
{
if (num!=0)
return num + sum(num-1); // sum() function calls itself
else
return num;
}



Output

Enter a positive integer:

3

6

Initially, the sum() is called from the main() function with number passed as an argument.

Suppose, the value of num is 3 initially. During next function call, 2 is passed to the sum() function. This process continues until num is equal to 0.

When num is equal to 0, the if condition fails and the else part is executed returning the sum of integers to the main() function.

Sum of Natural Numbers Using Recursion

Advantages and Disadvantages of Recursion

Recursion makes program elegant and cleaner. All algorithms can be defined recursively which makes it easier to visualize and prove.

If the speed of the program is vital then, you should avoid using recursion. Recursions use more memory and are generally slow. Instead, you can use loop.




Instagram