Data Structure Using C

BEC405D

Module 2: Recursion

Dr Maya B S
Associate Professor
Department of CSE
Bangalore Institute of Technology
Bangalore

1 [Link] B S, Associate Professor, CSE,BIT 6/25/2024

 Recursion
 Recursion is a process in which a procedure calls itself. In C
the function that calls itself is called as recursive function.
 Two types
1. Direct recursion – if the function A calls function A itself
2. Indirect recursion – if function A calls function B, function
B calls function A ( recursive chain)
 A recursive procedure must have the following 2 properties
1. There must be base criteria ( terminating condition) for
which procedure doesn’t calls itself
2. Successive recursive calls should lead towards base criteria

2 [Link] B S, Associate Professor, CSE,BIT 6/25/2024

3 [Link] B S, Associate Professor, CSE,BIT 6/25/2024
4 [Link] B S, Associate Professor, CSE,BIT 6/25/2024
 FACT(5) : 5*FACT(4)
4*FACT(3)
3*FACT(2)
2*FACT(1)
1*FACT(0) FACT(0)

1*1 FACT(1)
2* 1
FACT(2)
3*2
4*6 FACT(3)
FACT(5)
5*24

5 [Link] B S, Associate Professor, CSE,BIT 6/25/2024

 Recursion - Examples
 Recursion is implemented by means of Stacks.
 Factorial function – f(n) = n*f(n-1) for n != 0
f(n) = 1 for n = 0
Algorithm:
FACTOIAL (FACT, N)
This procedure calculates N! and returns the value in the variable FACT
1) If N = 0, then Set FACT := 1 and Return
2) Call FACTORIAL (FACT, N-1)
3) Set FACT := N * FACT
4) Return

6 [Link] B S, Associate Professor, CSE,BIT 6/25/2024

7 [Link] B S, Associate Professor, CSE,BIT 6/25/2024
 //To find the Factorial of a given number

#include<stdio.h>

int fact(int n)
{
//Factorial of 0 is 1
if(n==0)
return(1);

//Function calling itself: recursion

return(n* fact(n-1));
8 }
[Link] B S, Associate Professor, CSE,BIT 6/25/2024
 int main()
{
int num, fact;
//Ask user for the input and store it in num
printf("\nEnter any integer number:");
scanf("%d",&num);

//Displaying factorial of input number

printf("\nFactorial of %d is: %d",num, fact(num));
return 0;
}

9 [Link] B S, Associate Professor, CSE,BIT 6/25/2024

10 [Link] B S, Associate Professor, CSE,BIT 6/25/2024
11 [Link] B S, Associate Professor, CSE,BIT 6/25/2024
 GCD
 GCD – gcd(m, n) = gcd( n, m mod n) for n != 0
gcd (m,n) = m for n = 0
Algorithm:
GCD(m, n)
This procedure calculates the GCD of two numbers m, n and Returns
the value
1. If n=0 then, Set gcd := m; Return gcd
2. Call GCD ( n, m mod n)
3. End

12 [Link] B S, Associate Professor, CSE,BIT 6/25/2024

13 [Link] B S, Associate Professor, CSE,BIT 6/25/2024
 // Program to find the GCD of two numbers

#include <stdio.h>

int GCD(int a, int b)

{

if (b != 0)
return GCD(b, a % b);
else
return n1;

14 }
[Link] B S, Associate Professor, CSE,BIT 6/25/2024
 int main()
{
int a, b;
printf("Enter two positive integers:\n ");
scanf("%d %d", &a, &b);
printf("GCD of %d and %d is %d:", a, b, GCD(a, b));
return 0;
}

Assignment: Find the GCD of N numbers

15 (Note:
[Link] B S, Use
Associate0Professor,
to exit from the loop)
CSE,BIT 6/25/2024
16 [Link] B S, Associate Professor, CSE,BIT 6/25/2024
17 [Link] B S, Associate Professor, CSE,BIT 6/25/2024
 // Program to generate n fibonacci series

#include <stdio.h>

// fibonacci() funtion definition

int fibonacci(int num)
{
// first base condition check
if (num == 0)
{
return 0; // returning 0, if condition meets
}
18 [Link] B S, Associate Professor, CSE,BIT 6/25/2024
 // second base condition check
else if (num == 1)
{
return 1; // returning 1, if condition meets
}
// else calling the fibonacci() function recursively, till we get
to the base conditions
else
{
return fibonacci(num - 1) + fibonacci(num - 2); //
recursively calling the fibonacc() function and then adding them
}
}
19 [Link] B S, Associate Professor, CSE,BIT 6/25/2024
 int main()
{
int num, i; // variable to store how many elements to be
displayed in the series
printf("Enter the number of elements to be in the series : ");
scanf("%d", &num); // taking user input

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

{
printf("%d, ", fibonacci(i)); // calling fibonacci() function
for each iteration and printing the returned value
}
return 0;
20 [Link] B S, Associate Professor, CSE,BIT 6/25/2024
}
21 [Link] B S, Associate Professor, CSE,BIT 6/25/2024
 Example: Towers of Hanoi puzzle

In this puzzle, the player begins with n disks of decreasing

diameter placed one on top of the other on one of three pegs
of the game board. The player must move the disks from peg
to peg, using each of the three pegs, until the entire tower is
moved from the starting peg to one of the others. The only
rule governing the movement of the disks is that in each
move a disk of larger diameter must never be placed on top
of one of smaller diameter

22 [Link] B S, Associate Professor, CSE,BIT 6/25/2024

 Towers of Hanoi Puzzle

23 [Link] B S, Associate Professor, CSE,BIT 6/25/2024

 Towers of Hanoi Puzzle

24 [Link] B S, Associate Professor, CSE,BIT 6/25/2024

 Towers of Hanoi
Puzzle

25 [Link] B S, Associate Professor, CSE,BIT 6/25/2024

 Towers of Hanoi
Puzzle

26 [Link] B S, Associate Professor, CSE,BIT 6/25/2024

 Towers of Hanoi
Puzzle

27 [Link] B S, Associate Professor, CSE,BIT 6/25/2024

 Towers of Hanoi
Puzzle

28 [Link] B S, Associate Professor, CSE,BIT 6/25/2024

 Towers of Hanoi
Puzzle

29 [Link] B S, Associate Professor, CSE,BIT 6/25/2024

30 [Link] B S, Associate Professor, CSE,BIT 6/25/2024
 Solution to Tower of Hanoi Problem
 move top n-1 disks from source peg A to peg B using peg C as Auxpeg
 Transfer the remaining disk from peg A to peg C
 move n-1 disks from peg B to peg C using peg A as Auxpeg
Algorithm:
TOWER (N, Src, Aux, Dest)
//This procedure gives a recursive solution to the Towers of Hanoi problem for N disks
1) If N=1 then :
Write : move disk 1 from Src to Dest and Return
[ End of If structure ]
2) [ Move N-1 disks from peg Src to peg Aux ]
Call TOWER( N-1, Src, Dest, Aux)
3) Write : move disk N from Src to Dest
4) [ Move N-1 disks from peg Aux to peg Dest ]
Call TOWER( N-1, Aux,Src, Dest)
5) Return
31 [Link] B S, Associate Professor, CSE,BIT 6/25/2024
32 [Link] B S, Associate Professor, CSE,BIT 6/25/2024
 Recursive solution - Traces for n=3
Tower(3,A,B,C)
Tower(2,A,C,B)
Tower(1,A,B,C)
Move disk 1 from A to C
Move disk 2 from A to B
Tower(1,C,A,B)
Move disk 1 from C to B
Move disk 3 from A to C
Tower(2,B,A,C)
Tower(1,B,C,A)
Move disk 1 from B to A
Move disk 2 from B to C
Tower(1,A,B,C)
Move disk 1 from A to C
33 [Link] B S, Associate Professor, CSE,BIT 6/25/2024
 Binary Search Example

34 [Link] B S, Associate Professor, CSE,BIT 6/25/2024

35 [Link] B S, Associate Professor, CSE,BIT 6/25/2024
 Enter the number of elements to be in the series : 8
0, 1, 1, 2, 3, 5, 8, 13,

36 [Link] B S, Associate Professor, CSE,BIT 6/25/2024

 THANK YOU

37 [Link] B S, Associate Professor, CSE,BIT 6/25/2024