Recursion

An introduction to Recursion with Java.

Recursion is where some code (often a method) calls itself. This process allows for repetitive operations to be performed rapidly and for the simplification of code as a minimal number of lines of code would be required to run the same code/conditions again. Recursive methods have a comparable functionality to a loop but are often easier to understand and are much more capable. A recursive method must eventually come to an end, otherwise a stack overflow will occur. Generally speaking most recursive methods take a parameter. This allows the same code to be run with a different parameter passed to it and its result will often be used to determine whether or not to make a recursive call again.

int index=0;
private String[] toppings = {"Cheese", "Pepperoni", "Black Olives"};
public String loop (int index, String[] toppings){
    if (toppings[index]!=null){
        return loop(index+1,toppings);
    }else{
        return "your array has a length of: "+index;
    }
}

In the example above 2 variables are created an integer and an array of strings. The method takes both as parameters then determines if an item in the array with that index exists. If it does it will call the method again after incrementing index by one. If it does not then it will return a string stating that index is the length of the array.

Three common types of recursion exist: Linear, Binary and Tail.

• Linear: A linear recursion refers to a recursive method that only calls itself a single time.
• Binary: A binary recursion refers to a recursion that calls itself more than once within a method, it is called a binary recursion because it will often rely on a boolean condition to determine what parameters it should call itself with.
• Tail: A Tail recursion refers to a method that has its recursive call statement located at the end of the method just before the curly braces.

Recursion is very similar to a loop in the sense that the same block of code can be run more than once, but where recursion really stands out from a loop is that in binary recursion a method may call itself twice. This is functionality that is very difficult to replicate within a loop. Recursive methods are also often dependent on return statements to pass parameters back to the original method call. Where recursion really suffers in comparison to a loop is in terms of memory usage as recursive calls in java require the bytecode to be duplicated in memory.

Examples

Linear search or selection search is demonstrated below as a linear recursive method that will search through a set of data and return a boolean value based on if that value was found within the array.

int index=0;
private String[] toppings = {"Cheese", "Pepperoni", "Black Olives"};
public boolean loop (int index, String[] toppings, String search){
    if(index < toppings.length){
        if (toppings[index]==search){
            return true;
        }else{
            return loop(index+1, toppings, search);
        }
    }else{
        return false;
    }
}
search(0, toppings, "Pepperoni");

Our next example will be a method to calculate the fibonacci sequence which is one of the most popular pieces of code to write in a lesson about recursion. It utilizes tail recursion as it calls itself at the end of its method.

public int fibonacci (int n){
    if(n == 0)
        return 0;
    else if(n == 1)
        return 1;
    else
        return fibonacci(n - 1) + fibonacci(n - 2);
}

THANKS FOR READING

Credits: https://stackoverflow.com/questions/26874794/java-fibonacci-recursion-code