Question

Recursion is a technique for breaking down a complex problem into smaller pieces and then combining the results to obtain the desired answer. The most common example of recursion is calculating factorials. Describe another problem that can be solved using recursion and outline the approach using Java or Pseudo-Code. Discuss the Big-Oh run time performance of your example. (Make sure to use your own words – do not cut and paste someone else's solution.)

Answer 1

Following is the code for Tower of Hanoi problem being solved by recursion:

class Main {
  
static void tower(int n, char first,
               char second, char third)
{
   if (0 == n)
   return;

   tower(n - 1, first, third,
                       second);

   System.out.printf("Move the disk %d from %c to %c\n",
                       n, first, second);

   tower(n - 1, third, second, first);
}

public static void main(String[] args)
{
   tower(3, 'F', 'S', 'T');
}
}

If we write this program logic in a relation form, it will written as :

T(n)= 2*T(n-1)+1

When we apply Back Substitution method on this relation we get T(n)=((2^(n+1))-1) and hence the complexity is exponential O(2^n).

Please find the attached screenshot of the output of the program: