Rekursio

Rekursio liittyy ohjelmoinnin teorian aivan olennaisesti sellaisiin asioihin, joka tulee ymmärtää jos mielii ohjelmoida tietokoneella sama millä kielellä.

Klassinen opetusmateriaaleissa esitetty rekursio-ongelman asettelu on nk, ”Hanoin Tornit” -ongelma (Hanoi Towers), jossa seuraavat siirrot ovat riippuvaisia edellisestä siirrosta, ja oikean lopputuloksen saavuttamiseksi algoritmi, joka ratkaisee ongelman, on rekursiivinen, eli edellisten tulosten päälle kasautuu tulos kohti lopullista.

Alkuperäisessä Hanoin Tornin ongelmassa oli 64 kiekkoa, ja on totuus, että ihmisen elinaika ei riittäisi ratkaisemaan 64 kiekon Hanoin Tornia koska on olemassa sellainen termi. kuin aikakompleksisuus, mutta on mahdollista laatia algoritmi, joka ratkaisee verrattain useammankin kiekon Hanoin Tornit -ongelman verrattain nopeastikin.

Hanoin Tornin tarvittavien siirtojen lukumäärä on "2 potensiin n -1" ,jossa n edustaa kiekkojen lukumäärää.
Hanoin Tornin tarvittavien siirtojen lukumäärä on ”2 potensiin n -1” ,jossa n edustaa kiekkojen lukumäärää.

Toistojen vähentäminen rekursiolla

Yksi ohjelmoinnin teoriassa keskeisimpiä rakenteita on silmukat, joiden alkuperäinen idea on se, että saadaan ohjelmakoodin toistoa vähennettyä ja tätä kautta virheiden lukumäärä pienennettyä. Sitä vartenhan ihminen on kehittänyt silmukat tietokonekieleen ohjelmoinnin historian saatossa.

Olen julkaissut GitHub-profiilissani monta rekursiivista ratkaisua, esimerkiksi myös Pythonilla yksinkertaisen kertoma-laskennan, joka on ollut suosittu ulosmenevä linkki Tietokone-blogissani pitkään.

Juteltuani StackOverFlow:n palstalla luomastani binaarista ->desimaaliluvuksi -muunnosfunktiosta sen modifioimisieksi rekursiiviseksi, niin siellä eräs kommentoija väitti, että kaikki silmukat voidaan korvata ”saparo”-rekursiolla, en tiedä, kun en ole koskaan kuullut virallista suomennosta termile (Tail Recursion). Kommentoija käytti nimenomaan ”Tail” -sanaa ja se on suoraan suomennettuna ”Saparo, häntä” tai vastaava.

Rekursiivinen Python-metodi -esimerkki, joka korvaa for-silmukassa laskettavat 10->1 alas järjestyksessä ja tulostaa ne ruudulle:

def calc (x):
if (x<=0):
return 0
print (x)
return calc(x-1)
calc(10)

Tuo ylläoleva Python koodi tulostaa ruudulle luvu kympistä ykköseen, joka vastaa seuraavassa esittämääni for-silmukkaa tulosteen ollessa käänteinen:

for x in range(0,10):
print(x+1)

Kertomasta (Python)

Lukiosta opittu kertoma on myös rekursiivisesti ratkaistavissa. Julkaisin aiheesta artikkelin siitä havainnollistavan kuvan kera Tietokone-blogissani vuoden 2019 tammikuun 17. päivä. Suora linkki artikkeliin, josta sen voi lukea on vielä on tässä.

Rekursiivisen kertoma-metodin yleinen esitys graafisesti
Rekursiivisen kertoma-metodin yleinen esitys graafisesti

Kertoma-metodi Python-kielellä ohjelmoituna näyttää seuraavalta:

def calculate(value):
if (value == 0):
return 1
else:
return value*calculate(int(value)-1)

Huomautus sivun Python-esimerkeistäni (An Apology and legal disclaimer)

Kuten kaikki Python-kielellä joskus tekemisissä olleet havaitsevat, sisennykset eivät ole kohdallaan tämän sivun esimerkeissä. WordPress -hallintapaneelissa määrittelin koodini tälle sivulle HTML-tagilla <code></code>, mutta jostain syystä käyttämäni sisällönhallinta-julkaisujärjestelmä ei näytä sisennyksiä vierailijoille, vaikka hallintapaneelissa koodirivit on oikein sisennetty. Pahoitteluni tästä. Jos käytätte leikepöydän Kopiointi-Liitä -toiminta esimerkiksi Notepad++ -ohjelmaan siirrettäesä koodejani tältä sivulta, muistakaa hoitaa itse sisennykset, jotta saatte koodin toimimaan. Syntaksi on kuitenkin tarkistettu ja oikeellinen kaikissa tällä sivulla esittämissäni rekursio-esimerkeissä ja muissa koodi-esimerkeissä.