Задание 16 ЕГЭ по информатике: рекурсия, которая сокращается

Разбираю задачу 16 из ЕГЭ по информатике на рекурсивную функцию F(n). В условии задано: F(n) равно n в степени n², если n не больше 1000. F(n) равно n плюс 2F(n минус 2) плюс 6F(n минус 6), если n больше 1000. Нужно найти значение выражения: F(20024) минус 2F(20022) минус 3F(20020) плюс 18F(20014). На первый взгляд задача выглядит тяжёлой: значения функции огромные, рекурсия длинная, а прямой подсчёт быстро превращается в неудобные вычисления. Но в таких задачах почти всегда есть идея сокращения. В видео показываю: как аккуратно раскрывать F(20024), F(20022) и F(20020); почему не нужно считать сами огромные значения функции; как увидеть, какие части выражения сокращаются; как довести задачу до нормальных чисел; как решать подобные задачи 16 без рекурсии в лоб и без лишних костылей в Python. Этот разбор подойдёт тем, кто готовится к ЕГЭ по информатике и хочет научиться понимать рекурсивные функции, а не просто запускать код и надеяться, что он справится. Хэштеги: #егэ #информатика #егэинформатика #рекурсия #python