адача 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) установлено.