## Recursively Finding Greatest Common Divisor (GCD) – Java Implementation

This articles shows a java program that finds a greatest common divisor between two input integers and also prints the intermediate steps of recursion. Can you think about the complexity of this algorithm? It is O(Log(N)) where N is the largest number of the two. See the analysis here.

```package com.icodejava.research.ready;
/**
*
* @author Kushal Paudyal
* Created on: 2/8/2017
*
* Recursive way of finding the GCD (Greatest Common Divisor)
*/
public class GCDRecursive {

public static int gcd(int a, int b) {
System.out.println("First Number: " + a + " Second Number: " + b);
if (a < 0 || b < 0) {
throw new IllegalArgumentException("No GCD of negative integers");
}
return b == 0 ? a : gcd(b, a % b);
}

public static void main(String args []) {
System.out.println("Greatest Common Divisor of 35 and 21 is " + gcd(35,21));
}

}
```

The following is the output of this program.

```First Number: 35 Second Number: 21
First Number: 21 Second Number: 14
First Number: 14 Second Number: 7
First Number: 7 Second Number: 0
Greatest Common Divisor of 35 and 21 is 7
```

## Implementing a Simple LIFO Stack in Java using LinkedList

Last In First Out (LIFO) stacks can be easily implemented in Java using a singly linked list. This example shows a very simple implementation of the stack operations using singly linked list.

```package com.icodejava.blog.published.datastructure;
/**
*
* @author Kushal Paudyal
* Created on: 2/8/2017
*
* This class shows a simple implementation of Stack using LinkedList
*/

public void push(Object item) {
System.out.println("Stacked: " + item);
}

public Object pop() {
System.out.println("Destacked: " + list.getFirst());
return list.removeFirst();
}

public Object peek() {
return list.getFirst();
}

public int size() {
return list.size();
}

public boolean isEmpty() {
return list.isEmpty();
}

/**
* Testing the stack. The added objects should be returned in reverse order
*/
public static void main (String args[]) {
System.out.println("===STATCK-PUSH===");
stack.push("One");
stack.push("Two");
stack.push("Three");

System.out.println("\n===STACK-POP===");
while (!stack.isEmpty()) {
stack.pop();
}
}
}
```

Here is the output of this program:

```===STATCK-PUSH===
Stacked: One
Stacked: Two
Stacked: Three

===STACK-POP===
Destacked: Three
Destacked: Two
Destacked: One
```

## Implementing a Simple FIFO Queue in Java Using Linked List

First In First Out (FIFO) queues can be easily implemented in Java using a singly linked list. This example shows a very simple implementation of the queue operations using singly linked list.

```package com.icodejava.published.datastructure;
/**
*
* @author Kushal Paudyal
* Created on: 2/8/2017
*
* This class shows a simple implementation of Queue using LinkedList
*/

public void enqueue(Object item) {
}

public Object dequeue() {
System.out.println("Removed: " + data.getFirst());
return data.removeFirst();

}

public Object peek() {
return data.getFirst();
}

public int size() {
return data.size();
}

public boolean isEmpty() {
return data.isEmpty();
}

/**
* Testing the stack. The added objects should be returned in same order
*/
public static void main (String args[]) {
System.out.println("===ENQUEUE===");
queue.enqueue("One");
queue.enqueue("Two");
queue.enqueue("Three");

System.out.println("\n===DEQUEUE===");
while (!queue.isEmpty()) {
queue.dequeue();
}
}
}
```

Here is the output of running the above program:

```===ENQUEUE===