Recursion in Java

To understand what recursion is, you need to understand what recursion is. In fact, there is nothing difficult in understanding such functions; you only need to understand it well once. And practice when it comes to programming. Recursion in Java - 1

Recursion occurs not only in programming, but also in real life. Take a mirror in your hands and stand in front of another mirror. The reflection of the reflection will be reflected in the reflection and so on. You will see an infinite number of reflections going into infinity. You can find more about “real” recursion in the article “ Dedicated to Groundhog Day... ” Let’s return from the real world to the everyday life of a programmer. Simple definition: Recursive functions in java are functions that call themselves. Let me give you a very simple and very harmful example:

public void recursionFucn() {
    System.out.println("Привет, JavaRush!");
    recursionFucn();
}

Why is it harmful? I suggest you check it yourself! If you decide to take this adventure (and you most likely will, you programmer!), write in the comments what error the JVM will throw =) This example, and many others, demonstrate that the use of recursion in Java must be approached carefully. You need to understand where, when and why such an approach to solving a problem is justified, and make sure that your function does not turn the execution of the program into “Groundhog Day”. There are two more important definitions for understanding recursion:

Recursion basis - the condition for exiting the block of recursive calls - the basic solution to the problem, under conditions when there is no need to call recursion.
The recursion step is when a function calls itself when changing parameters.

A classic example of using a recursive function is calculating the factorial of a number. In case you forgot, let me remind you: the factorial of a positive integer N(denoted as N!) is the product of numbers from 1 до N: N! = 1 * 2 * 3 * … (N - 1) * N. By the way, the factorial of zero by definition is equal to 1. So the factorial can be found for any positive integer and zero (in the language of mathematics - for the set of non-negative integers or for the set of natural numbers and zero). I think you understand that you can program factorial using loops. Actually, here is a non-recursive method for solving this problem:

private int fact(int n) {
    int result = 1;
    for (int i = 1; i <= n; i++) {
        result = result * i;
    }
    return result;
}

Let's add a check that the number is positive and an integer, and a separate check for zero.

private int fact(int n) {
    if (n < 0) {
        System.out.println("Зачем тебе факториал из отрицательного числа?");
         return null;
    }
    int result = 1;
    if (n == 0) {
        return result;
    }
    for (int i = 1; i <= n; i++) {
        result = result * i;
    }
    return result;
}

Now I will give the method code for recursively solving this problem:

private int factorial(int n) {
    int result = 1;
    if (n == 1 || n == 0) {
        return result;
    }
    result = n * factorial(n-1);
    return result;
}

Let's look at the output results for the calls:

System.out.println(factorial(0));
System.out.println(factorial(1));
System.out.println(factorial(2));
System.out.println(factorial(3));
System.out.println(factorial(4));
System.out.println(factorial(5));
System.out.println(factorial(6));

We get the expected values:

Let's add a nice output and calculate the factorial for a larger number:

private int factorial(int n) {
    int result = 1;

    if (n == 0) {
        System.out.print(" = ");
        return result;
    }
    if (n == 1) {
        System.out.print(" * 1 = ");
        return result;
    }

    System.out.print(n);
    if (n != 2) {
        System.out.print(" * ");
    }

    result = n * factorial(n-1);
    return result;
}


System.out.println(factorial(15) + "!");

We get: 15 * 14 * 13 * 12 * 11 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 1 307 674 368 000! In this case, the use of a recursive function is justified and safe. We have clearly defined the condition for exiting the recursive block, and we are confident that it is achievable: we enter a non-negative integer number, if the number is equal to zero or one, we return the result, if the number is greater, we multiply the result by a function of the number n-1. Using the factorial of three as an example:

factorial(3) внутри себя выполнит следующее:
	result = 3 * factorial(2); (рекурсивный вызов)

	factorial(2) внутри себя выполнит следующее:
		result = 2 * factorial(1); (рекурсивный вызов)

		factorial(1) вернет 1 (базис рекурсии)

	factorial(2) вернет 2 * 1

factorial(3) вернет 3 * 2 * 1

Regarding caution in use: what is the vulnerability of this function? If you give a method a negative number as a parameter, then the check

if (n == 1 || n == 0) {
    return result;
}

makes no sense and we will end up in an endless cycle of calling ourselves. It is worth adding a check for non-negativity:

if (n < 0) {
	System.out.println(«Зачем тебе факториал отрицательного числа?»);
	return null;
}

And all will be well.

What is the advantage of one method over another? It doesn't seem like there's a big difference, but in fact, a lot of recursive calls will have a negative impact on performance and memory consumption: the call stack is an almost uncontrollable resource and under different conditions for calling the same recursive function, we may or may not get problems associated with this resource. Almost all problems solved using iterations (cycles like for-each) can also be solved recursively. The advantage of recursion is readability and ease of writing, we talked about the disadvantages above: the opportunity to “shoot yourself in the foot” is not illusory. You need to be even more careful when using so-called “complex recursion”: A function A()will call a function B()that calls a function A(). Solving such problems requires a full understanding of how recursion works. An example of such a task: calculating the value of x^n/(n!). The factorial, as we discussed above, is defined on the set of non-negative integers. Finally, I will provide the solution code. Complex recursion will consist of two methods:

private double calculate(int x, int n) {
    return power(x, n) / n;
}
private double power(int x, int n) {
    if (n == 1) return x;
    return x * calculate(x, n - 1);
}

To enter recursion, a method is used calculate, which calls a method power, which in turn calls a method calculate. We defined the recursion basis in the power method:

if (n == 1) return x;

The recursion step is also defined there:

return x * calculate(x, n - 1);

It remains to add a check for the validity of the input data:

Any number other than zero is equal to the power of zero 1. If n = 0, then n! = 1. Need to return it 1.
Zero to any power is equal to zero.
We will not consider type uncertainty 0^0and will accept such input data as invalid.

With all the checks, the methods will look like this:

private double calculate(int x, int n) throws ArithmeticException {
    if (x == 0 && n == 0) {
        throw new ArithmeticException("Невалидные входные данные: Неопределенность типа 0^0");
    }

    if (n < 0) {
        throw new ArithmeticException("Невалидные входные данные: Факториал из отрицательного числа!");
    }

    if (n == 0) {
        return 1;
    }

    if (x == 0) {
        return 0;
    }

    if (x == 0) {
        return 0;
    }
    return power(x, n) / n;
}

private double power(int x, int n) {
    if (n == 1) return x;
    return x * calculate(x, n - 1);
}

Well, when calling a function you need to remember to catch the error:

try {
    System.out.println(calculate(x, n));
} catch (ArithmeticException e) {
    System.out.println(e.getMessage());
}

Comments

TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION