Funktiot

Esimerkki epäsuorasta rekursiosta

Lukuohje

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

Epäsuorassa rekursiossa funktio A kutsuu funktiota B, joka puolestaan kutsuu A:ta. Tässä tarkastellaan lausekkeen jäsentämistä ja evaluointia eli sen arvon laskemista. Jäsentämisessä tarkistetaan, että lauseke noudattaa annettua kielioppia.

Lausekkeen kielioppi

Lausekkeiden kielioppi voidaan kuvata näin:

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

Kielioppi on kirjoitettu BNF-muodossa (Backus–Naur Form). Välisymbolit (nonterminal) kirjoitetaan kulmasulkeisiin, ja loppusymbolit (terminal) kirjoitetaan sellaisinaan.

Kielioppi sallii yksinumeroiset luvut 0–9, operaattorit + ja - sekä sulkeet. Esimerkkejä kieliopin mukaisista lausekkeista:

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

Jos lauseke noudattaa kielioppia, se voidaan johtaa kieliopin säännöistä soveltamalla niitä toistuvasti. Esimerkiksi 1 - (2 + 3) voidaan johtaa näin:

<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/. Se jäsentää annetun lausekkeen ja laskee sen arvon, jos lauseke noudattaa kielioppia.

Pääohjelman lisäksi ohjelmassa on kaksi funktiota, yksi kumpaakin kieliopin sääntöä varten: parse_term ja parse_expr. Funktiot kutsuvat toisiaan, joten kyseessä on epäsuora rekursio. Tämän vuoksi ainakin toinen funktioista täytyy esitellä ennen sen ensimmäistä kutsukohtaa.

parse_expr()
  └─ kutsuu parse_term()
       └─ sulkeiden kohdalla kutsuu parse_expr()
            └─ kutsuu taas parse_term()

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

Ohjelman funktiot on toteutettu suoraviivaisesti kieliopin perusteella:

  • parse_term tarkistaa ensin, onko termi yksinumeroinen luku. Jos termi alkaa vasemmalla sulkeella, funktio ohittaa sen, kutsuu parse_expr-funktiota ja ohittaa lopuksi oikean sulkeen.
  • parse_expr kutsuu ensin parse_term-funktiota, koska lauseke alkaa termillä. Sen jälkeen se tarkistaa, jatkuuko lauseke plus- tai miinusoperaattorilla, ja laskee arvon sen mukaisesti.

Rekursion hyödyllisyydestä

Tämänkaltaista jäsentäjää olisi vaikea toteuttaa yhtä suoraviivaisesti ilman rekursiota. Rekursio sopii ongelmiin, joiden rakenne vastaa luontevasti pienempiä, samanmuotoisia osaongelmia. Ohjelmaa on myös helppo laajentaa: esimerkiksi kertolaskulle ja jakolaskulle voi lisätä kielioppisäännöt ja niitä vastaavan käsittelyn.