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>
65
Complejidad de tiempo: O(n)