Question

Recursion practice

Write a Java program with functions for each of the following problems. Each problem should be solved by writing a recursive function. Your final program should not have any loops in it.

All of your solutions should be in a single .java file. The main function of the file should demonstrate each of your solutions, by running several tests and producing the corresponding outputs.

Write a recursive method to

1. calculate power of a give number

2. multiply m by n using only repeated addition

3. Implement recursive Fibonacci: Return the nth number in the Fibonacci sequence (5 points) a. Demonstrate by printing the first 10 numbers
4. Implement Euclid’s algorithm recursively.

a. Euclid’s algorithm to calculate the greatest common divisor of two positive integer         

numbers a and b (gcd(a,b)) is recursively defined as:

gcd(a,b) := a if a = b

gcd(a,b) := gcd(a - b, b) if a > b

gcd(a,b) := gcd(a, b - a) if b > a

5. Return the length of a linked list
   1. You will need to implement a simple link list
   2. Include a length function that uses recursion to count the number of elements

Answer 1

import java.util.*;
public class Main
{
public static int calculatePower(int x,int y) //to calculate power(x,y)
{
if(y==0)
return 1;
else
return x*calculatePower(x,y-1);
}
public static int multiply(int m,int n)
{
       if(n>0)
           return m+multiply(m,n-1);//recursivly calling multiply()
       else
           return 0; //n<=0
}
public static int gcd(int a,int b) //to calculate gcd
{
if(a==b)
return a;
else if(a>b)
return gcd(a-b,b);
else
return gcd(a,b-a);
}
public static int fib(int n) //to get fibnocci series
{
if(n>1)
return fib(n-1)+fib(n-2);
else
return n; //n<=1
}
   public static void main(String[] args) {
       Scanner sc=new Scanner(System.in);
       int n=sc.nextInt();
       int b=sc.nextInt();
       System.out.println(n+" power of "+b);
       System.out.println(calculatePower(n,b)); //calculatint Power
       System.out.println("multiplication of "+n+"x"+b);
       System.out.println(multiply(n,b)); //multiplication
       System.out.println("Greatest common divisor of "+n+" and "+b);
       System.out.println(gcd(n,b)); //to get gcd value
       System.out.println(n+"th Number in the fibnocci sequence is "+fib(n)); //get nth fibnocci number
       System.out.println("first 10 numbers in the fibnocci series are: ");
       System.out.println(fib(1)+"\n"+fib(2)+"\n"+fib(3)+"\n"+fib(4)+"\n"+fib(5)+"\n"+fib(6)+" \n"+fib(7)+" \n"+fib(8)+" \n"+fib(9)+"\n"+fib(10)); //printing first 10 numbers in fibnocci series without using loop (or) we can write another function for this.
       System.out.println("Single Linked List:");
       LinkedList L = new LinkedList();
L =L.insert(L, 10); //inserting elements to the list
L =L.insert(L, 20);
L =L.insert(L, 30);
L =L.insert(L, 40);
L =L.insert(L, 50);
L.printList(L); //print the list
       System.out.println();
System.out.println("Length of linked list is:");
System.out.println(L.count(L.head)); //length of list
      
   }
}
class LinkedList {
  
Node head; //starting node of list
static class Node { //static class to easy access
int data;
Node next;
Node(int d) // Constructor
{
data = d; // data to be stored in the node
next = null; //to create link betwwen nodes
}
}
public static LinkedList insert(LinkedList l, int data) // insert a new node
{
Node new_node = new Node(data);
new_node.next = null;
if (l.head == null) {
l.head = new_node;
}
else {
Node last = l.head;
while (last.next != null) {
last = last.next;
}
last.next = new_node;
}
return l;
}
public static int count(Node temp) //to count the number of elements in the list
{
if(temp==null)
return 0;
else
return 1+count(temp.next);
}
public static void printList(LinkedList list) //to print the list elements
{
Node n = list.head;
System.out.print("LinkedList: ");
while (n != null) {
System.out.print(n.data + " ");
n = n.next;
}
}
}

output: