[...]
Mutta on myös toinen, vähemmän ilmeinen syy Prolog-ohjelmien vahingossa suuriin kompleksisuuksiin. Suuria kompleksisuuksia saa ylipäänsä aikaiseksi moninkertaisilla rekursioilla. Esimerkiksi funktio, joka kutsuu itseään, on yleensä kompleksisuudeltaan O(n). Funktio, joka kutsuu O(n)-funktiota ja itseään, on yleensä kompleksisuudeltaan O(n^2). Nämä funktiot vielä pystyy kuvaamaan (sisäkkäisillä) silmukoilla, ja niinpä polynomiset kompleksisuudet ovat tuttuja myös ei-funktionaalisilla kielillä ohjelmoiville.
Funktio, joka kutsuu itseään kahdesti, on tyypillisesti kompleksisuudeltaan O(2^n) eli eksponentiaalinen. Mutta nämä ovat vain primitiivirekursiivisia funktioita. Funktio, joka tekee toisen tai korkeamman asteen rekursioita, on tyypillisesti kompleksisuudeltaan yli kaikkien tavallisesti matematiikassa käytettyjen funktioiden. (Tämä johtuu siitä, että kaikilla matematiikassa tavallisilla funktioilla on primitiivirekursiivinen määritelmä.) Ackermannin funktio on esimerkki toisen asteen rekursiosta; se kykenee saamaan ällistyttäviä arvoja yksinkertaisesti siitä syystä, että se sisältää kahden rekursiivisen kutsun komposition (ts. yhden palautusarvo annetaan toiselle argumentiksi).
Funktionaalisissa ohjelmointikielissä korkeamman asteen rekursiot on helppoa nähdä syntaktisesti: mikäli rekursiivisen kutsun "sisällä" (ts. argumenttilistassa) on toinen rekursiivinen kutsu, kyse on korkeamman asteen rekursiosta. Logiikkaohjelmointikielissä kuitenkin kompositiot esitetään "littanassa" muodossa, jolloin korkeamman asteen rekursioita voi syntyä vahingossa. Luulisin, että niitä voi jopa esiintyä vain tietyille suoritussuunnille, mutta tästä en ole varma.
[...]