# Recursion

A self calling function is known as recursive function and this technique is known as recursion in C programming.

Example of recursion in C programming

Program to compute the sum of first n natural numbers using recursion.

```
#include<stdio.h>

int sum(int n);

void main()

{

int number,result;

printf("Enter a positive integer:\n");

scanf("%d",&number);

result=sum(number);

printf("The sum is %d\n",result);

}

int sum(int n)

{

if(n==0)

return n;

else

return n+sum(n-1);

}

```

OUTPUT:
Enter a positive integer: 5
15

In this program, sum() function is invoked from the same function. If the value of n is not equal to 0 then, the function calls itself passing argument 1 less than the previous argument it was called with. Suppose, n is 5 initially. Then, during the succeeding function calls, 4 is passed to function and the value of argument decreases by 1 in each recursive call. When the value of n becomes equal to 0, the value of n is returned which is the sum of numbers from 5 to 1.

For better visualization of recursion in this example:

sum(5)
=5+sum(4)
=5+4+sum(3)
=5+4+3+sum(2)
=5+4+3+2+sum(1)
=5+4+3+2+1+sum(0)
=5+4+3+2+1+0
=5+4+3+2+1
=5+4+3+3
=5+4+6
=5+10
=15

• Recursion is an elegant method and requires just a few variables which can make the program clean. Recursion can be used to replace complex nesting code by dividing the problem into various sub problems.
• On the other hand, it is difficult to think the logic of a recursive function. It is equally difficult to debug the code containing recursion.

### Programming and problem solving using Functions and Recursions

Write a C program to find the prime numbers between two intervals by making user-defined function

```
#include<stdio.h>

int prime(int num);

void main()

{

int num1,num2,i,count;

printf("Enter two numbers(intervals): ");

scanf("%d %d",&num1, &num2);

printf("The Prime numbers are: ");

for(i=num1+1;i<num2;++i)

{

count=prime(i);

if(count==0)

printf("%d ",i);
}

}

int prime(int num)

{

int j,count=0;

for(j=2;j<=num/2;++j)

{

if(num%j==0)

{

count=1;

break;

}

}

return count;

}

```

OUTPUT: Enter two numbers(intervals):
10 30
The Prime numbers are:
11 13 17 19 23 29

In this program, all numbers between two intervals is passed to function int prime(int num)using for loop. This function checks whether a number is prime or not. If the number is prime it returns 1 if not it return 0.

C Program to reverse a sentence using recursion.

```
#include <stdio.h>

void reverse();

void main()

{

printf("Enter a sentence: ");

reverse();

}

void reverse()

{
char ch;

scanf("%c",&ch);

if( ch != '\n')

{

reverse();

printf("%c",ch);
}

}

```

Output:
Enter a sentence:
Hello World
dlroW olleH

This program prints "Enter a sentence: " and then reverse() function is called. This function stores the first letter which has been entered by user and stores it in variable ch. If that variable is other than '\n' [enter character] then, again reverse() function is called. Do not assume this reverse() function and the reverse() function before is same although they both have same name. Additionally, the variables are also different, i.e., ch variable in both functions are also different.

Then, the second character is stored into variable ch of second Reverse function of the program. This process goes on until user enters '\n'. As and when the user enters '\n', the last function reverse() function returns to second last reverse() function and prints the last character. The Second last reverse() function returns to the third last reverse()function and prints the second last character. This process keeps going on and the final output obtained will be the reversed sentence.

<< Back