What is Recusion

Recursion is a powerful way of developing algorithms in which the solution of a problem is determined by the solution of one or more identical subproblems. A recursive solution involves two parts:

1. at least one BASE CASE in which the solution returned is not dependent on any solution of any subproblem,
2. and at least one RECURSIVE CASE, where the solution will be determined by the solution of subproblems.

It is very important that the recursive cases eventually make it to the base case. If you do not have a base case, or if your recursive cases never make it to the base case, then you can cause an infinite loop.

A common example of using recursion is to find the answer to n! where n is an integer and n! is defined as: n! = n * (n – 1) * (n – 2) * … * 2 * 1 * 0
It is important to note that 0! is defined as 1. Another way of saying this is that n! is really n * (n – 1)!, and (n – 1)! is really (n – 1) * (n – 2)! The most challenging part of using recursive functions is to determine WHAT is actually being recursively solved. It is often where a loop would naturally occur in an iterative solution. n! is a simple and obvious example, but a helpful way to visualize where the recursion should happen is to draw out the problem step-by-step until you see a pattern: n! n * (n – 1)! n * (n – 1) * (n – 2)! …..

Once you determine where the recursion will occur, you can start coming up with ways to solve this. You need to decide what the base case is. From our definition of a factorial, we see that 0! equals 1, so that would be a good base-case for this problem. After you have your base case, you need to determine what your recursive case is going to be.

For this example, we can see from our pattern above that we want the solution of n * (n – 1)!. We can achieve this by returning n * factorial(n – 1). We will ultimately enter our base case once n = 0, so we know we are safe and are ready to implement our code!

Examples:

Input : 5
Output : 120

Input : 7
Output : 5040

public class Factorial {
  public static void main(String[] args) {
    System.out.println("Factorial for 5:");
    System.out.println(recursiveFactorial(5)); // Should print 120

    System.out.println("Factorial for 7:");
    System.out.println(recursiveFactorial(7)); // Should print 5040

    System.out.println("Factorial for 5:");
    System.out.println(iterativeFactorial(5)); // Should print 120

    System.out.println("Factorial for 7:");
    System.out.println(iterativeFactorial(7)); // Should print 5040
  }

  // Recursive solution to n!
  public static int recursiveFactorial(int n)
  {
    // BASE CASE
    if (n == 0) 
      return 1;

    // RECURSIVE CASE
    return n * recursiveFactorial(n - 1);
  } 

  // To contrast, this is the iterative solution to the factorial problem.  
  public static int iterativeFactorial(int n)
  {
    int factorialN = 1;
    
    // Recursive solutions can typically be rewritten as for-loops:
    for (int i = 1; i <= n; i++) {
      factorialN *= i;
    }

    return factorialN; 
  }
}

Deciding when to use recursion over iteration is another part of the puzzle. Recursion takes up more space on the stack, and can cause problems if you spiral too deeply and run out of memory, but also provides an elegant and often easier to understand block of code than iterative solutions. Comparing the recursive and iterative solutions above, it is much easier to understand exactly what is happening in the recursive solution (n! is just n * (n – 1)! which is just (n – 1) * (n – 2)! which is just…) whereas the iterative solution isn’t so obvious (though after a few seconds the programmer will understand what is happening….this is again a simple solution).

Take another example– a pre-order traversal of a binary search tree. A pre-order traversal involves processing a node, then processing the left subtree, then the right subtree. In a tree such as: 1 / \ 2 3 / \ / \ 4 5 6 7 The order of traversal would be: 1 – 2 – 4 – 5 – 3 – 6 – 7 Iteratively, this would require nested while and for loops, and would look a little something like:

void iterativePreorderTraversal(Node node) {
  if (node == null) {
    return;
  }

  Stack<Node> nodeStack = new Stack<Node>();
  nodeStack.push(root);
  while (!nodeStack.empty()) {
    Node thisNode = nodeStack.peek();
    // Process thisNode in some way
    nodeStack.pop();
    // Push the right node onto the stack first so that the left node
    // is processed first
    if (thisNode.right != null) {
      nodeStack.push(thisNode.right);
    }
    if (thisNode.left != null) {
      nodeStack.push(thisNode.left);
    }
  }
}

This works but looks a little convoluted. It would be much easier to read/understand something written like this:

void recursivePreorderTraversal(Node node) {
  if (node != null) {
    //process node in some way 
    traversePreRecursive(node.getLeft());
    traversePreRecursive(node.getRight());
}

The recursive solution is much easier to read, understand, and debug from the perspective of the developer, and would be a sensible choice for this type of problem.