Programa Java para encontrar la suma de N números usando recursividad

La recursividad es un proceso por el cual una función se llama a sí misma repetidamente hasta que cae bajo la condición base y se logra nuestro motivo.

Para resolver cualquier problema usando la recursividad , simplemente debemos seguir los siguientes pasos:

1. Suponga/identifique el problema más pequeño del problema que es similar al problema más grande/original.
2. Decida la respuesta a la entrada válida más pequeña o la entrada no válida más pequeña que actuaría como nuestra condición base.
3. Acérquese a la solución y vincule la respuesta al problema más pequeño dado por la función recursiva para encontrar la respuesta al problema más grande/original usándola.

Aquí, estamos ilustrando la Suma total usando la recursión que se puede hacer usando el almacenamiento de números en una array y tomando la suma de todos los números usando la recursión.

Ejemplo

Input: N = 5, arr[] = {70, 60, 90, 40, 80}
Output: Total Sum = 340

Input: N = 8, arr[] = {8, 7, 6, 5, 4, 3, 2, 1}
Output: Total Sum = 36

Acercarse:

Ahora, aplicaremos el enfoque discutido anteriormente en esta pregunta para calcular la suma de todos los elementos de forma recursiva.

• El problema más pequeño será la array desde el índice 1 hasta el último índice.
• La condición base será cuando el índice alcance la longitud de la array, es decir, fuera de la array, lo que significa que no existe ningún elemento, por lo que la suma devuelta debe ser 0.
• Ahora, nuestra tarea es resolver el problema más grande/original usando el resultado calculado por el problema más pequeño. Entonces, para hacer eso, como sabemos, el problema más pequeño es desde el índice1 hasta el último índice, por lo que si obtenemos la suma de este problema, luego de eso, para la suma total de la array, solo necesitamos agregar el primer elemento / iésimo elemento a esa respuesta y devolver nuestra respuesta final.

A continuación se muestra la implementación del enfoque anterior.

Ejemplo: 

// Java program to calculate the sum of
// the elements of the array recursively
 
import java.io.*;
 
class GFG {
    // recursive function
    public static int calculate_sum_using_recursion(int arr[], int i,
                                  int length)
    {
        // base condition - when reached end of the array
        // return 0
        if (i == length) {
            return 0;
        }
       
        // recursive condition - current element + sum of
        // (n-1) elements
       
        return arr[i]
         + calculate_sum_using_recursion(arr, i + 1,length);
       
    }
 
    public static void main(String[] args)
    {
       
        int N = 5, total_sum = 0;
       
        // create 1-D array to store numbers
        int arr[] = { 89, 75, 82, 60, 95 };
       
        // call function to calculate sum
        total_sum = calculate_sum_using_recursion(arr, 0, N);
       
        // print total sum
        System.out.println("The total of N numbers is : "
                           + total_sum);
    }
}

The total of N numbers is : 401

Complejidad del tiempo: O(N)

Espacio Auxiliar: O(N)

Enfoque 2: 

Podemos aplicar la recursión no solo de una manera, sino que puede haber una o más formas de resolver un solo problema usando la recursión.

En el enfoque anterior, comenzamos la recursión desde la dirección de avance y alcanzamos y alcanzamos la condición base en la última posición.

En este enfoque, consideraremos la variable de longitud en la función como el parámetro cambiante, donde la variable de longitud comenzará desde la última posición y el caso base llegará al frente fuera del índice de límite que es -1.

Ejemplo:

// Java program to calculate the sum of
// the elements of array using recursion
 
import java.io.*;
 
class GFG {
   
    // recursive function
    public static int calculate_sum_using_recursion(int arr[], int length)
    {
        // base condition - when reached -1 index
        // return 0
        if (length == -1) {
            return 0;
        }
       
        // recursive condition - current element + sum of
        // (n-1) elements
        return arr[length]
            + calculate_sum_using_recursion(arr,length - 1);
       
    }
 
    public static void main(String[] args)
    {
        int N = 8, total_sum = 0;
       
        // create 1-D array to store numbers
        int arr[] = { 8, 7, 6, 5, 4, 3, 2, 1 };
       
        // call function to calculate sum
        total_sum = calculate_sum_using_recursion(arr, N - 1);
       
        // print total sum
        System.out.println("The total of N numbers is : "
                           + total_sum);
    }
}

The total of N numbers is : 36

Complejidad del tiempo: O(N)

Espacio Auxiliar: O(N)