Write a small program, in pseudocode or otherwise, that demonstrates a recursive algorithm. Write a small explanation of how recursion is used in your program.

The Fibonacci sequence is defined as:f(n) = f(n-1) + f(n-2)F(0) = 1F(1) = 1Where n is a positive number. This allows for a recursive algorithm to be written that returns 1 for the two base cases, and returns the sum of calling the function on n - 1 and n - 2 for any other case.public class RecursionDemonstration { public static int recursiveFibonacci(int n) { // Sanity check that n > 0 if (n < 0) { // return -1 to signal an error. return -1; } // check for the base case. if (n == 0 || n == 1) { return 1; } else { return (recursiveFibonacci(n-1) + recursiveFibonacci(n-2); } } public static void main(String[] args) { System.out.println("The 0th fibonacci number is " + Integer.toString(recursiveFibonacci(0)); System.out.println("The 1st fibonacci number is " + Integer.toString(recursiveFibonacci(1)); System.out.println("The 2nd fibonacci number is " + Integer.toString(recursiveFibonacci(2)); System.out.println("The 7th fibonacci number is " + Integer.toString(recursiveFibonacci(7)) } }