In this section, we will learn what the recursion is and how it works in Java.

Note: Before reading this section, we’re assuming you are familiar with methods and stack & heap.

What Is a Recursive Function?

We know that inside the body of a method, we can call other methods. But one thing that you might didn’t notice is that we can call the method within its body as well! This is called recursion.

Recursion at its core is a simple process. All we do is calling a method within its body. But if we don’t pay attention, it can easily crash the program.

Example: creating recursive function in Java

public class Simple {
    public static void main(String[] args) {
        int res = multiply(4);
        System.out.println(res);
    }
    public static int multiply(int value){
        if (value !=0){
            return multiply(value -1) * value;
        }else{
            return 1;
        }
    }
}

Output:

24

How recursion works in Java?

Let’s break this example and see how we got the value 24:

Within the body of the `main` method, we called the `multiply()` method with the value 4.

multiply(4):

The first time we called this method, the assigned value was 4.

Within its body, we have an `if-statement` which is in charge of checking to see if the argument of the method is not zero.

For this call, the result of this condition is true (the argument is 4) and so the body of the `if-statement` will run.

Within this statement, we have the `return` keyword with the expression of ` multiply(value -1) * value`.

In order to resolve the expression, we need to call the `multiply` method with the value `value-1` so it is basically `multiply(3)` method.

As mentioned before in stack&heap section, when a method is called within the body of another method, the CPU will stop running the first method and will jump into running the body of the second one.

So here the first method call will stop running until the result of the `multiply(3)` method is declared and retuned.

multiply(3):

The first line of this method was to check if the input is not 0, and as you can see the value is 3 so the condition is true and its body will run.

Within the body of the statement, we have the expression of ` multiply(value -1) * value` which is equal to: `multiply(2) * 3`. So solving the expression, the CPU will stop running the current method and will jump into running the `multiply(2)` method and get the result of the method call.

Note: again, a block of memory will be set aside first and then the body of the `multiply(2)` will be executed.

multiply(2):

Again, the first line in the method is to check the value of the argument and because this argument is not 0, the body of the `if` statement runs.

The expression in the statement will be: ` multiply(value -1) * value`, which is equal to: ` multiply(1) * 2`. And again, in order to resolve the expression, a call to the `multiply(1)` should happen.

multiply(1):

In this call, because the value of the argument is still non-zero, the body of the `if-statement` will run and so we will have this expression within the statement: ` multiply(0) * 1`.

Again, to solve the expression, another call to the `multiply()` method with the value 0 should happen.

multiply(0):

This time because the value of the method (argument) is 0, the condition of the `if-statement` won’t run and so the body of the `else` statement is the one to run instead.

Within the body of this statement, we have the `return 1` which will cause the `multiply(0)` to terminate with the value 1 as its final result.

So now one method `multiply(0)` resolved, and it is off the stack.

Note: so far we start with `main()`, then went to `multiply(4)`, `multiply(3)`, `multiply(2)`, `multiply(1)`, and here `multiply(0)`. Basically, we have a stack of 6 methods with the `multiply(0)` is off the stack now, the remaining methods will be 5.

Essentially, every time a method is resolved, it will be off the stack.

Back to the multiply(1):

The method was at `return multiply(0) * 1` statement when the call to the `multiply(0)` happened. Now because the result of the call is declared, the method will be replaced with its value and the final expression will be: `1*1`.

So the value that `multiply(1)` will return is 1.

Back to the multiply(2):

We know that the call to the `multiply(1)` happened within the body of the `multiply(2)` in the expression of: ` multiply(1) * 2`. So now that the value of the `multiply(1)` is cleared, the method will be replaced with its returned value which is 1 and the final result of this expression at this point is now clear which is 2. (`1*2`)

Back to the multiply(3):

The call to the `multiply(2)` happened within the body of the `multiply(3)` in the expression of: ` multiply(2) * 3`. And now that the result of the call to the `multiply(2)` is cleared, this expression can be resolved as well.

So the final expression is: ` 2 * 3` which results 6 and that’s the value that will be returned to the caller method.

Back to the multiply (4):

This method was the first call from the `main()` method and it has the expression of : ` multiply(3) * 4` that caused the call to the `multiply(3)`.

Now that the result of the `multiply(3)` is cleared. This expression can also be resolved.

So the final expression is: `6 *4` which is equal to 24. And the value 24 is the one that will be returned to the caller method, which is `main()` in this case.

Back to the `main()` method:

This line of instruction was the reason to call the `multiply(4)` method: `int res = multiply(4); `

And now that the result of the `multipl(4)` is clear, the result will be assigned to the `res` variable. (So it will have the value 24 stored in its memory space).

In the next line, inside the `main()` method, the values stored in the `res` variable is sent to the output stream (the value is 24). After the last statement, the work of the `main()` method is done and so the program terminates.

That’s how recursion works.

What is StackOverFlow error in Java?

The StackOverFlow error happens when there’s no available space remained in the stack memory to be used for the program!

This error specially happens when we design a recursive function without any break point in the function in order to stop the function from calling itself after a certain point.

Example: throwing StackOverFlow exception in Java

public class Simple {
    public static void main(String[] args) {
        sum(10,20);
    }
    public static int sum (int valueOne , int valueTwo){
        sum(40,30);
        return valueOne + valueTwo;
    }
}

Output:

Exception: java.lang.StackOverflowError

After running this program, we got runtime exception which is saying that the stack over flowed!

Let’s see what happened:

We know that the entry point of the program is the `main()` method. When the program is running, a memory space in the stack is set aside for the `main()` method and the instructions inside this method will be executed one at a time.

Here, the only instruction is to call the method named `sum()`. So before running the instructions within the body of this second method, a memory space in the stack is allocated to the `sum()` method and now the instruction in the body of this method will be run.

The first instruction in the `sum` is to call a method named `sum()` which is basically itself!

To the eyes of the computer, there’s no difference between a method calling itself or calling another method. Basically, at this stage, another memory space in the stack is set aside for the `sum()` method that we called for the second time.

Now if you look at the stack, at the bottom it has the memory space that belongs to the `main()` method, next is the memory space that belongs to the first time we called the `sum()` method and the next memory space belongs to the second time we called the `sum()` method.

Because inside the body of the `sum()` method there’s nothing but calling the method itself again, inside the stack every time the call happens, a new memory space will be allocated to this method. This process will repeat itself to the point where there will be no stack memory space anymore and the program will crash.

That’s why we’ve got the `Stack over Flowed` error.

Notes on Java recursion:

1. Recursion is about simplifying a process. For example, if someone asked to add a range of numbers together (for example 0 to 100), we can simply use recursion.
2. Recursion is somewhat difficult to understand at first, but if you keep running other types of examples, it’ll soon get easy to understand.
3. If you don’t pay attention, a method can call itself infinitely. Of course, because the memory is limited, a method might call itself multiple times and then the program simply crashes because it ran out of memory, which also known as `Stack overflowed`.

So make sure there’s a condition in your method that finally will stop letting the method to call itself.