Рубрики

Хвостовая рекурсия для вычисления суммы элементов массива.

Для данного массива A [] нам нужно найти сумму его элементов, используя метод Tail Recursion . Как правило, мы хотим достичь хвостовой рекурсии (рекурсивная функция, в которой рекурсивный вызов — последнее, что делает функция), чтобы компиляторы могли оптимизировать код. По сути, если рекурсивный вызов является последним оператором, компилятору не нужно сохранять состояние родительского вызова.
Примеры:

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

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

Для метода линейной рекурсии, обратитесь: http://espressocode.top/sum-array-elements-using-recursion/

Логика: здесь ключом к хвостовой рекурсии является то, какая операция применяется с вызовом функции, сохраните ее как отдельный параметр функции.
Итак, сохраните сумму последних элементов K элементов в качестве параметра функции и верните сумму, когда K = 0.

C ++

#include <bits/stdc++.h>

using namespace std;

  
// Хвост рекурсивной функции

int arrSum(int* array, int size, int sum = 0)

{

    // Базовый вариант

    if (size == 0) 

        return sum;

  

    // вызов функции Observ sum + array [size-1]

    // для поддержания суммы элементов

    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;

}

python3

# Python3 реализация данного подхода.

  
# Хвост рекурсивной функции

def arrSum(array, size, Sum = 0): 

  

    # Базовый вариант

    if size == 0

        return Sum

  

    # Вызов функции Наблюдать за суммой + массив [размер-1]

    # поддерживать сумму элементов

    return arrSum(array, size - 1,

            Sum + array[size - 1]) 

  
Код водителя

if __name__ == "__main__":

  

    array = [2, 55, 1, 7

    size = len(array) 

    print(arrSum(array, size)) 

  
# Этот код предоставлен Rituraj Jain

Выход:

65

Сложность времени: O (n)

Рекомендуемые посты:

Хвостовая рекурсия для вычисления суммы элементов массива.

0.00 (0%) 0 votes