マッカーシーの91関数（英: McCarthy 91 function）とは、離散数学における再帰関数の一種であり、整数引数 "n" ≤ 101 に対して 91 を返し、"n" > 101 に対しては formula_1 を返す。計算機科学者ジョン・マッカーシーが考案した。マッカーシーの91関数の定義は次の通り。例 A:例 B:ジョン・マッカーシーはこれを、自身が開発したLISP言語で次のように書いた。この関数が期待通りに動作することの証明は次のようになる。90 ≤ "n" < 101 のとき、従って 90 ≤ "n" < 101 のとき "M"("n") = 91 である。以上を基本として、11個の数のブロック毎に証明していく。"a" ≤ "n" < "a" + 11 について "M"("n") = 91 であるとする。そのとき "a" - 11 ≤ "n" < "a" となるような任意の "n" について、以上のように "n" をブロック単位で考えれば "M"("n") = 91 であることが求められる。ブロック間に抜けているところはないので、"n" < 101 の場合常に "M"("n") = 91 となる。また、"n" = 101 の場合を特殊例として追加することもできる。

出典:wikipedia