CHAPTER

6 Recursion

Chapter Outline
6.1 Recursion – as a different way of solving problems
6.2 Example programs
6.3 Quick sort
6.4 Merge sort
6.5 MCQ Questions with Solution
6.1 RECURSION – AS A DIFFERENT WAY OF SOLVING
PROBLEMS
 In C language, there is a concept to call a function from another function. It also support
the concept where function call itself.
 Definition: “Recursive function is a function, which is called repetitively by itself.”
Such function call is known as recursive call.

 Recursion includes several number of function call, but it is necessary to apply

terminate condition to come out from repetitively function call situation.

Syntax:

return_type func1(parameters)
{
………………….
………………….

func1(parameters);
}

int main()
{
……………….
……………….

func1(parameters);
}

 Generally, iterative solutions are more efficient than recursion since function call is
always overhead.
 Any problem that can be solved recursively, can also be solved iteratively. However,
some problems are best suited to be solved by the recursion, for example, tower of
Hanoi, Fibonacci series, factorial finding, etc.
 Recursion cannot be applied to all the problem, but it is more useful for the tasks that
can be defined in terms of similar subtasks.
 In recursive program solution of bigger problem is expressed in terms of smaller
problems.

For example, consider the scenario to determine factorial of number n, it can be

logically represented as:
int fact(int n)
{
 if (n < = 1)
return 1;

else
return n * fact(n-1);
}

 In order to understand execution flow of above finding factorial problem and to

understand how big problem can be represented by dividing problem in smaller sub
problem, consider the pictorial representation as below:

return 5 * factorial(4) = 120

return 4 * factorial(3) = 24

return 3 * factorial(2) = 6

return 2 * factorial(1) = 2

return 1 * factorial(0) = 1

 In order to find factorial of 5, recursive function needed factorial of 4. For the

calculation of factorial of 4, it calculates factorial of 3 and so on. In this manner
recursive function require greater space as all the functions will remain in stack until
base or final case is reached.
 It also has time overhead because of too many function call and return.

6.1.1 Difference between Recursion and Iteration:

Recursion Iteration
In recursion, statements inside the body of Iteration allows the set of instructions to be
function calls the function itself. executed repetitively.
In recursion, only terminate condition is Iteration includes initialization, condition,
necessary to specify to come out from block of statements and updating in control
function. variable. It keep iterating until a certain
condition is reached.
Infinite recursion can crash the system. Infinite loop uses CPU cycles repeatedly.
 Stack is used to store the set of new variables It does not use stack and also no overhead of
and parameters, each time the function is repetitively calling function.
called. So, it possesses the overhead of
repeated function call.
It is slow in execution compare to iterative Comparatively iterative approach is faster
method. than recursive approach.
Recursive method reduces the size of the Code in iteration method is comparatively
code. longer.

AIM 6.1: Write a program to perform summation of digits of a given number without using
recursion.

#include<stdio.h>
#include<conio.h>

void main()
{
int num, temp, ans = 0;
clrscr();

printf(“Enter a number: \n ”);

scanf(“%d”,&num);

while(num != 0)
{
temp = num % 10;
ans = ans + temp;
num = num / 10;
}

printf(“Summation of digits of a number = %d”,ans);

}

OUTPUT:
Enter a number:
564
Summation of digits of a number = 15

AIM 6.2: Write a program to perform summation of digits of a given number using recursion.

#include<stdio.h>
#include<conio.h>
int sum(int);
void main()
{
int num, ans;
clrscr();

printf(“Enter a number: \n”);

scanf(“%d”,&num);
ans = sum(num);
printf(“\nSummation of digits of a number %d is = %d”,num, ans);

getch();
}

int sum(int n)
{
if(n == 0)
return n;

else
return (n%10) + sum(n / 10);
}

OUTPUT:
Enter a number:
564
Summation of digits of a number 564 is = 15

6.1.2 Types of recursion

 Recursions are of two types:
1. Direct recursion
2. Indirect recursion

Direct Recursion

 When a function call itself, this type of recursion is direct recursion.

 In direct recursion, only one function is involved and it calls itself until the given
condition is true.

Scenario of direct recursion:

int func()
{
…………..
…………..
 func();
}

Program:

AIM 6.3: Write a program to calculate triangular number using recursion.

#include<stdio.h>
#include<conio.h>
int triangle_num(int);

void main()
{
int num, ans;
clrscr();
printf(“Enter a number: \n”);
scanf(“%d”,&num);
ans = triangle_num(num);
printf(“\nTriangle number of %d is %d”,num, ans);
getch();
}

int triangle_num(int m)
{
int p = 0;
if(m == 0)
{
return m;
}

else
{
p = p + m + triangle_num(m - 1);
return p;
}
}

OUTPUT:
Enter a number:
4
Triangle number of 4 is 10
Indirect Recursion

 In this type of recursion, two or more functions are involved in the recursion.
 Advantage with indirect recursion is that it does not make any overhead. When control
exits from one function and enter into another function, the local variable of former
functions gets destroyed and memory also released.

Scenario of indirect recursion:

int func1()
{
…………..
…………..

func2();
}
int func2()
{
…………..
…………..

func1();
}
AIM 6.4: Write a program to demonstrate recursion between two functions.

#include<stdio.h>
#include<conio.h>
int m = 0;
void show(void);

void main()
{

if ( m == 5)
exit(0);
show();
}

void show()
{
printf(“ %d”, m);
m++;
 main();
}

OUTPUT:
01234

Here, in this example two functions are main() and show() are used. From the main() function
show() function is executed and from show() function main() function is called. When the value
of m reaches to 5, the program terminates.

6.2 EXAMPLE PROGRAMS

AIM 6.5: Write a program using function to find out factorial of given number by using
recursion.

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

void main()
{

int n, ans;
clrscr();

printf(“Enter one number: \n”);

scanf(“%d”,&n);
ans = fact(n);
printf(“Factorial of a given number %d is = %d”,n,ans);
getch();
}
int fact(int n)
{

if(n==1)
return n;
else
return n * fact(n-1);
}

OUTPUT:
Enter one number:
5
Factorial of a given number 5 is = 120

AIM 6.6: Write a program using function to display Fibonacci series with n elements by using
recursion.

#include<stdio.h>
#include<conio.h>
int Fibonacci(int);

int main()
{
int n, i = 0, c;
printf(“Enter value of n: \n”);
scanf("%d",&n);
printf("Fibonacci series: \n");

for ( c = 1 ; c <= n ; c++ )

{
printf("%d\n", Fibonacci(i));
i++;
}
return 0;
}
int Fibonacci(int n)
{
if ( n == 0 || n ==1)
return n;
else
return ( Fibonacci(n-1) + Fibonacci(n-2) );
}

OUTPUT:
Enter value of n:
7
Fibonacci series:
0112358

AIM 6.7: Write a C Program to implement Ackermann function using recursion.

NOTE: Definition: A function of two parameters whose value grows very fast. The
Ackermann function is a usually defined as follows:
 𝑛+1 𝑚=0
A(m, n) = { 𝐴(𝑚 − 1, 1) 𝑖𝑓 𝑚 > 0 𝑎𝑛𝑑 𝑛 = 0
𝐴(𝑚 − 1, 𝐴(𝑚, 𝑛 − 1)) 𝑖𝑓 𝑚 > 0 𝑎𝑛𝑑 𝑛 > 0

#include<stdio.h>
#include<conio.h>
int A(int m, int n);
void main()
{
int m, n;
printf("Enter two numbers :: \n");
scanf("%d%d",&m,&n);
printf("\nOUTPUT :: %d\n",A(m,n));
getch();
}

int A(int m, int n)

{

if(m==0)
return n+1;

else if(n==0)
return A(m-1, 1);

else
return A(m-1,A(m, n-1));
}

OUTPUT:
Enter two numbers ::
0
5

OUTPUT :: 6

6.3 QUICK SORT

 Sorting is a basic operation in computer science. It refers to the operation of arranging
data in some sequence i.e. increasing order or decreasing order.
 Let, p be a list of n elements p1, p2, p3, …, pn. Sorting of p means
 p1 ≤ p2 ≤ p3 ≤ p4 ….. ≤ pn
 QuickSort is a Divide and Conquer algorithm.
 It picks an element as pivot and partitions the given array around the picked pivot.
 The key process in quickSort is partition(). Target of partitions is, given an array and
an element x of array as pivot, put x at its correct position in sorted array and put all
smaller elements (smaller than x) before x, and put all greater elements (greater than x)
after x.

≤ pivot pivot > pivot

 Now, recursively sort each half (left and right part)

≤ p1 p1 > p1 pivot ≤ p2 p2 > p2

How quick sort work?

 It has two pointer, left and right indicating low and high end point of array respectively.
 We have to move left pointer while item pointed by that pointer is less than or equal to
pivot (item ≤ pivot). In other word, we have to stop moving left pointer when we have
element greater than pivot.
 On the other side, decrement right pointer while it points to item > pivot.
 When both pointer stop, we have to check whether left < right (not cross over) or not.
If it is true then,
swap (Arr[left], Arr[right])
otherwise,
swap (Arr[right], Arr[pivot])
Now, our array is divided into two parts. So, we have to sort that array recursively.

Example, high
low

23 12 15 38 42 18 36 29 27

left right
Here, pivot = Arr[low] = Arr[0] = 23

We have to increment left pointer while we are getting value ≤ pivot. For 23, 12 and 15 pointer
will be incremented.
We have to decrement right pointer while we are getting value > pivot.
After performing both pointer increment and decrement, final scenario array where both pointer
stops moving looks like as:
 Swap

23 12 15 38 42 18 36 29 27

left right

23 12 15 18 42 38 36 29 27

left right

 Same procedure will remain continue. After continuously moving left and right pointer,
the final scenario looks like as below where both left and right pointer crosses each
other.

23 12 15 18 42 38 36 29 27

right left

 Now, left < right condition becomes false and we have to swap Arr[right] and pivot
element.

18 12 15 23 42 38 36 29 27

Left part Right part

 Now, we have to divide array into two parts and we have to perform same procedure
on both the array. Final sorted list at the end of this procedure looks like as below:

12 15 18 23 27 29 36 38 42

Algorithm:
QuickSort (A, low, high)

if(low < high)

pivot = partition (A, low, high)
QuickSort(A, low, pivot)
QuickSort(A, pivot + 1, high)
partition(A, low, high)
pivot = A[low]
left = low
right = high

while(left < right)

{
while(A[left] ≤ pivot)
left++
while(A[right] > pivot)
right—

if(left < right)

swap(A[left], A[right])
}

swap(A[right], pivot)
return right;

AIM 6.8: Implement a sorting mechanism Quick Sort by using concept of recursion.

#include <stdio.h>
#include<conio.h>
void quicksort (int [], int, int);

int main()
{
int list[50];
int size, i;

printf("Enter the number of elements: ");

scanf("%d", &size);
printf("Enter the elements to be sorted:\n");

for (i = 0; i < size; i++)

{
scanf("%d", &list[i]);
}
quicksort(list, 0, size - 1);
printf("After applying quick sort\n");
for (i = 0; i < size; i++)
 {
printf("%d ", list[i]);
}
printf("\n");
return 0;
}

void quicksort(int list[], int low, int high)

{
int pivot, i, j, temp;

if (low < high)

{
pivot = low;

i = low;
j = high;

while (i < j)
{
while (list[i] <= list[pivot] && i <= high)
{

i++;
}
while (list[j] > list[pivot] && j >= low)

{
j--;
}
if (i < j)

{
temp = list[i];
list[i] = list[j];
list[j] = temp;
}
}

temp = list[j];
list[j] = list[pivot];
list[pivot] = temp;
 quicksort(list, low, j - 1);
quicksort(list, j + 1, high);
}
}

OUTPUT:
Enter the number of elements: 6
Enter the elements to be sorted:

67
45
24
98
12
38
After applying quick sort
12 24 38 45 67 98

6.4 MERGE SORT

 This is another flavour of sorting algorithm which is based on divide and conquer
method. It divide the array into equal half and then combines them in a sorted manner.

Working scenario with example:

 To understand this consider one simple example with initially unsorted array,

14 33 27 10 35 19 42 44
 As merge sort first divides array elements into two equal sub parts, we have to divide
8 elements into two arrays of size 4.

14 33 27 10 35 19 42 44

 This division does not change sequence of elements in which they appear in original
array.

14 33 27 10 35 19 42 44

 Further divide these arrays and we will find scenario from where no further division
can be made.
 14 33 27 10 35 19 42 44

 Now, we have to combine these elements in the same manner the way we divided.
 We first compare the element for each list and then combine them into another list in a
sorted manner. We see that 14 and 33 are in sorted positions. We compare 27 and 10
and in the target list of 2 values we put 10 first, followed by 27.

14 33 10 27 19 35 42 44

 In the next iteration of the combining phase, we compare lists of two data values, and
merge them into a list of found data values placing all in a sorted order.

10 14 27 33 19 35 42 44

 After the final merging, the list should look like this −

10 14 19 27 33 35 42 44

Algorithm:
MergeSort(A, p, r)

if(p < r)
q  (p + r) /2

MergeSort(A, p, q)
MergeSort(A, q + 1, r)
Merge(A, p, q, r)

Algorithm Merge(A, p, q, r)
Let, i = p, j = q + 1 and k = 1

while(i <= q) and (j < r) do

if(A[i] <= A[j])
then B[k] = A[i]
k=k+1
i=i+1

else
B[k] = A[j]
k=k+1
i=i+1
 // If one of the sublist is over then

if(i > q) then

for index = j to r
do B[k] = A[index]
k=k+1

else for index = i to q

do B[k] = A[index]
k=k+1

for index = p to r
A[index] = B[index]

return.

AIM 6.9: Implement a sorting mechanism Merge Sort by using concept of recursion.

#include<stdio.h>
#include<conio.h>
void mergeSort(int [], int, int, int);
void partition(int [],int, int);

int main()
{
int list[50];
int i, size;

printf("Enter total number of elements:");

scanf("%d", &size);
printf("Enter the elements:\n");

for(i = 0; i < size; i++)

{
scanf("%d", &list[i]);
}

partition(list, 0, size - 1);

printf("After merge sort:\n");

for(i = 0;i < size; i++)

{
printf("%d ",list[i]);
}
 return 0;
}

void partition(int list[],int low,int high)

{
int mid;

if(low < high)

{
mid = (low + high) / 2;
partition(list, low, mid);
partition(list, mid + 1, high);
mergeSort(list, low, mid, high);
}
}

void mergeSort(int list[],int low,int mid,int high)

{
int i, mi, k, lo, temp[50];
lo = low;
i = low;
mi = mid + 1;

while ((lo <= mid) && (mi <= high))

{
if (list[lo] <= list[mi])
{
temp[i] = list[lo];
lo++;
}

else
{
temp[i] = list[mi];
mi++;
}

i++;
}

if (lo > mid)

{
for (k = mi; k <= high; k++)
{
temp[i] = list[k];
i++;
}
}
 else
{
for (k = lo; k <= mid; k++)
{
temp[i] = list[k];
i++;
}
}

for (k = low; k <= high; k++)

{
list[k] = temp[k];
}
}

OUTPUT:
Enter total number of elements:5
Enter the elements:
12
36
22
76
54
After merge sort:
12 22 36 54 76

6.5 MCQ QUESTIONS WITH SOLUTION

1) Recursion is a method in which the solution of a problem depends on ____________

(a) Larger instances of different problems (b) Larger instances of same problems
(c) Smaller instances of the same problem (d) Smaller instances of different
problems
Ans. C - Smaller instances of the same problem

Explanation: In recursion, the solution of a problem depends on the solution of smaller

instances of the same problem.

2) Which of the following problems can be solved using recursion?

 (a) Factorial of a number (b) Tower of hanoi
(c) Length of a string (d) All of the above
Ans. D – All of the above

Explanation: All of the above mentioned problems can be solved using recursion.

3) Recursion is similar to which of the following?

(a) Switch Case (b) Loop

(c) if-else (d) All of the above
Ans. B - Loop

Explanation: Same task that performed with recursion can be implemented using iteration.
Iteration is achieved with the help of loop.

4) Consider the following code snippet:

void my_recursive_function()
{
my_recursive_function();
}

int main()
{
my_recursive_function();
return 0;
}
What will happen when the above snippet is executed?

(a) The code will be executed successfully (b) The code will be executed successfully
and no output will be generated and random output will be generated
(c) The code will show a compile time (d) The code will run for some time and
error stop when the stack overflows
Ans. D - The code will run for some time and stop when the stack overflows

Explanation: Every function call is stored in the stack memory. In this case, there is no
terminating condition (base case). So, my_recursive_function() will be called continuously
till the stack overflows and there is no more space to store the function calls. At this point of
time, the program will stop abruptly.

5) What is the output of the following code?

void my_recursive_function(int n)
{
if(n == 0)
return;
printf("%d ",n);

my_recursive_function(n-1);
}

int main()
{
my_recursive_function(10);
return 0;
}

(a) 10 (b) 1
(c) 10 9 8….1 0 (d) 10 9 8….1
Ans. D - 10 9 8….1

Explanation: The program prints the numbers from 10 to 1. Because whenever value of n
becomes 0 it returns from that function without printing 0.

6) Which of the following statements is true?

(a) Recursion is always better than (b) Recursion uses more memory
iteration compared to iteration
(c) Recursion uses less memory compared (d) Iteration is always better and simpler
to iteration than recursion
Ans. B - Recursion uses more memory compared to iteration

Explanation: Recursion uses more memory compared to iteration because every time the
recursive function is called, the function call is stored in stack.

7) What is the output of the following code?

int cnt = 0;
void my_recursive_function(char *s, int i)
{
 if(s[i] == '\0')
return;

if(s[i] == 'a' || s[i] == 'e' || s[i] == 'i' || s[i] == 'o' || s[i] == 'u')
cnt++;
my_recursive_function(s,i+1);
}
int main()

{
my_recursive_function("thisisrecursion",0);
printf("%d",cnt);
return 0;
}

(a) 6 (b) 9
(c) 5 (d) 10
Ans. A - 6

Explanation: The function counts the number of vowels in a string. In this case the number
is vowels is 6.

8) Which Data Structure is used to perform Recursion?

(a) Queue (b) Stack

(c) Linked List (d) Tree
Ans. B – Stack

Explanation: Stack data structure is used to perform recursion. Recursion use system stack
for storing the return addresses of the function calls.

9) What’s happen if base condition is not defined in recursion?

(a) Stack Underflow (b) Stack Overflow

(c) None of these (d) Both a and b
Ans. B – Stack Overflow

Explanation: When base condition is not defined in recursion, it will run infinitely until
stack overflow (It is a situation in which computer program tries to use more memory space
than the call stack has available).

10) How many times is the recursive function called, when the following code is executed?
void my_recursive_function(int n)
{

if(n == 0)
return;

printf("%d ",n);
my_recursive_function(n-1);
}

int main()
{
my_recursive_function(10);
return 0;
}

(a) 9 (b) 10
(c) 11 (d) 12
Ans. C - 11

Explanation: The recursive function is called 11 times.