адача 2. Вкладчик положил в сбербанк сумму в sum единиц под p процентов за один период времени (год, месяц, неделя и т. д.). Составить рекурсивную программу-функцию, возвращающую величину вклада по истечении n периодов времени (n = 1, 2, …).

Решение. Пусть invest(sum,p,n) - искомая функция. Для данной задачи вычисления значений invest() можно проводить по известной формуле:

Однако в учебных целях нас интересует именно рекурсивный вариант алгоритма решения задачи. Рекурсию будем осуществлять по параметру n. Тривиальный случай очевиден. Если вклад положен на хранение и взят сразу же, то есть до истечения первого периода времени начисления процентов, то возврату подлежит начальная сумма вклада - sum. Далее, декомпозиция может быть реализована исходя из следующего факта. Положить некоторую сумму в банк на n периодов – это то же самое, что положить эту сумму на n – 1 периодов, а затем полученную сумму взять и снова положить на один период. Соответствующий вариант программы-функции решения задачи выглядит так:

Контрольные примеры:

Схема рекурсивных вызовов здесь такая же, как при вычислении значений функции facto(n). Нетрудно видеть, что общее количество рекурсивных вызовов при вычислении invest(sum,p,n) равно n. При необходимости можно было бы уменьшить это значение до величины log₂(n).