Recursion

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:

  • The factorial function (commonly denoted as n!) is a classic mathematical function that has a natural recursive definition.
  • An English ruler has a recursive pattern that is a simple example of a fractal structure.
  • Binary search is among the most important computer algorithms. It allows us to efficiently locate a desired value in a data set with upwards of billions of entries.
  • The file system for a computer has a recursive structure in which directories can be nested arbitrarily deeply within other directories. Recursive algo- rithms are widely used to explore and manage these file systems.

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




Subscribe To Our Newsletter
You will receive our latest post and tutorial.
Thank you for subscribing!

required
required


Leave a Reply

Your email address will not be published. Required fields are marked *