Java. Recursion. Examples of tasks solving. Advantages and disadvantages of recursion

Recursion. Examples of tasks solving. Advantages and disadvantages of recursion

Search other websites:

1. What is recursion? What is called recursion?

In theory of algorithms, the following definition of recursion is given: recursion is a method of defining a function in which the result of returning from a function for a given argument value is determined based on the result of returning from the same function for the previous (smaller or larger) argument value.

In other words, recursion is a function call itself to go to the next step of the recursion. In order for the next iteration step to differ from the previous one, the value of at least one of the function parameters must change during the recursive call.

⇑

2. Explanation to the implementation of tasks on recursion. How to organize a recursive function call?

A recursive function call can be made if the algorithm is defined recursively. The use of recursion is not always effective, for example, in cases where many variables are used or affect the number of iterations of the cycle. However, cycles in which the number of variable values (iterators) is not very large can be implemented by recursion.

To turn a cyclic process into a recursive process, you need to be able to identify three important points:

condition for ending the recursive process. For example, if a counter or an iterator with the name k changes from 1 to 10 in ascending order, then the termination condition is the achievement of the value k = 10. The termination condition is specified in the return statement;
the formula of the next element or iterator that is used in the recursive process. This formula is specified in the return statement;
the list of parameters that are passed to the recursive function. One of the parameters is necessarily an iterator (counter), changing its value. Other parameters are optional, for example, a reference to the array being processed.

⇑

3. Search for the sum of array items. Example

For this example, you can create your own recursive functions that define any sums of the elements of any arrays.

Task. An array of numbers A is given. Develop a recursive function that calculates the sum of the elements of an array:

S = A[0] + A[1] + … + A[n],

here n – the number of items in the array. The program code of the function is as follows:

// recursion - the sum of the elements of the array
static int Sum(int i, int[] A) {
    if (i==(A.length-1))
        return A[i];
    return A[i] + Sum(i+1,A);
}

In the above code, the function accepts two parameters. The first parameter i is the value of the current index, which changes its value with each recursive call. The second parameter A – an array whose elements are summed.

The last element of the array has the index A.length-1. Exit the function when the last element of the array is reached. Therefore, the text of the Sum() function specifies the condition for terminating the recursive process:

if (i==(A.length-1))
    return A[i];

In Java, an array is an instance (object) of a class, so the number of elements in an array is determined by the length property. This is convenient, since you do not need to pass the dimension of the array as a parameter (unlike some other programming languages).

Since, the sum of the current value of A[i] is carried out with the following, the line is indicated

// A[i] - current value, Sum(i+1,A) – the next value in the array
return A[i] + Sum(i+1,A);

here Sum(i+1, A) means the next value of array A, which will be calculated at the next (lower) level of the recursive call. The i+1 parameter indicates that at the next level of recursion, the next element of the array will be taken.

Using the Sum() function in another program code can be as follows:

int[] A = { 3, 12, 10, 11 };
int sum;
sum = Sum(0,A); // sum = 36

⇑

4. Calculation factorial – n!. Example

The example has developed a recursive function that calculates the factorial of a given number n

f = 1 · 2 · … · (n-1) · n

here n>=1.

The program code of the function is as follows:

// calculating the factorial of n
int Fact(int n) {
    if (n==1)
        return 1; // termination condition of the recursive process
    else
        return n*Fact(n-1); // Fact(n-1) - the result of the next function calls
}

In this function, a recursive call to the Fact() function occurs with the parameter n, which changes from n to 1 in descending order. The recursive process ends when n = 1.

Returning to a higher level returns the current value of n and the result of the calculations for the following recursive calls:

return n*Fact(n-1);

Using a function in another program code:

int fact;
fact = Fact(7); // fact = 5040

⇑

5. The program for calculating the greatest common divisor for the Euclidean algorithm. Example

The example defines the greatest common divisor using the Euclidean formula:

The program code of the function is as follows:

// GCD - Euclidean Algorithm
int MaxDivisor(int n, int m) {
    if (n==m) return n;
    else
        if (n>m) return MaxDivisor(n-m, m);
        else
            return MaxDivisor(n, m-n); // n<m
}

Using the MaxDivisor function

int md;
md = MaxDivisor(28,20); // md = 4

⇑

6. Calculate the n-th term in the Fibonacci number sequence. Example

The sequence of Fibonacci numbers is:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …

In the sequence of Fibonacci numbers, each subsequent number n is defined as the sum of the two preceding numbers: (n-1) + (n-2). Therefore, in the formula of a recursive process there can be a call of the sum of two functions and not one. Termination of the recursive process is achieved if the value n = 0.

The following is the text of the GetNFibonacci() function

// Determining the n-th Fibonacci number
static int GetNFibonacci(int n) {
    if (n>1)
        return GetNFibonacci(n-2)+GetNFibonacci(n-1); // Fibonacci formula
    else
        if (n==1)
            return 1;
        else
            return 0; // if n==0
}

Using the GetNFibonacci() method in other program code:

int n;
n = GetNFibonacci(10); // n = 55

⇑

7. Advantages and disadvantages of recursion

Recursion is often compared with iteration. The organization of a cyclic process using recursion has its advantages and disadvantages.

The following interrelated advantages of recursion can be distinguished:

natural expression of seemingly complex algorithms.
recursive algorithm is more readable in comparison with iterative;
for many common tasks, recursion is easier to implement than iteration. Recursion is well suited for implementing list traversal algorithms, trees, graphs, etc.

The disadvantages of recursion are as follows:

compared to iteration, a multiple call to a recursive function takes longer. This is due to the fact that when the recursive method is called, its parameters are copied to the stack. Also the temporary values of local internal variables are saved. When the call to the recursive function is completed, the previous values of the parameters are pulled out of the stack, which leads to unnecessary operations. The iteration algorithm for the same task is faster;
recursive process needs more memory. This is due to the fact that when a recursive call is necessary to save the previous value of the internal variables of the calling function, so that after the completion of the recursive call to restore its execution. Thus, if the recursive function is called many times, then this can lead to excessive memory usage.

⇑

BestProg