Recursion is the technique of making a function call to itself. This technique provides a way to break complicated problems down into simple problems which are easier to solve.

Recursion Structure

1. validation of input
2. base case where it stops calling itself and returns a value
3. recursive case, logical operation + call itself with reduced value(s)

When a invocation of the function makes a recursive call, that invocation is suspended until the recursive call completes, new storage locations for variables are allocated on the stack. As, each recursive call returns, the old variables and parameters are removed from the stack. Hence, recursion generally uses more memory and is generally slow. On the other hand, a recursive solution is much simpler and takes less time to write, debug and maintain. The execution starts from the top and goes to bottom, for example 6,5,4,3,1, then when it hits the base case, the calculation will start from bottom(base case) back to to.

Here are some examples of recursion:

Things like tree or graph data can be good candidates for recursion.

Every recursion or recursive function can be done with for loop or while loop.

Just as loops can run into the problem of infinite looping, recursive functions can run into the problem of infinite recursion. Infinite recursion is when the function never stops calling itself. Every recursive function should have a halting condition, which is the condition where the function stops calling itself. In the below examples, the halting condition is when the parameter num becomes 0 or 1.

Recursion may be a bit difficult to understand. The best way to figure out how it works is to experiment with it.

Sum with Recursion

private static int sum(int num) {

    /**
     * base case
     */
    if (num <= 0) {
        return 0;
    }

    /**
     * recursive case
     */
    return num + sum(num - 1);
}

private static int sumWithLoop(int num) {
    int total = 0;
    for (int i = 0; i <= num; i++) {
        total += i;
    }
    return total;
}

10 + sum(9)
10 + ( 9 + sum(8) )
10 + ( 9 + ( 8 + sum(7) ) )
…
10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + sum(0)
10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + 0

Factorial with Recursion

/**
 * Recursion used for factorial<br>
 * Start from the top and go to bottom, then calculation will start from bottom back to top
 */
private static int factorial(int num) {
    /**
     * validation
     */
    if (num < 0) {
        throw new IllegalArgumentException("num is invalid");
    }

    /**
     * base case
     */
    if (num == 0) {
        return 1;
    }

    /**
     * recursive case
     */

    return num * factorial(num - 1);
}

private static int factorialWithLoop(int num) {

    int fact = 0;

    for (int i = 1; i <= num; i++) {
        fact = fact * i;
    }

    return fact;
}

Fibonacci with Recursion

/**
 * Recursion used for fibonacci<br>
 * Start from the top and go to bottom, then calculation will start from bottom back to top
 */
private static int fibonacci(int num) {
    if (num <= 1) {
        return num;
    }
    int number1 = fibonacci(num - 1);
    int number2 = fibonacci(num - 2);
    return number1 + number2;
}

private static int fibonacciWithLoop(int num) {
    int indexNumber = 0;
    int number1 = 0;
    int number2 = 1;
    int sum = 0;

    for (int i = 0; i < num; i++) {

        sum = number1 + number2;

        number1 = number2;
        number2 = sum;

        indexNumber = sum;

    }

    return indexNumber;
}

Fibonacci with Momeization

private static int fibonacci(int num, Map<Integer, Integer> map) {
    if (num <= 1) {
        return num;
    }

    if (map.containsKey(num)) {
        return map.get(num);
    }

    int number1 = fibonacci(num - 1, map);
    int number2 = fibonacci(num - 2, map);

    int sum = number1 + number2;
    map.put(num, sum);
    return sum;
}

Map<Integer, Integer> map = new HashMap<>();
 int   total = fibonacci(9, map);

Source code on Github