Recurrencia de cola para calcular la suma de los elementos de la array.

Dado un arreglo A[], necesitamos encontrar la suma de sus elementos usando el Método de Recursión de Cola . Por lo general, queremos lograr recurrencia de cola (una función recursiva en la que la llamada recursiva es lo último que hace la función) para que los compiladores puedan optimizar el código. Básicamente, si la llamada recursiva es la última instrucción, el compilador no necesita guardar el estado de la llamada principal. 
Ejemplos: 
 

Input : A[] = {1, 8, 9}
Output : 18

Input : A[] = {2, 55, 1, 7}
Output : 65

Para el método de recursión lineal, consulte: https://www.geeksforgeeks.org/sum-array-elements-using-recursion/
Lógica: aquí la clave para la recursión de cola es cualquier operación que se aplique con la llamada de función, manténgala como una operación separada parámetro de función. 
Por lo tanto, mantenga la suma de los últimos elementos K elementos como un parámetro de función y devuelva la suma cuando K = 0.
 

C++

#include <bits/stdc++.h>
using namespace std;
 
// Tail recursive function
int arrSum(int* array, int size, int sum = 0)
{
    // Base Case
    if (size == 0)
        return sum;
 
    // Function Call Observe sum+array[size-1]
    // to maintain sum of elements
    return arrSum(array, size - 1, sum + array[size - 1]);
}
 
int main()
{
    int array[] = { 2, 55, 1, 7 };
    int size = sizeof(array) / sizeof(array[0]);
    cout << arrSum(array, size);
    return 0;
}

Java

// Java implementation of the given approach.
class GFG
{
 
// Tail recursive function
static int arrSum(int []array, int size, int sum)
{
    // Base Case
    if (size == 0)
        return sum;
 
    // Function Call Observe sum+array[size-1]
    // to maintain sum of elements
    return arrSum(array, size - 1, sum + array[size - 1]);
}
 
// Driver code
public static void main(String[] args)
{
    int array[] = { 2, 55, 1, 7 };
    int size = array.length;
    System.out.print(arrSum(array, size, 0));
}
}
 
// This code is contributed by Rajput-Ji

Python3

# Python3 implementation of the given approach.
 
# Tail recursive function
def arrSum(array, size, Sum = 0):
 
    # Base Case
    if size == 0:
        return Sum
 
    # Function Call Observe sum+array[size-1]
    # to maintain sum of elements
    return arrSum(array, size - 1,
            Sum + array[size - 1])
 
# Driver Code
if __name__ == "__main__":
 
    array = [2, 55, 1, 7]
    size = len(array)
    print(arrSum(array, size))
 
# This code is contributed by Rituraj Jain

C#

     
// C# implementation of the given approach.
using System;
 
class GFG
{
 
// Tail recursive function
static int arrSum(int []array, int size, int sum)
{
    // Base Case
    if (size == 0)
        return sum;
 
    // Function Call Observe sum+array[size-1]
    // to maintain sum of elements
    return arrSum(array, size - 1, sum + array[size - 1]);
}
 
// Driver code
public static void Main(String[] args)
{
    int []array = { 2, 55, 1, 7 };
    int size = array.Length;
    Console.WriteLine(arrSum(array, size, 0));
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
 
// Tail recursive function
function arrSum(array, size, sum = 0)
{
    // Base Case
    if (size == 0)
        return sum;
 
    // Function Call Observe sum+array[size-1]
    // to maintain sum of elements
    return arrSum(array, size - 1, sum + array[size - 1]);
}
 
var array = [2, 55, 1, 7];
var size = array.length;
document.write( arrSum(array, size));
 
</script>   
Producción: 

65

 

Complejidad de tiempo: O(n)
 

Publicación traducida automáticamente

Artículo escrito por krikti y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *