Рекурсивные функции (задание 16)

В задании 16 ЕГЭ функцию задают формулами, как в учебнике математики. Типичная формулировка звучит примерно так: «Алгоритм вычисления значения функции F(n), где n — натуральное число, задан соотношениями: F(n) = 1 при n = 1; F(n) = n + F(n − 1) при n > 1. Чему равно значение F(40)?»

Руками придётся раскрутить сорок шагов и не ошибиться ни в одном сложении. А бывает хуже: функция вызывает себя дважды, n измеряется тысячами, а промежуточные числа состоят из тысяч цифр. Программа же почти дословно повторяет условие и занимает пять строк. Сегодня научимся переписывать такие определения в Python, обходить ограничение глубины рекурсии и ускорять «тормозящие» функции так, чтобы ответ появлялся за доли секунды.