адача 18. Функция Маккарти. Показать, что для приведенной ниже рекурсивной программы-функции
при целочисленных значениях n справедлива формула:
makkarti(n) = max(n - 10, 91). (5)
Решение. Относительно параметра n возможны три случая:
n > 100, 90 £ n £ 100, - ¥ < n < 90.
В первом из них в силу базы рекурсии следует, что makkarti(n)=n-10. Во втором случае:
Наконец, всякое начальное n<90 в соответствии с декомпозицией через конечное число рекурсивных вызовов приводит ко второму случаю. Отсюда опять makkarti(n)=91. Таким образом, (5) справедливо во всех случаях.
Заметим, что из проведенных рассуждений вытекает, что рассматриваемая функция может быть определена более просто, например так:
адача 19. Функция Кадью. Показать, что для приведенной ниже рекурсивной программы-функции
при целочисленных значениях x справедлива формула:
cadiou(x, 0, 1) = x!. (6)
Решение. При y=0 и z=1 имеем z=y!. Далее из характера декомпозиции функции cadiou() ясно, что z=y! остается инвариантом в ходе рекурсивных вызовов. Вместе с условием завершения x=y это и дает z=x! и (6) установлено.