Презентация «Рекурсия на простых задачах»
Зачем рекурсии нужен базовый случай и где появляется ответ? Разберите цепочку вычислений для суммы от 1 до 3 и проверьте её при возврате.
О презентации «Рекурсия на простых задачах»
Сумму от единицы до n можно представить как n плюс сумму от единицы до n−1. Это правило работает, пока n — положительное целое. Для нуля используется отдельное определение: пустая сумма равна нулю. Оно даёт первый готовый ответ, от которого вычисляются остальные.
Для n = 3 сначала нужны результаты для 2, затем для 1 и 0. До базового случая операции сложения ждут результата вложенного вызова. При возврате получаем S(1) = 1, затем S(2) = 3 и S(3) = 6. Запись двух этапов помогает понять, где очередной вызов создаётся и где он возвращает значение.
При проверке рекурсивной записи задайте два вопроса. Есть ли случай, в котором ответ возвращается сразу? И приближает ли каждый новый вызов аргумент к этому случаю? В примере n уменьшается ровно на единицу, поэтому любые допустимые неотрицательные целые достигают нуля.
Вопросы по теме «Рекурсия на простых задачах»
Зачем задавать S(0) = 0?
Это базовый случай, в котором вычисление возвращает значение без нового вызова. Ноль также соответствует пустой сумме.
Как получается ответ 6 для S(3)?
Вызовы доходят до S(0) = 0. Затем возвращаются значения S(1) = 1 + 0, S(2) = 2 + 1 и S(3) = 3 + 3.
Что будет, если передать отрицательное целое в эту рекурсивную схему?
Правило уменьшения на единицу будет уводить аргумент от нуля. Поэтому пример определён для неотрицательных целых чисел, а отрицательное значение нужно отклонить.
Нужна другая тема?
Напишите свою тему или выберите близкую — PREZA подготовит новую презентацию.



























