Funkcja Ackermanna

Funkcja Ackermanna – funkcja matematyczna odkryta przez Wilhelma Ackermanna w 1928 roku. Cechą charakterystyczną tej dwuargumentowej funkcji jest jej nadzwyczaj szybki wzrost. Funkcja Ackermanna jest prostym przykładem funkcji rekurencyjnej, niebędącej funkcją pierwotnie rekurencyjną. Funkcje pierwotnie rekurencyjne to większość znanych funkcji, między innymi dodawanie, funkcja wykładnicza itp. Funkcja Ackermanna często jest używana do testowania jakości optymalizacji kompilatorów – stosunki czasu wykonania pomiędzy różnymi kompilatorami tego samego języka czasami sięgają tysiąca. Jakość kodu generowana dla tego typu funkcji jest szczególnie ważna w językach funkcyjnych, gdzie używa się rekursji. Inną funkcją o własnościach podobnych do funkcji Ackermanna (tzn. będąca rekurencyjną i nie pierwotnie rekurencyjną) jest funkcja Sudana.