Tutorial 34: Recursion

When we talk about recursion, what we are saying is that the method is calling itself from within its body. For example, let us create a class and create a method within it that uses recursion:

public class Person {

            public static void calculate(int number) {

                        calculate(number);

            }

            public static void main(String[] args) {

                        calculate(7);

}

}

Figure 1: Stackoverflow error when a recursion has no end

If you run the above program, it will run for some time and then throw a StackOverflowError. The stack is a special area in the Java Virtual Machine memory and it is used for local variables and remembering which method called another method. The heap is another area of memory where objects are allocated when you use the “new” operator. 

In the above function definition, the outer function calculate calls the inner function calculate, which then calls the outer calculate indefinitely. However, recursion can work and we can use it to do a lot in Java, so long as there is a way to stop it from running forever. You should however not use recursion a lot in your program in order to avoid the danger of stack overflow.

So, how can we stop a recursive loop? Let’s say that in every loop, we decrement the value of the integer by one. Now you see, Java will negate one from the previous value and do so until there is a stack overflow error. We can use an if condition for example to stop the loop at some point like this:

public class Person {

            public static void calculate(int number) {

                        System.out.println(number);

if (number == 1) {

                                    return;

                        }

calculate(number - 1);

            }

            public static void main(String[] args) {

                        calculate(7);

}

}

Figure 2 Example of recursion

Now when we run the program, Java will deduct one from the value passed as a parameter and do so until it is equal to one, and then stop.

So can we do with recursion that is of value? Well, we can calculate the factorial. In math, a factorial is multiplying a number by the numbers less than it until you reach one. So the factorial of 5 is 5 x 4 x 3 x 2 x 1 = 120. The factorial of 3 is 3 x 2 x 1 = 6.

So in the above function, we can modify the method calculate() to determine the factorial of any number passed to it. We will also change the name of the function to “factorial” to make it sure it says what it does. We will also change its return type to int like this:

public class Person {

            public static int factorial(int number) {

if (number == 1) {

                                    return 1;

                        }

return factorial((number - 1) * number);

            }

            public static void main(String[] args) {

                        System.out.println(factorial(1));

}

}

 Figure 3 Factorial as an example of recursion

It is important to stick with small numbers. Otherwise, you will end up with a stack overflow error.

So that’s about it with regards to recursion. If you have any question or comment, please feel free to post it in the comments section below and I will make sure to address it.

Until next time, take care.