Data Structure and Algorithms

[Link]

Recursion

Recursion is deceptively simple in statement but exceptionally complicated

in implementation. Recursive procedures work fine in many problems. Many
programmers prefer recursion through simpler alternatives are available. It
is because recursion is elegant to use through it is costly in terms of time
and space. But using it is one thing and getting involved with it is another.

➔Importance to Recursion:
A function is recursive if a statement in the body of the function calls itself.
Recursion is the process of defining something in terms of itself. For a
computer language to be recursive, a function must be able to call itself.

For example, let us consider the function factr() shown below, which
computers the factorial of an integer.

public class Factorial {

public static void main(String[] args) {

int num = 6;
long factorial = multiplyNumbers(num);
[Link]("Factorial of " + num + " = " +
factorial);
}
public static long multiplyNumbers(int num)
{
if (num >= 1)
return num * multiplyNumbers(num - 1);
else
return 1;
}
}

©Topperworld
Data Structure and Algorithms

A non-recursive or iterative version for finding the factorial is

as follows:

factorial (int n)
{ int i, result = 1; if
(n == 0)
return (result);
else
{ for (i=1; i<=n; i++)
result = result * i;
}
return (result);
}

The operation of the non-recursive version is clear as it uses a loop starting

at 1 and ending at the target value and progressively multiplies each
number by the moving product.

When a function calls itself, new local variables and parameters are
allocated storage on the stack and the function code is executed with these
new variables from the start. A recursive call does not make a new copy of
the function. Only the arguments and variables are new. As each recursive
call returns, the old local variables and parameters are removed from the
stack and execution resumes at the point of the function call inside the
function.

When writing recursive functions, you must have a exit condition

somewhere to force the function to return without the recursive call being
executed. If you do not have an exit condition, the recursive function will
recurse forever until you run out of stack space and indicate error about
lack of memory, or stack overflow.

➔Differences between recursion and iteration:

• Both involve repetition.
• Both involve a termination test.
• Both can occur infinitely.

©Topperworld
Data Structure and Algorithms

Iteration Recursion
Iteration explicitly user a Recursion achieves repetition
repetition structure. through repeated function calls.
Iteration terminates when the Recursion terminates when a
loop continuation. base case is recognized.
Iteration keeps modifying the Recursion keeps producing
counter until the loop simple versions of the original
continuation condition fails. problem until the base case is
reached.
Iteration normally occurs within a Recursion causes another copy of
loop so the extra memory the function and hence a
assigned is omitted. considerable memory space’s
occupied.
It reduces the processor’s It increases the processor’s
operating time. operating time.

➔Factorial of a given number:

The operation of recursive factorial function is as follows:

Start out with some natural number N (in our example, 5). The recursive
definition is:

n = 0, 0 ! = 1 Base Case
n > 0, n ! = n * (n - 1) ! Recursive Case

Recursion Factorials:

5! =5 * 4! = 5 *___ = ____ factr(5) = 5 * factr(4) = __

4! = 4 *3! = 4 *___ = ___ factr(4) = 4 * factr(3) = __
3! = 3 * 2! = 3 * ___ = ___ factr(3) = 3 * factr(2) = __
2! = 2 * 1! = 2 * ___ = ___ factr(2) = 2 * factr(1) = __
1! = 1 * 0! = 1 * __ = __ factr(1) = 1 * factr(0) = __
0! = 1 factr(0) = __

5! = 5*4! = 5*4*3! = 5*4*3*2! = 5*4*3*2*1! = 5*4*3*2*1*0! =

5*4*3*2*1*1
=120

©Topperworld
Data Structure and Algorithms

We define 0! to equal 1, and we define factorial N (where N > 0), to be N *

factorial (N-1). All recursive functions must have an exit condition, that is
a state when it does not recurse upon itself. Our exit condition in this
example is when N = 0.

Tracing of the flow of the factorial () function:

When the factorial function is first called with, say, N = 5, here is what
happens:

FUNCTION:
Does N = 0? No
Function Return Value = 5 * factorial (4)

At this time, the function factorial is called again, with N = 4.

FUNCTION:
Does N = 0? No
Function Return Value = 4 * factorial (3)

At this time, the function factorial is called again, with N = 3.

FUNCTION:
Does N = 0? No
Function Return Value = 3 * factorial (2)

At this time, the function factorial is called again, with N = 2.

FUNCTION:
Does N = 0? No
Function Return Value = 2 * factorial (1)

At this time, the function factorial is called again, with N = 1.

FUNCTION:
Does N = 0? No
Function Return Value = 1 * factorial (0)

At this time, the function factorial is called again, with N = 0.

FUNCTION:
Does N = 0? Yes
Function Return Value = 1
Now, we have to trace our way back up! See, the factorial function was
called six times. At any function level call, all function level calls above still

©Topperworld
Data Structure and Algorithms

exist! So, when we have N = 2, the function instances where N = 3, 4, and

5 are still waiting for their return values.

So, the function call where N = 1 gets retraced first, once the final call
returns 0. So, the function call where N = 1 returns 1*1, or 1. The next
higher function call, where N = 2, returns 2 * 1 (1, because that's what the
function call where N = 1 returned). You just keep working up the chain.

When N = 2, 2 * 1, or 2 was returned.

When N = 3, 3 * 2, or 6 was returned.
When N = 4, 4 * 6, or 24 was returned.
When N = 5, 5 * 24, or 120 was returned.

And since N = 5 was the first function call (hence the last one to be
recalled), the value 120 is returned.

➔The Towers of Hanoi:

In the game of Towers of Hanoi, there are three towers labeled 1, 2, and 3.
The game starts with n disks on tower A. For simplicity, let n is 3. The disks
are numbered from 1 to 3, and without loss of generality we may assume
that the diameter of each disk is the same as its number. That is, disk 1
has diameter 1 (in some unit of measure), disk 2 has diameter 2, and disk
3 has diameter 3. All three disks start on tower A in the order 1, 2, 3. The
objective of the game is to move all the disks in tower 1 to entire tower 3
using tower 2. That is, at no time can a larger disk be placed on a smaller
disk.

Figure , illustrates the initial setup of towers of Hanoi. The figure , illustrates
the final setup of towers of Hanoi.

The rules to be followed in moving the disks from tower 1 tower 3

using tower 2 are as follows:

• Only one disk can be moved at a time.

• Only the top disc on any tower can be moved to any other tower.
• A larger disk cannot be placed on a smaller disk.

©Topperworld
Data Structure and Algorithms

Tower 1 Tower 2 Tower 3

Fig. 3.11.1. Initial setup of Towers of Hanoi

Tower 1 Tower 2 Tower 3

Fig 3.11.2. Final setup of Towers of Hanoi

The towers of Hanoi problem can be easily implemented using recursion.

To move the largest disk to the bottom of tower 3, we move the remaining
n – 1 disks to tower 2 and then move the largest disk to tower 3. Now we
have the remaining n – 1 disks to be moved to tower 3. This can be achieved
by using the remaining two towers. We can also use tower 3 to place any
disk on it, since the disk placed on tower 3 is the largest disk and continue
the same operation to place the entire disks in tower 3 in order.

The program that uses recursion to produce a list of moves that shows how
to accomplish the task of transferring the n disks from tower 1 to tower 3
is as follows:

public class TowerOfHanoi {

public static void towerOfHanoi(int n, char source, char
auxiliary, char destination) {
if (n == 1) {
[Link]("Move disk 1 from " + source + "
to " + destination);
return;
}
towerOfHanoi(n - 1, source, destination, auxiliary);

©Topperworld
Data Structure and Algorithms

[Link]("Move disk " + n + " from " + source +

" to " + destination);
towerOfHanoi(n - 1, auxiliary, source, destination);
}

public static void main(String[] args) {

int n = 3; // Number of disks
towerOfHanoi(n, 'A', 'B', 'C');
}
}

OUTPUT:-
Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C

➔Fibonacci Sequence Problem:

A Fibonacci sequence starts with the integers 0 and 1. Successive elements

in this sequence are obtained by summing the preceding two elements in
the sequence. For example, third number in the sequence is 0 + 1 = 1,
fourth number is 1 + 1= 2, fifth number is 1 + 2 = 3 and so on. The
sequence of Fibonacci integers is given below:

0 1 1 2 3 5 8 13 21 . . . . . . . . .

A recursive definition for the Fibonacci sequence of integers may be defined

as follows:

Fib (n) = n if n = 0 or n = 1
Fib (n) = fib (n-1) + fib (n-2) for n >=2

We will now use the definition to compute fib(5):

©Topperworld
Data Structure and Algorithms

fib(5) = fib(4) + fib(3)

fib(3) + fib(2) + fib(3) fib(2) +

fib(1) + fib(2) + fib(3) fib(1) +

fib(0) + fib(1) + fib(2) + fib(3)

1 + 0 + 1 + fib(1) + fib(0) + fib(3)

1 + 0 + 1 + 1 + 0 + fib(2) + fib(1)

1 + 0 + 1 + 1 + 0 + fib(1) + fib(0) + fib(1)

1+0+1+1+0+1+0+1=5

We see that fib(2) is computed 3 times, and fib(3), 2 times in the above
calculations. We save the values of fib(2) or fib(3) and reuse them
whenever needed.

A recursive function to compute the Fibonacci number in the n th position is

given below:

public class Fibonacci {

public static int fibonacci(int n) {
if (n <= 1) {
return n;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}

public static void main(String[] args) {

int n = 5; // Change this to compute Fibonacci number at
a different position
int result = fibonacci(n);
[Link]("Fibonacci number at position " + n +
" is: " + result);
}
}

©Topperworld
Data Structure and Algorithms

Output:

fib(5) is 5

Program using recursion to calculate the NCR of a given

number:

public class CombinationCalculator {

public static int calculateNCR(int n, int r) {
if (r == 0 || r == n) {
return 1;
} else {
return calculateNCR(n - 1, r - 1) + calculateNCR(n -
1, r);
}
}

public static void main(String[] args) {

int n = 5; // Change n and r as needed
int r = 2;
int ncr = calculateNCR(n, r);

[Link]("C(" + n + ", " + r + ") = " + ncr);

}
}

Output:

C(5, 2) = 10

Program to calculate the least common multiple of a

given number:

public class LCMCalculator {

// Function to calculate the greatest common divisor (GCD)
using Euclidean algorithm
public static int calculateGCD(int a, int b) {
if (b == 0) {

©Topperworld
Data Structure and Algorithms

return a;
}
return calculateGCD(b, a % b);
}

// Function to calculate the LCM of an array of numbers

public static int calculateLCM(int[] numbers) {
int lcm = numbers[0];
for (int i = 1; i < [Link]; i++) {
int gcd = calculateGCD(lcm, numbers[i]);
lcm = (lcm * numbers[i]) / gcd; // Calculate LCM
using GCD
}
return lcm;
}

public static void main(String[] args) {

int[] numbers = {4, 6, 8}; // Change the array to include
your numbers
int lcm = calculateLCM(numbers);

[Link]("LCM of the given numbers is: " +

lcm);
}
}

Output:

LCM of the given numbers is: 24

Program to calculate the greatest common divisor:

public class GCDCalculator {

// Function to calculate the greatest common divisor (GCD)
using Euclidean algorithm
public static int calculateGCD(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;

©Topperworld
Data Structure and Algorithms

}
return a;
}

public static void main(String[] args) {

int number1 = 48;
int number2 = 18;

int gcd = calculateGCD(number1, number2);

[Link]("GCD of " + number1 + " and " +

number2 + " is: " + gcd);
}
}

Output:

GCD of 48 and 18 is: 6

©Topperworld