Esimerkki epäsuorasta rekursiosta¶

Lukuohje

Jos et ymmärrä esimerkkiä, ei kannata huolestua.

Edellä mainittiin, että epäsuora rekursio tarkoittaa sitä, että funktio A kutsuu funktiota B, ja B kutsuu A:ta.

Esimerkkinä epäsuorasta rekursiosta tarkastellaan lausekkeen jäsentämistä ja evaluointia (eli lausekkeen arvon laskemista). Jäsentämällä (parse) tarkistetaan, että lauseke on oikean muotoinen eli että se noudattaa annettua kielioppia.

Lausekkeen kielioppi¶

Lauseke voidaan esittää kieliopilla:

<Expr> ::= <Term> + <Expr> | <Term> - <Expr> | <Term>
<Term> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | ( <Expr> )

Yllä oleva kielioppi on kirjoitettu BNF-muotoon (Backus-Naur Form). Siinä välisymbolit (nonterminal) kirjoitetaan kulmasulkeiden sisään, ja loppusymbolit (terminal) sellaisenaan.

Kielioppi sallimia loppusymboleita ovat yksinumeroiset luvut (0 - 9), operaattorit + ja - sekä sulut. Kielioppi sallii esimerkiksi lausekkeet:

2+3
2+3-4
1-(2+3)
(2+3)
((2+3))
1+(6-7)-(2+4+5+(2+3))

Jos annettu lauseke noudattaa kielioppia, niin lauseke voidaan voidaan johtaa (derive) kieliopista soveltamalla jompaakumpaa kieliopin sääntöä riittävän monta kertaa. Esimerkiksi lauseke 1 - (2 + 3) voidaan johtaa seuraavasti:

<Expr>
     -> <Term> - <Expr>
     -> 1 - <Expr>
     -> 1 - <Term>
     -> 1 - ( <Expr> )
     -> 1 - ( <Term> + <Expr> )
     -> 1 - ( 2 + <Expr> )
     -> 1 - ( 2 + <Term> )
     -> 1 - ( 2 + 3 )

Ohjelmakoodi¶

Tarkasteltava ohjelma löytyy hakemistosta examples/02/expression/. Ohjelma jäsentää annetun lausekkeen, ja jos lauseke noudattaa kielioppia, niin ohjelma laskee sen arvon.

Ohjelmassa on pääohjelmafunktion lisäksi kaksi muuta funktiota kumpaakin kieliopin sääntöä varten: parse_term ja parse_expr. Nämä kumpikin kutsuvat toisiansa, eli kyseessä on epäsuora rekursio. Tästä syystä tarvitaan ennakkoesittely ainakin toiselle funktiolle.

Rekursio nähdään myös kieliopissa: <Expr>-säännössä esiintyy <Term>, ja <Term>-säännössä esiintyy <Expr>.

Ohjelman funktiot on toteutettu hyvin suoraviivaisesti kieliopin perusteella. Esimerkiksi funktiossa parse_term tarkastellaan ensin tapauksia, joissa termi on jokin numero. Sen jälkeen käsitellään tapaus, jossa termi on sulkujen sisällä oleva lauseke. Tällöin ohitetaan vasen sulkumerkki, ja sen jälkeen kutsutaan rekursiivisesti funktiota parse_expr. Lopuksi ohitetaan vielä oikea sulkumerkki.

Vastaavasti funktiossa parse_expr tarkastellaan kieliopin tapaukset erikseen. Lauseke voi olla pelkkä termi (esimerkiksi vain jokin luku vaikkapa 2), tai lauseke voi koostua kahdesta termistä, joiden välissä on plus-merkki (esimerkiksi 2+3), tai lauseke voi koostua kahdesta termistä, joiden välissä on miinus-merkki (esimerkiksi 2-3). Joka tapauksessa siis lausekkeessa on ensin termi, ja siksi heti aluksi kutsutaan rekursiivisesti funktiota parse_term. Sen jälkeen tarkistetaan, tuleeko vielä operaattori (+ tai -) ja lasketaan lausekkeen arvo sopivalla tavalla.

Rekursion hyödyllisyydestä¶

Tämän tyylistä ohjelmaa olisi vaikea toteuttaa muuten kuin rekursiivisesti. Rekursio on siis hyödyllinen asia osata. Ohjelma olisi hyvin helppo laajentaa esimerkiksi käsittelemään myös kerto- ja jakolaskun. Tai jos kieliopissa olisi enemmän sääntöjä, niillekin voitaisiin hyvin suoraviivaisesti toteuttaa omat funktionsa.