June 2020 | JavaByPatel: Data structures and algorithms interview questions in Java

How Recursion works in Java with example

How Recursion works internally in Java

In this post, we will see, how recursion works internally in java with example along with recursive function practice programs in Java.
We will also see, how Stackoverflow error is caused in Recursive functions.

What is Recursion?

Recursion is a process in which a function gets called repeatedly, either directly called by the same method or via other method call and such a method is called Recursive function.

To keep it simple, I would say, when a function calls itself is called recursion or a recursive call. Let's understand recursive function with a small example,

What is Base condition in recursion?

We have seen in recursion a function calls itself, now if the function keep calling itself recursively then how the control is going to come out, that is where a Base condition helps. Base condition is a necessary check to break the recursive call at some point.

Which data structure is used internally in recursion?

Stack data structure is used in recursion for storing the state of each function call.

Explain the use of stack in recursion?

let us first understand why we need data structure in recursion. check below program to find factorial using recursion in java

 
private static int findFactorialRecursive(int num){
   if(num < 0) {
     return -1;
   }
   if(num == 1 || num == 0) {
     return 1;
   }
   num = num * factRecursive(num-1); //Recursive call
   return num; 
}

When above function is invoked for the first time, method would be executed till line number 8, and post that it would jump back to line number 1 for a fresh method call with a new value of “num”.

If a function will execute again(second time) with new value of num, what about the value of previous num as it still has to execute line number 9 of the first call and has to preserve the value of num( basically it has to preserve state of first method call, then second call, then third call and so on).
So when a function calls itself, Stack is used to store the state of previous call.

Lets understand how recursion works internally with recursive call stack diagram.

Recursive call stack diagram

Recursion practice programs with solution

List of recursive practice programs, some of the recursive programs are tricky, read the complete solution to understand it better.

When Stackoverflow error is caused by recursive function?

In recursion, a method calls itself and a Stack data structure is used internally to store the state of each function call.

So as long as the function keep calling itself, Stack memory needs to be allocated for each function call.

Consider a situation where a program never hits the base condition then function will keep calling itself and Stack memory consumption will keep on increasing and at one point when there would be no Stack memory left to allocate for the next function call at that time Stackoverflow error would be thrown.

Builder Design Pattern.

Builder Design pattern is used to simplify the creation of complex Immutable object.

In simple words, we should use builder design pattern when a class have multiple properties, some of which are optional and some mandatory for an object creation that is constructor or static factories of such a class would require more than 4 to 5 parameters.

When to use Builder Design Pattern

Purpose of the Builder Design Pattern

Consider a class with multiple fields, Example: Pizza, Burger, Assembled Car, Computer etc, object creation of such class(Pizza) is complex due to multiple constructors required with some mandatory fields(like pizza size, bread type) and some optional(like pizza toppings cheese, olive, pepper etc).

Problem without Builder Pattern,

Approach 1: Telescoping Constructor

For creating a object of such complex classes, it would require multiple constructors(Telescoping Constructor) each taking mandatory parameters with a new optional parameter as shown below,

public Pizza (int size, boolean cheese){ ... }
public Pizza (int size, boolean cheese, boolean olive){ ... } 
public Pizza (int size, boolean cheese, boolean olive, boolean pepper){ ... } 
public Pizza (int size, boolean cheese, boolean olive, boolean pepper, boolean onion){ ... }

Telescoping Constructor: A class with many constructors, where each constructor calls a more specific constructor in the hierarchy, which has more parameters than itself, providing default values for the extra parameters. The next constructor does the same until there is no left.

Problem: We can use Telescoping constructors in this situation but a problem with this pattern is that once constructors start taking more than 4 to 5 parameters, It becomes difficult to maintain and remember the required order of the parameters, also it brings more complexity for the caller of the constructor as which one to call in a given situation.

Approach 2: Setter method

One way of creating the object is to use setter method approach to set the properties of object step by step.

Pizza pizza = new Pizza(6);
pizza.setCheese(true);
pizza.setOlive(true);
pizza.setPepper(true);

Problem: we cannot use setter method approach here because with setter method, object could be modify after it is created using setter call and would no longer remain immutable.

Builder Pattern in Rescue

To avoid above problems in a situation where we have complex constructor, large number of parameters and need object Immutability, we use builder design pattern which separates the construction of a complex object from its representation.

Pizza.java

package javabypatel;

public class Pizza {
    private int size;
    private BreadType breadType;

    private boolean cheese;
    private boolean olive;
    private boolean pepper;

    public Pizza (PizzaBuilder pizzaBuilder) {
        this.size = pizzaBuilder.size;
        this.breadType = pizzaBuilder.breadType;

        this.cheese = pizzaBuilder.cheese;
        this.olive = pizzaBuilder.olive;
        this.pepper = pizzaBuilder.pepper;
    }

    public static class PizzaBuilder {
        //Mandatory Parameters
        private int size;
        private BreadType breadType;

        //Optional Parameters
        private boolean cheese;
        private boolean olive;
        private boolean pepper;

        public PizzaBuilder(int size, BreadType breadType) {
            this.size = size;
            this.breadType = breadType;
        }

        public PizzaBuilder withCheese(boolean cheese) {
            this.cheese = cheese;
            return this;
        }
        public PizzaBuilder withOlive(boolean olive) {
            this.olive = olive;
            return this;
        }
        public PizzaBuilder withPepper(boolean pepper) {
            this.pepper = pepper;
            return this;
        }

        public Pizza build() {
            return new Pizza(this);
        }
    }
}

enum BreadType {
    THIN_CRUST,
    THICK_CRUST,
    FLAT_BREAD;
}

class Main {
    public static void main(String[] args) {
        Pizza pizza = new Pizza.PizzaBuilder(6, BreadType.THICK_CRUST)
                .withCheese(true)
                .withOlive(true)
                .build();
        System.out.println(pizza);
    }
}

Advantages of Builder Design Pattern

1. Complex object construction become more readable and easy.
2. No need to pass optional parameters in creating the object.

Disadvantages of Builder Design Pattern

1. Builder pattern requires creating a separate Builder class for each different Type.
2. It creates more code.

Builder Design Pattern used in JDK API.

java.lang.StringBuilder class is a Builder for String class.

String str = new StringBuilder("Hello").appeend("world").toString();

JavaByPatel

How Recursion works in Java with example

How Recursion works internally in Java

You may also like to see

Command Design Pattern

Observer Design Pattern

Adapter Design Pattern

Decorator Design Pattern

When to use Builder design pattern.