Question

Java Problem:

Provide a recursive definition of some sequence of numbers or function (e.g. log, exponent, polynomial). Write a recursive method that given n, computes the nth term of that sequence. Also provide an equivalent iterative implementation. How do the two implementations compare?

Answer 1

Let us suppose, we have an arithmetic sequence as given below:

2 5 8 11 14 17 20 23...

First term = 2

Second term = 5

Third term = 8 and so on.

Now we will calculate the 4th term using a recursive method and simple method as given below:

public class Main
{
//recursive method to find the nth term of a sequence
public static int nthTermRecursive(int s, int d, int n)
{
if(n == 0)
return 0;

return s + nthTerm(d, d, n-1);
}
  
//method to find the nth term of a sequence
public static int nthTerm(int s, int d, int n)
{
for(int i=0; i<n; i++)
{
s = s+d;
}
return s;
}
  
   public static void main(String[] args)
   {
   //variable declaration
   int s, d, n, nthTrm;
  
   //initialization of starting term
   s = 2;
  
   //initialization of difference
d = 3;
  
n = 4;
  
   //display the nth term with recursion
       System.out.println(n+"th Term(without recursion): " + nthTerm(s, d, n));
      
       //display the nth term using recursion
       System.out.println(n+"th Term (using recursion): " + nthTermRecursive(s, d, n));
   }
}

OUTPUT:

Recursion Method:

The recursion method calls to itself and the values are pushed on to the stack. This method will terminate when the base condition is matched and it is slower and takes more memory as compared to the iterative method.

The complexity of this method is exponential.

Iterative Method:

The iterative method a block of statements is executed many times and the complexity is generally polynomial-logarithmic.