Factorial, Fibonacci Sequence and GCD

Highlighting the explanation of Factorial, Fibonacci Sequence and GCD

→Below are Java programs demonstrating the calculation of Factorial, Fibonacci Sequence, and Greatest Common Divisor (GCD) using recursion, along with explanations for each:

Factorial Calculation using Recursion:

Factorial is a mathematical operation denoted by the symbol “!”, where for a non-negative integer n, the factorial of n is the product of all positive integers less than or equal to n.

Here’s a Java program demonstrating the calculation of Factorial using recursion:

public class FactorialExample {
    public static int factorial(int n) {
        if (n == 0 || n == 1) {
            return 1; // Base case: factorial of 0 or 1 is 1
        } else {
            return n * factorial(n - 1); // Recursive call to calculate factorial
        }
    }

    public static void main(String[] args) {
        int n = 5;
        int result = factorial(n);
        System.out.println("Factorial of " + n + " is: " + result);
    }
}

Explanation:

• The factorial method calculates the factorial of a given number n.
• Base case: If n is 0 or 1, the factorial is 1.
• Recursive case: Otherwise, it calculates n * factorial(n - 1) recursively until reaching the base case.

Fibonacci Sequence using Recursion:

The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones, usually starting with 0 and 1.

Here’s a Java program demonstrating the calculation of Fibonacci Sequence using recursion:

public class FibonacciExample {
    public static int fibonacci(int n) {
        if (n <= 1) {
            return n; // Base case: Fibonacci of 0 or 1 is the number itself
        } else {
            return fibonacci(n - 1) + fibonacci(n - 2); // Recursive call to calculate Fibonacci
        }
    }

    public static void main(String[] args) {
        int n = 6;
        System.out.println("Fibonacci sequence up to " + n + ":");
        for (int i = 0; i < n; i++) {
            System.out.print(fibonacci(i) + " ");
        }
    }
}

Explanation:

• The fibonacci method calculates the Fibonacci sequence up to the nth term.
• Base case: If n is 0 or 1, the Fibonacci number is the number itself.
• Recursive case: Otherwise, it calculates fibonacci(n - 1) + fibonacci(n - 2) recursively until reaching the base case.

Greatest Common Divisor (GCD) using Recursion:

The Greatest Common Divisor (GCD) of two integers is the largest positive integer that divides both of the given integers without leaving a remainder. In other words, it is the largest integer that divides both numbers evenly.

Here’s a Java program demonstrating the calculation of Greatest Common Divisor (GCD) using recursion:

public class GCDExample {
    public static int gcd(int a, int b) {
        if (b == 0) {
            return a; // Base case: GCD is the non-zero number
        } else {
            return gcd(b, a % b); // Recursive call to calculate GCD
        }
    }

    public static void main(String[] args) {
        int num1 = 48;
        int num2 = 18;
        int result = gcd(num1, num2);
        System.out.println("GCD of " + num1 + " and " + num2 + " is: " + result);
    }
}

Explanation:

• The gcd method calculates the Greatest Common Divisor (GCD) of two numbers a and b.
• Base case: If b is 0, then GCD is a.
• Recursive case: Otherwise, it calculates gcd(b, a % b) recursively until b becomes 0.