Recursion

Recursion is a programming technique in which a function calls itself. This allows for large, complicated problems to be simplified into smaller, more solvable problems. There are 3 main laws of recursion:
  1. A recursive algorithm must call itself.
  2. A recursive algorithm must have a base case (a condition that allows the algorithm to stop recursing).
  3. A recursive algorithm must change its state and move toward the base case.
Shown below is an example program which accepts an integer n and runs the factorial function (multiplies all whole numbers from n down to 1). 

public class FactorialDemo {
    public static void main(String[] args) {
        System.out.println(factorial(5)); // prints 120 (5*4*3*2*1 = 120)
    }
    public static int factorial(int n) {
        if (n > 1) return n * factorial(n - 1);
        else return 1; // Base case
    }
}

This program works by multiplying n by factorial(n-1) while n > 1 and returning 1 if otherwise. When broken down, factorial(5) essentially follows these steps. 

5 * factorial(4)
5 * 4 * factorial(3)
5 * 4 * 3 * factorial(2)
5 * 4 * 3 * 2 * factorial(1)
5 * 4 * 3 * 2 * 1 // n = 1 is the base case, returns 1 and stops the recursion

Advantages and Disadvantages of Recursion


Advantages

As stated before, recursion is useful for simplifying large tasks into smaller, more managable subtasks. It is also useful when the output from a function is needed to be stored or manipulated before being inserted into the same function again (e.g. a recursive function which calculates the fibonacci sequence would need to take the 2 previous fibonacci numbers and add them together to get the third, then repeat this over and over again). These abilities also makes recursion very useful for tasks such as sorting arrays and graph traversal.


Disadvantages

Though recursive functions are simpler and more compact that non-recursive functions, recursive functions are also generally slower than non-recursive functions, and also may require more memory. This is because in a recursive function, all function calls must be stored in a stack to allow the recursive functions to return back to the caller functions. This action of storing the function calls in a stack both decreases performance, and also can use much more memory depending on how many levels of recursion are used.