Lecture Notes Data Structures and Algorithms [18CS32]

Recursion
It is a process in which an object is defined in terms of simpler case of itself.

Direct Recursion
A function which calls itself repeatedly is called recursive function.
Ex: a ( formal parameters)
{
---------
--------- Dr. Mahesh G Dr. Harish G
a (arguments); Assoc. Prof. Assoc. Prof.
BMSIT&M Dr.AIT
---------
}

Note: The important requirements or constraints that every recursive function should satisfy
are
 Every time a function is called, it should be nearer to the solution.
 There should be at least one statement to terminate recursion.
The recursive function calls are initially pushed on to the stack until the terminating condition
is met. After encountering the terminating condition the recursive functions are popped from
the stack and executed.

Indirect Recursion
A recursive function need not call itself directly. Rather, it may contain a call to another
function which eventually calls the first function and both are termed recursive.
Ex: a ( formal parameters) b ( formal parameters)
{ {
--------- ---------
--------- ----------
b (arguments); a (arguments);
--------- ---------
} }

Here function ‘a’ calls ‘b’, which may in turn call ‘a’, which may again call ‘b’. Thus both ‘a’
and ‘b’ are recursive, since they indirectly call on themselves.
However the fact that they are recursive is not evident from examining the body of either of
the routines individually.

Module 2 31
Lecture Notes Data Structures and Algorithms [18CS32]

Example 1: Factorial Function

Given a positive integer ‘n’, n! is defined as the product of all integers between ‘n’ and 1. The
exclamation mark (!) is often used to denote the factorial function.
Ex: 5! = 5x4x3x2x1
3! = 3x2x1
0! = 1
The recursive definition to find the factorial of ‘n’
 1 if (n  0)
fact(n) =   Dr. Mahesh G Dr. Harish G
n * fact (n  1) otherwise  Assoc. Prof. Assoc. Prof.
BMSIT&M Dr.AIT
Ex: To compute 4!
4!=4x3!
3!=3x2!
2!=2x1!
1!=1x0!
0!=1
1!=1x1=1
2!=2x1=2
3!=3x2=6
4!=4x6=24

Recursive Program to find the factorial of a number

/*Function to find factorial of a number*/
int fact(int n)
{
if(n= = 0)
return 1;
return(n*fact(n-1));
}

void main( )
{
int n, result;
printf(“enter the value of n\n”);
scanf(“%d”, &n);
result = fact(n);
printf(“factorial of %d = %d\n”, n, result);
}

Module 2 32
Lecture Notes Data Structures and Algorithms [18CS32]

Example 2: Fibonacci Sequence

The Fibonacci sequence is the sequence of integers 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …….
The first two numbers 0 and 1 are the initial values. The nth Fibonacci number is the sum of
the two immediate preceding elements.
The recursive definition to find the nth Fibonacci number is given by
 0 if (n  1) 
 
Fib(n) =  1 if (n  2)
Fib(n  1)  Fib(n  2) otherwise
 
The recursive tree for fib(5) is as shown below

Recursive Program for Fibonacci number

Dr. Mahesh G Dr. Harish G
int fib(int n) Assoc. Prof. Assoc. Prof.
{ BMSIT&M Dr.AIT

if(n= = 1)
return 0;
if(n= = 2)
return 1;
return(fib(n-1)+ fib(n-2));
}

Main Function to find the nth Fibonacci number

void main( )
{
int n, result;
printf(“enter the value of n\n”);
scanf(“%d”, &n);
result = fib(n);
printf(“ %d fibonacci number = %d\n”, n, result);
}

Module 2 33
Lecture Notes Data Structures and Algorithms [18CS32]

Main Function to generate ‘n’ Fibonacci numbers

void main( )
{
int n, i;
printf(“enter the value of n\n”);
scanf(“%d”, &n);
printf(“The fibonacci numbers are\n”);
for(i=1; i<=n; i++)
printf(“ %d”,fib(i));
}

Example 3: GCD (Greatest Common Divisor)

The GCD of two numbers 'm' and 'n' denoted by GCD(m,n) is defined as the largest integer
that divides both 'm' and 'n' such that the remainder is zero.
Example: To find GCD(10, 30)
The numbers 1,2,5 and 10 can divide 10.
The numbers 1,2,3,5,6,10, 15 and 30 can divide 30.
The common divisors are 1,2,5 and 10. The Greatest Common Divisor (GCD) is 10
The recursive definition to find GCD of two numbers 'm' and 'n' is given by
 m if (m  n) 
 
GCD(m,n) =  GCD(m  n, n) if (m  n) 
GCD(m, n  m) if (m  n) 
 
Recursive Program to find GCD of two numbers 'm' and 'n'
/*Function to find GCD of 2 numbers*/
int GCD(int m, int n)
{ Dr. Mahesh G Dr. Harish G
if(m= = n) Assoc. Prof. Assoc. Prof.
BMSIT&M Dr.AIT
return m;
if(m > n)
return GCD(m-n, n);
if(m < n)
return GCD(m, n-m);

}
void main( )
{
int m, n, result;
printf(“enter the values of m and n\n”);
scanf(“%d%d”, &m,&n);
result = GCD(m,n);
printf(“GCD of %d and %d = %d\n”, m, n, result);
}

Module 2 34
Lecture Notes Data Structures and Algorithms [18CS32]

Example 4: Binomial Coefficient (nCr)

Binomial coefficients are a family of positive integers that occur as coefficients in the
binomial theorem. They are indexed by two non negative integers called the binomial
coefficient indexed by 'n' and 'r'. It is the coefficient of the Xr term in the polynomial
expansion of the binomial power (1+X)n.
In mathematics, it is denoted as nCr and is given by n! / (n-r)! * r!

The recursive definition to find nCr is given by

 1 if (n  1|| n  r ) 
C(n, r) =  
C (n  1, r  1)  C (n  1, r ) otherwise 
Recursive Program to find nCr
/*Function to find nCr*/
int C(int n, int r)
{ Dr. Mahesh G Dr. Harish G
if(n = = 1 || n = = r) Assoc. Prof. Assoc. Prof.
return 1; BMSIT&M Dr.AIT

return C(n-1, r-1) + C(n-1, r);

}
void main( )
{
int n, r, result;
printf(“enter the values of n and r\n”);
scanf(“%d%d”, &n,&r);
result = C(n, r);
printf(“%d C %d = %d\n”, n, r, result);
}
Alternative way using the mathematical definition nCr = n! / (n-r)! * r!

/*Function to find factorial of a number*/

int fact(int n)
{
if(n= = 0)
return 1;
return(n*fact(n-1));
}

void main( )
{
int n, r, result;
printf(“enter the values of n and r\n”);
scanf(“%d%d”, &n,&r);
result = fact(n) / fact(n-r) * fact(r);
printf(“%d C %d = %d\n”, n, r, result);
}

Module 2 35
Lecture Notes Data Structures and Algorithms [18CS32]

Example 5
The Towers of Hanoi Problem

The initial set up of the towers of Hanoi problem is as shown below.

Source ‘A’ Auxiliary ‘B’ Destination ‘C’

Three pegs A, B and C exists. There will be ‘n’ disks (in general) on Peg ‘A’ of different
diameters placed such that a larger disk is always below a smaller disk. The objective is to
move ‘n’ disks to peg ‘C’, using peg ‘B’ as auxiliary. The rules to be followed are
1. Only one disk is to be moved at a time.
2. Only the top disk on any peg may be moved to any other peg.
Dr. Mahesh G Dr. Harish G
3. A larger disk may never rest on a smaller one. Assoc. Prof. Assoc. Prof.
BMSIT&M Dr.AIT
Example of 3 Disks on Source
Source ‘A’ Auxiliary ‘B’ Destination ‘C’

Module 2 36
Lecture Notes Data Structures and Algorithms [18CS32]

Source ‘A’ Auxiliary ‘B’ Destination ‘C’

A recursive solution to the towers of Hanoi problem is as follows. Dr. Mahesh G Dr. Harish G
Assoc. Prof. Assoc. Prof.
To move ‘n’ disks from A to C, using B as auxiliary, BMSIT&M Dr.AIT

Step 1: If n==1, move the single disk from A to C and stop (trivial case).
Step 2: Recursively move the top n-1 disks from A to B, Using C as auxiliary.
Step 3: Move the nth disk from A to C.
Step 4: Recursively move the n-1 disks from B to C using A as auxiliary.

/*Recursive Program for Towers of Hanoi Problem*/

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

int count = 0;

Module 2 37
Lecture Notes Data Structures and Algorithms [18CS32]

void tower(int n, char source, char destination, char temp)

{
if(n = = 1)
{
printf("move %d disc from %c to %c\n",n,source,destination);
count++;
return;
}
tower(n-1, source, temp, destination);
printf("move %d disc from %c to %c\n",n,source,destination);
count++;
tower(n-1, temp, destination, source);
}
void main( )
{
int n;
clrscr( );
printf("enter the number of discs\n"); Dr. Mahesh G Dr. Harish G
Assoc. Prof. Assoc. Prof.
scanf("%d",&n); BMSIT&M Dr.AIT
tower(n,'a','c','b');
printf("the total number of disc moves=%d",count);
getch( );
}

Example 6
Ackerman’s Function
In computability theory, the Ackermann function, named after Wilhelm Ackermann, is one of
the simplest and earliest-discovered examples of a total computable function. The Ackermann
function is a classic recursive example in computer science. It is a function that grows very
quickly (in its value and in the size of its call tree). It is defined as follows:
 n 1 if (m  0) 
 
A(m,n) =  A(m  1,1) if (n  0) 
 A(m  1, ( A(m, n  1) otherwise
 

To see how the Ackermann function grows so quickly, it helps to expand out some simple
expressions using the rules in the original definition. For example, we can fully evaluate
A(1,2) in the following way:

Module 2 38