Как построить рекуррентное уравнение для количества выполнения сложения кубов в рекурсивном алгоритме?

Question

Как построить рекуррентное уравнение для количества выполнения сложения кубов в рекурсивном алгоритме?

Виктор Корнеплод Ученик (90), закрыт 6 дней назад

S(n) = 1^3 + 2^3 + ... + n^3.
сам алгоритм: возвращать S(n-1) + n*n*n при условии, что n != 1.
Нужно построить рекуррентеное уравнение для количества выполнения основной операции алгоритма и найти его решение.

Answer 1

А аргументы n у Вас какими предполагаются? В Пайтоне ведь есть строго определённая стандартная глубина рекурсии и такой, например, код

 def S(n): return 1 if n == 1 else n**3+S(n-1) 
while True: print(S(int(input('n: '))))

может не сработать уже при n=1000, хотя прекрасно будет работать для небольших n. А если надо чтобы n было, скажем, до десяти миллионов, тогда надо как-нибудь так:

 from sys import setrecursionlimit 
setrecursionlimit(10000010) 
def S(n): return 1 if n == 1 else n**3+S(n-1) 
while True: print(S(int(input('n: '))))

В общем простейший код такой:

 def S(n): return 1 if n == 1 else n**3+S(n-1) 
print(S(int(input('n: '))))

А дальше надо смотреть что программа должна делать в тех или иных случаях. Можно глубину рекурсии увеличивать до максимума, можно вводить перехват исключений для некорректных вводимых данных или сделать измерение времени работы кода, сравнивая вычисление суммы кубов первых n натуральных чисел при помощи функции с рекурсивным вызовом и при помощи циклов, специтерирования или формулы
⅀(k=1;n)k³ = ¼·(n·(n+1))².
Но это если надо. А не надо так и не надо! Обёртку в бесконечный цикл для множественного ввода-вывода тоже можно ставить, а можно и без неё обойтись.