Recursive Methods

Recursive methods are useful when you want to break down a complex problem into several smaller problems. You can apply them whenever a iterative method is also possible.

Designing a recursive method

Designing a recursive method comprises 3 steps 1. Divide problem into problems of the same kind. 2. Find a solution for the most basic, simple problem. 3. Find a solution for the general problem (i.e. recursive call to the same method).

The idea is that general problem arrives at the basic solution. So, one has to find the recursive pattern in a problem. Taking faculty as example, to solve the problem of faculty(n), one could try to solve the problem faculty (n-1) first until one arrives at the basic problem faculty(1).

1! = 1 (basic solution) 2! = 1 * 2 = 1! * 2 3! = 1 * 2 * 3 = 2! * 3 4! = 1 * 2 * 3 * 4 = 3! * 4 n! = 1 * 2 … * (n -1) * n

Example

public static long fac(int n){
  //basic problem: i = 1
  if (n == 1){
    return 1;
  }
  // general problem
  return fac(n-1) * n;
}

Another example

public static boolean rowContainsElement(int[] row, int element){
    int index = 0;
    return recursiveRowContainsElement(row, index, element);

}

    public static boolean recursiveRowContainsElement(int[] row, int index, int element){

    if (row[index] == element){
      return true;
    } else {
      if (row[index] < row[row.length-1])
        return recursiveRowContainsElement(row,index +1, element);
      else {
        return false;
      }
    }
  }

## Reading a recursive method

  1. Check if provided basic solution solves basic problem
  2. Check if general solution solves general problem
  3. Check if general solution covers the whole scope of the problem

Types of recursion

Head recursion: recursive method call first, then non recursive rest Tail recursion: non-recursive rest first, then recursive part

Extra requirements

Extra requirements can be added to the recursive function as e.g. empty return value.

public recursiveFunction(int[] row, int index){


if (requirementFullfilled == false){

  return;
}

}