Recursion

Apr 11, 2019

Recursion is a topic many beginner (and even some advanced) programmers struggle to grasp. In this tutorial, we break done recursion into smaller pieces and take a deeper look at each of them, hopefully allowing you to fully understand recursion and its potential. We will also look at one of my assignments in my CS course, which required us to solve a series of problems, using *only* one recursive method, and no instance variables.

Recursion is the idea of a function that calls itself. The idea is relatively simple, however it can be expanded to a variety of algorithms, such as Graph algorithms (e.g Depth-First Search) and Divide and Conquer algorithms (e.g Merge Sort).

For a problem to have a recursive solution, the following must be satisfied:

```
1. There must be a way to reduce the problem to smaller, simpler states.
2. There must be a base case, in which the recursion will terminate.
3. There must be a way to combine the smaller states into a larger result.
```

One simple example of a recursive problem is the factorial problem. Recall that the factorial of the number is the product of all the positive integers before it. For example \(5! = 5 \times 4 \times 3 \times 2 \times 1 = 120\).

The recursive implementation would look something like this:

```
public long factorial(int n)
{
if (n == 1)
return 1;
return n * factorial(n-1);
}
```

Note that this specific example is sometimes known as **tail recursion** - when the recursive call is always the last statement of the method. Not all recursive problems will look like this, some may even look as crazy as:

```
ArrayList<Integer>[] adj = new ArrayList[100];
public long crazyMethod(int u, int p)
{
long maxValue = 0;
for (Integer v : adj[u])
if (v != p)
maxValue = Math.max(maxValue, 1 + crazyMethod(v, u));
return maxValue;
}
```

If you don't understand the method above, **don't worry!** It will be explained in a future tutorial. For those curious, that is what is known as Depth-First Search. Also, please note that the above is *not tail recursion*, as the last statement of the method is not a recursive call.

Another type of recursion is called **mutual recursion** - when two methods call each other recursively. However, this type of recursion is rarely used as it is often hard to understand.

Listed below are the solutions to some of the problems from my CS course. Above each solution will be a simple definition of the problem being solved.

The first problem was to print a series of lines, reversed, and stopping at a period:

```
/**
* Evan Zhang
* Ms Krasteva
* April 11, 2019
* Problem 1
*/
import java.util.*;
public class Problem1
{
/**
* Reverses a string input, recursively
* @param input The original string to reverse.
* @return The reversed string.
*/
public static String run(String input)
{
return input.length() == 0 ? "" : run(input.substring(input.indexOf("\n") + 1)) + input.substring(0, input.indexOf("\n")) + "\n";
}
/**
* Main method
* @param args Command line arguments
*/
public static void main(String[] args)
{
Scanner in = new Scanner(System.in);
String input = "";
while (true)
{
String line = in.nextLine();
input += line + "\n";
if (line.equals("."))
break;
}
System.out.println(run(input));
}
}
```

The second problem was to reverse the digits of an integer, and print it out:

```
/**
* Evan Zhang
* Ms Krasteva
* April 11, 2019
* Problem 2
*/
public class Problem2
{
/**
* Reverse the digits in an integer
* @param n the input number
*/
public static void revDigits(int n)
{
if (n == 0) return;
System.out.print(n % 10);
revDigits(n / 10);
}
/**
* Main method
* @param args Command line arguments
*/
public static void main(String[] args)
{
System.out.print("345 reversed is ");
revDigits(345);
System.out.println();
System.out.print("4 reversed is ");
revDigits(4);
System.out.println();
}
}
```

The third problem was to check if an `Object`

existed in an array of `Comparable`

s by using only the `compareTo`

method:

```
import java.util.*;
/**
* Evan Zhang
* Ms Krasteva
* April 11, 2019
* Problem 3
*/
public class Problem3
{
/**
* Search for a comparable object in a comparable array, recursively
* @param arr The array to search in.
* @param obj The object to search for.
* @return Whether the element exists.
*/
public static boolean searchItem(Comparable[] arr, Comparable obj)
{
return arr.length != 0 && (arr[0].compareTo(obj) == 0 || searchItem(Arrays.copyOfRange(arr, 1, arr.length), obj));
}
/**
* Main method
* @param args Command line arguments
*/
public static void main(String[] args)
{
System.out.print("Finding '2' in array [1,2,3,4,5]: ");
System.out.println(searchItem(new Integer[]{1,2,3,4}, 2) ? "element exists." : "element does not exist.");
System.out.print("Finding '6' in array [1,2,3,4,5]: ");
System.out.println(searchItem(new Integer[]{1,2,3,4}, 6) ? "element exists." : "element does not exist.");
}
}
```

The last (and hardest) problem was to implement an algorithm known as Depth First Search on a grid. We had to check if there was a path between two points on a \(2\)-d grid.

```
/**
* Evan Zhang
* Ms Krasteva
* April 11, 2019
* Problem 4
*/
public class Problem4
{
/**
* Depth first search
* @param grid The input grid.
* @param i The current row.
* @param j The curent column.
* @return Whether there is a path from the entrance to the exit.
*/
private static boolean dfs(int[][] grid, int i, int j)
{
if (i < 0 || i > 4 || j < 0 || j > 4 || grid[i][j] == 1)
return false;
if (i == 4)
return true;
grid[i][j] = 1;
for (int x = -1; x <= 1; x ++)
for (int y = -1; y <= 1; y ++)
if ((x == 0 || y == 0) && dfs(grid, i+x, j+y))
return true;
grid[i][j] = 0;
return false;
}
/**
* Finds a path from the entrance to the exit.
* @param grid The input grid.
* @return Whether there is a path from the entrance to the exit.
*/
public static boolean run(int[][] grid)
{
for (int x = 0; x < 5; x++)
if (grid[0][x] == 0 && dfs(grid, 0, x))
return true;
return false;
}
/**
* Main method
* @param args Command line arguments
*/
public static void main(String[] args)
{
int[][] arr = {
{0, 0, 0, 0, 1},
{0, 1, 1, 0, 0},
{0, 0, 1, 1, 0},
{1, 0, 0, 1, 0},
{1, 1, 0, 1, 1},
};
System.out.println(run(arr));
}
}
```