Esimesed katsed anda algoritmile matemaatiliselt range kuju tehti 1920. aastatel. Esmalt arvati, et formaliseerimiseks kõlbab lihtrekursiivne funktsioon. 1928 avaldas Wilhelm Ackermann näite funktsioonist, mis on algoritmiliselt arvutatav, kuid ei ole lihtrekursiivne. 1930. aastatel lõid Alonzo Church ja Stephen Kleene lambdaarvutuse. Sel ajal lõid ka Alan Turing ja Emil Leon Post Turingi masina ning Kurt Gödeli ja Jacques Herbrand võtsid kasutusele täisrekursiivse funktsiooni mõiste.